Submit solution
Points:
0.27 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
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:
- ~4 = 1 + 1 + 1 + 1~
- ~4 = 1 + 1 + 2~
- ~4 = 1 + 3~
- ~4 = 2 + 2~
- ~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