题目描述

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶或2阶。输入楼梯的级数，求有小孩有多少种不同的走楼梯方式。

输入格式

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

输出格式

不同的楼梯走法数

样例

输入样例 1

5

输出样例 1

8

输入样例 2

3

输出样例 2

3

输入样例 3

8

输出样例 3

34

输入样例 4

15

输出样例 4

987