Problem B: 冬冬爬楼梯

Memory Limit:128 MB Time Limit:5.000 S
Judge Style:Text Compare Creator:
Submit:380 Solved:67

Description

冬冬爬楼梯,一步可以1级,也可以爬2级、3级。冬冬很可爱,每到一处楼梯处,他都想知道直完这个楼梯有多少种走法。但由于有的时候楼梯级数太多,可能是个天文数字,很显然,对于还处于小学5年级的冬冬是不太现实的。聪明的你,能帮冬冬实现这个愿望吗?

Input

多笔测资,每笔测资一行:整数n (1<=n<=3000)

Output

对第笔测资,输出一个整数,为n级楼梯冬冬走完的方法数。

Sample Input Copy

1
2
3

Sample Output Copy

1
2
4

HINT

递推