Problem1210--爬楼梯游戏

1210: 爬楼梯游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1002  Solved: 238
[Submit] [Status] [Web Board] [Creator:]

Description

现有n阶楼梯,PIPI从第一阶走到第n阶,每次可以跨一阶或者两阶,问PIPI从第一阶走到第n阶总共有多少种可能。为了防止结果过大,需要让结果对p取模。
ps: p = 1e9+7.

Input

输入包含多组测试用例。
每组样例第一行输入楼梯的阶数n。(1<=n<=1000000)

Output

对于每组样例,输出方案数。最后结果对109+7取模。

Sample Input

1
2
3

Sample Output

1
2
3