Табло в спортзале: n-е число Фибоначчи

В школьном спортзале повесили табло, которое на тренировках показывает «число дня». Тренер выбрал последовательность Фибоначчи.

Числа Фибоначчи начинаются так: 1, 1, а каждое следующее равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, …

Тренер вводит номер n, а табло должно показать n-е число Фибоначчи (первое и второе равны 1).

Важно: значения могут не помещаться в 32-битный тип, но помещаются в 64-битный (как на олимпиадах).

Формат ввода: Одно натуральное число n, записанное в одной строке.

Формат вывода: Выведите одно целое число — n-е число Фибоначчи.

Ограничения: 1 ≤ n ≤ 80.

Пример Ввод:

6

Вывод:

8