Problem1379--XP的楼梯

1379: XP的楼梯

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

XP是个淘气的孩子,他最近迷上了跳楼梯。他可以一次跳一级,也可以一次跳两级,他居然还能够一次跳三级楼梯(危险动作,请勿模仿)。某次,XP在跳完楼梯后突然想到一个问题,如果有n级楼梯,他从第一级开始往上跳,一直跳到第n级共有多少种不同的方案?你能帮他解决这个问题吗?当然,如果只有一级楼梯,很明显他只有一种选择。

Input

单组输入数据 n (0<n<30)

Output

输出一行结果

Sample Input Copy

29

Sample Output Copy

15902591

Source/Category