フィボナッチ数列

フィボナッチ数列の第 $n$ 項の値を出力するプログラムを作成してください。ここではフィボナッチ数列を以下の再帰的な式で定義します：

\begin{equation*} fib(n)= \left \{ \begin{array}{ll} 1　 & (n = 0) \\ 1　 & (n = 1) \\ fib(n - 1) + fib(n - 2) & \\ \end{array} \right. \end{equation*}

入力

１つの整数 $n$ が与えられます。

出力

フィボナッチ数列の第 $n$ 項の値を出力してください。

制約

• $0 \leq n \leq 44$

入力例 1

3

出力例 1

3

---