当前没有测试数据。

题目描述

小符同学站在彩虹桥的起点（第0个彩虹石），需要到达终点（第n个彩虹石）。他每次可以跨1个或2个彩虹石。小符同学想知道，从起点到终点，有多少种不同的走法？请用递归的方法解决。

当只剩1个彩虹石（n=1）时，他只能跨1步，所以只有1种走法

当只剩2个彩虹石（n=2）时，他有两种选择：跨1步再跨1步，或者直接跨2步，所以有2种走法

输入格式

一个整数 $n$，满足 $1 \leq n \leq 30$。

输出格式

一个整数，表示小符同学过彩虹桥的不同路径数。

样例

3

3

5

8