問題文

太郎君は N 段の階段を上ろうとしています。彼は一歩で 1 段か 2 段上ることができます。

0 段目から出発し、N 段目にたどり着くまでの移動方法が何通りあるかを計算してください。

制約

• 1 \leq N \leq 45
• 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