Биолог изучает упрощённую модель роста популяции кроликов. В этой модели число кроличьих пар в n-й момент времени описывается последовательностью Фибоначчи:

F(1) = 1, F(2) = 1, а для любого k > 2 выполняется F(k) = F(k-1) + F(k-2).

По заданному числу n определите, сколько кроличьих пар будет в n-й момент времени, то есть найдите F(n).

Гарантируется, что ответ помещается в 64-битный целочисленный тип long long.

Входные данные

В единственной строке дано целое число n — номер момента времени в модели роста популяции кроликов (1 <= n <= 90).

Выходные данные

Выведите одно целое число — количество кроличьих пар в n-й момент времени.

Ограничения

1 <= n <= 90

Примеры

Пример 1

Входные данные

1

Выходные данные

1

Пример 2

Входные данные

2

Выходные данные

1