Phân tích số

Xem dạng PDF

Gửi bài giải


Điểm: 0,27 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
Ðược add lên bởi Khúc Anh Tuấn
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hãy đếm số cách phân tích số ~N~ ~(N \le 100000)~ thành tổng các số nguyên dương.

Lưu ý ~2~ cách chỉ khác nhau về thứ tự các số hạng được coi là giống nhau. Ví dụ ~4~ có ~5~ cách phân tích sau:

  1. ~4 = 1 + 1 + 1 + 1~
  2. ~4 = 1 + 1 + 2~
  3. ~4 = 1 + 3~
  4. ~4 = 2 + 2~
  5. ~4 = 4~

Hai cách phân tích ~4 = 1 + 3 = 3 + 1~ chỉ được tính một lần.

Vì kết quả sẽ rất lớn nên các bạn chỉ cần đưa ra phần dư của phép chia số cách tìm được cho ~1000000000~ ~(10^{9})~.

Input

Một số tự nhiên ~N~ duy nhất.

Output

In ra phần dư của của số cách tìm được cho ~10^{9}~.

Sample Input

4

Sample Output

5

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.