階段

あなたは n 段の階段を登ろうとしています。各ステップで、一度に2段進むか、1段ずつ進むかを選択できます。このとき、階段を登る方法は全部で何通りあるでしょうか？

入力

入力として、整数 n（1 ≤ n ≤ 45）が1つ与えられます。

出力

出力には、階段を登る方法の総数を表示してください。

例

説明

1. 2段の階段の場合 → (1) 1段 + 1段、(2) 2段

2. 3段の階段の場合 → (1) 1段 + 1段 + 1段、(2) 1段 + 2段、(3) 2段 + 1段