Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

KTUAN - Phân tích số

no tags 

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274496/problem/X

Hãy đếm số cách phân tích số N ( N<=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.

Example

Input:
4

Output:
5

Added by:VOJ problem setters
Date:2007-10-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6
Resource:Được add lên bởi Khúc Anh Tuấn