超级楼梯

题目描述

小 Z 要爬一段有 n 级台阶的楼梯。

他每次可以爬：

• 1 级；
• 2 级。

请问他爬到第 n 级台阶一共有多少种不同的方法？

由于答案可能非常大，请输出完整答案，不能取模。

输入格式

一行一个整数 n。

输出格式

输出一个整数，表示方案数。

样例输入 #1

3

样例输出 #1

3

样例输入 #2

5

样例输出 #2

8

数据范围

• $1 \le n \le 5000$