描述

成长的其中一个标志就是步子迈得越来越大。老师观察同学们上楼梯，就发现了能证明这个观点的例子。

蛋壳班的同学每次只能上一个台阶； 雏鸟班的同学每次可以上一个或者两个台阶； 鹦鹉班的同学每次可以上一个、两个或者三个台阶；

对于蛋壳班的同学来说，上五级台阶，只有1种走法：

• (1-1-1-1-1)

但对于雏鸟班的同学来说，上五级台阶，可以有8种走法：

• (1-1-1-1-1)
• (1-1-1-2)
• (1-1-2-1)
• (1-2-2)
• (1-2-1-1)
• (2-1-1-1)
• (2-1-2)
• (2-2-1)

是不是说明了，能力越大，选择就越多呢？

现在需要你帮忙解答一下，雏鸟班的同学走$N$级台阶，能有多少种方法？

输入输出格式

输入

一个正整数$N$，表示共有多少级台阶。 （$1≤N≤82$)

输出

一个正整数，表示总共的走法。

样例

5

8