爆炸的兔子

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

       小铁养了一只小白兔,一只成熟的兔子每天能产下一胎兔子。每只小白兔从出生起算第三天才会开始产下新兔子。 某人领养了一只小白兔,请问第N天以后,他将会得到多少只兔子。因为这品种的兔子繁殖能力太高,小铁的兔子窝也有限,超过一百万只兔子时,只会留下后六位 数量的兔子,其余的百万只兔子会被送出。

注意n的范围 每次都跑n次会超时 在输入之前处理出来

PS:留下后六位 即ans = ans%1000000(ans 为最终答案) 注意中间过程每一步都要取余!

Input

输入有多组数据。

每组数据一行,包含一个整数n (1≤n≤100000)。

Output

对应每一组输入,输出第n天小白有多少只小白兔。

Sample Input

1
2
3
4

Sample Output

1
2
3
5

Hint

Source

2015级《程序设计基础II》计科软件期末上机考试1 - by LeiQ