A. Числа Фибоначчи

Числа Фибоначчи заданы так: $f_1 = f_2 = 1$, а при $n > 2$ выполнено $f_n = f_{n-1} + f_{n-2}$.

Выведите $f_n$. Считать рекурсией «в лоб» нельзя: она пересчитывает одни и те же значения снова и снова, и уже на четвёртом десятке это становится заметно.

Одна строка содержит число $n$ ($1 \le n \le 90$).

Одно число — $f_n$. При $n = 90$ ответ близок к пределу 64-битного типа, но в него помещается.