超级台阶

题目描述

有一个楼梯共m级，刚开始你在第一级，若每次只能向上走一级或者两级，要走上m级，共有几种走法？

注：从一级到一级共有0种走法。

输入说明

输入数据每行包含一个整数m,表示楼梯的级数

输出说明

对于每个测试样例，输出不同的走法的数量。

样例

输入

2
3
30

输出

1
2
832040