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