题目描述

某个上班族正在上楼梯，楼梯有n阶台阶，他一次可以上1阶、2阶、3阶。输入楼梯的级数，求有多少种不同的上楼方式。

输入格式

一个整数n代表楼梯总级数(1≤n≤30)

输出格式

不同的楼梯走法数

样例

输入样例 1

5

输出样例 1

13

输入样例 2

3

输出样例 2

4

输入样例 3

8

输出样例 3

81

输入样例 4

20

输出样例 4

121415