题目描述

树老师爬楼梯，他每次可以选择走 1 级台阶，或者走 2 级台阶。给定楼梯的总级数 $N$，请你计算一共有多少种不同的走法可以走完这 $N$ 级台阶。

例如：楼梯一共有 3 级，共有 3 种走法：

1. 每次都走 1 级，分 3 次走完；
2. 第一次走 1 级，第二次走 2 级；
3. 第一次走 2 级，第二次走 1 级。

输入格式

一行，一个正整数 $N$，表示楼梯的级数。

输出格式

一行，一个整数，表示不同的走法总数。

样例

5

8

数据范围

$1 \le N \le 30$