Числа Фибоначчи устроены следующим образом. Первое и второе равны единице. А каждое следующее - сумме двух предыдущих. То есть третье равно 2, четвертое - 3, пятое - 5, шестое - 8 и т.д.

По данному числу N напечатайте N-ое число Фибоначчи.

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

Вводится одно натуральное число N, не превышающее 40 (числа Фибоначчи при этом ограничении помещаются в тип Longint).

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

Выведите N-ое число Фибоначчи.

Пример ввода

3

Пример вывода

2