配点: 1000 点
問題文
太郎君是 N 我正在尝试爬一段楼梯。他迈出了一步 1 丹卡 2 你可以上楼梯。
0 从步骤1开始,N 计算到达该步骤的方式有多少种。
制約
- 1 \leq N \leq 45
- N 是一个整数
入力
输入是按以下格式从标准输入给出的。
N
出力
请打印答案。 到达
入力例 1
4
出力例 1
5
0 从第一行开始 4 如何进入下一步如下。 5 有一条街。 转至
- 0 段目 → 1 段目 → 2 段目 → 3 段目 → 4 段目
- 0 段目 → 1 段目 → 2 段目 → 4 段目
- 0 段目 → 1 段目 → 3 段目 → 4 段目
- 0 段目 → 2 段目 → 3 段目 → 4 段目
- 0 段目 → 2 段目 → 4 段目
因此,
输出5 。
入力例 2
45
出力例 2
1836311903