Ở một thế giới song song, tichpx đang dạy lớp nqson môn toán rời rạc chương II: Phương pháp đếm. Vậy nên, tichpx cho lớp nqson một bài tập như sau:

Cho số tự nhiên \(n\), hãy đếm xem có bao nhiêu cách tách số này thành tổng các số nguyên dương khác nhau.

Ví dụ: \(6 = 1+2+3 = 1+5 = 2+4 = 6\) -> có \(4\) cách tách.

Đây là 1 bài rất khó và nqson rất hay cúp học môn này. Bạn hãy giúp nqson giải bài tập này nhé.

Đầu vào

Một dòng chứa số tự nhiên \(n\).

Đầu ra

Một số tự nhiên duy nhất là kết quả của bài toán, đáp án có thể rất lớn nên bạn hãy chia dư cho \(10^9+7\).

Subtask

\(30\%\) số test có \(n \le 20\).

\(30\%\) số test có \(20 < n \le 100\).

\(40\%\) số test còn lại có \(100 < n \le 10^4\).

Ví dụ

Đầu vào:

6

Đầu ra:

4

P/S: Phổ cập kiến thức cho K63 (PHẦN NÀY KHÔNG QUAN TRỌNG VỚI ĐỀ BÀI, CÁC BẠN CÓ THỂ BỎ QUA):

Với \(a, b, c, m\) là các số nguyên, \(m > 0\). Ta có cách tính mod không âm với số \(m\) như sau:

• \((a+b)\% m = (a\%m + b\%m + m)\%m\).
• \((a-b)\% m= (a\%m - b\%m + m)\%m\).
• \((a*b)\% m = (a\%m * b\%m + m)\%m\).
• \((a^b)\% m = ((a\%m) ^ b)\%m\).
• \((a/b)\% m \neq (a\%m / b\%m)\%m\) (Đây là trường hợp ngoại lệ)
• Với \(P\) là đa thức trên các biến \(x_1, x_2,...\): \(P(x_1,x_2,...)\%m = P(x_1\%m, x_2\%m,...)\%m\).

Tổng kết: hãy %mod khi tính toán mọi phép tính, trừ phép chia.