题目描述

洛谷大厦门口的楼梯共有 $n$ 个台阶。扶苏要从最下面走到最上面。

扶苏一步可以向上走 $1$ 个台阶或 $2$ 个台阶。特别地，她不能连续两次都向上走 $2$ 个台阶。

她想知道走到第 $n$ 级台阶一共有多少种方案。

输入格式

输入只有一行一个整数 $n$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1

样例输出 #1

1

样例 #2

样例输入 #2

2

样例输出 #2

2

样例 #3

样例输入 #3

3

样例输出 #3

3

提示

样例 3 解释

有如下三种方案：

• 共走三步，每步走一个台阶；
• 共走两步，第一步走两个台阶，第二步走一个台阶；
• 共走两步，第一步走一个台阶，第二步走两个台阶。

数据规模与约定

• 对 $50\%$ 的测试点，$n \leq 5$。
• 对 $80\%$ 的测试点，$n \leq 20$。
• 对 $100\%$ 的测试点，$1 \leq n \leq 60$。