Последовательность Фибоначчи определяется так: φ0=0, φ1=1,..., φn=φn−1+φn−2.
По данному числу n определите n-е число Фибоначчи φn.
Входные данные
Вводится натуральное число n.
Выходные данные
Выведите ответ на задачу.
Примеры
входные данные
6
выходные данные
8