Problem D: 整数拆分

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：176 Solved：41

Description

 一个整数总可以拆分为若干自然数的和，例如： 4 = 4，4 = 1 + 3， 4 = 2 + 2, 4 = 2 + 1 + 1, 4 = 1 + 1 + 1 + 1，五种不同的拆法。

 用 f(n)表示n的不同拆分的种数，要求编写程序，读入n(不超过1000000)，输出f(n)%1000000。



示例1：

       输⼊: 5                       

       输出: 7
      解释: 有 5， 1 + 4,  2 + 3，1 + 2 + 2, 1 + 1 + 1 + 2,  3 + 1 + 1， 1 + 1 + 1 + 1 + 1 + 1。

Input

输入一个整数n。

Output

输出f(n)%1000000。

Sample Input Copy 

5

Sample Output Copy 

7

HINT

输入整数最大不超过20000。