Dynamic Programming - Fibonacci Number

Time Limit : 1 sec, Memory Limit : 65536 KB

フィボナッチ数列

フィボナッチ数列の第 $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*}

入力

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

出力

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

制約

  • $0 \leq n \leq 44$

入力例 1

3

出力例 1

3

Note

      解説