← 返回题目列表

AtCoder · math_and_algorithm_ab

029. 爬楼梯

中文机器翻译题面 查看原题

配点: 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