有一楼梯共 $n$ 级,如规定每次只能跨上一级或两级,要登上第 $n$ 级,共有多少种不同走法?

输入格式

一个整数 $n$。

输出格式

输出登上 $n$ 级台阶的方案数。

输入样例

4

输出样例

5

数据规模与约定

$1\le n\le40$