死变态的跳台阶

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

  小银今天准备去爬山,山上的台阶太难爬了,但是小银最近得到了一个新的技能,他每一次可以向上跳一个台阶,也可以两个台阶,也可以三,四,五.......n个台阶。现在已知台阶的数量为n,小银想知道他有多少种方法跳上山顶。

Input

多组输入,每组输入一个整数n(1 <= n <= 10^5)。

Output

输出跳上n个台阶总共的跳法,由于结果可能非常的大,结果对1000000007取余。(%1000000007)

Sample Input

1
2

Sample Output

1
2

Hint

Source

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