Phân tích số

View as PDF

Submit solution


Points: 0.27 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Ðược add lên bởi Khúc Anh Tuấn
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.