Ciąg Fibonacciego

Limit czasu: 0.5s | Limit pamięci: 32MB

Ciąg Fibonacciego zadany jest wzorem rekurencyjnym: $$ a_n = \begin{cases} 1 & \text{dla } 1 \leq n \leq 2 \\ a_{n-1} + a_{n-2} & \text{dla } n \geq 3 \end{cases} $$

Napisz program, który dla zadanego $n$ obliczy $a_n$.

Wejście

Pierwszy i jedyny wiersz wejścia zawiera liczbę naturalną $n$.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara liczbę $a_n$

Ograniczenia

• $1\leq n \leq 1000$

Przykłady

Wejście 1

2

Wyjście 1

1

Wejście 2

400

Wyjście 2

176023680645013966468226945392411250770384383304492191886725992896575345044216019675