Послідовність Фібоначчі визначається так:

$F [0] = 0, F [1] = 1, ..., F [n] = F [n-1] + F [n-2]$.

За даним числом n визначте n-е число Фібоначчі $F [n]$.

Формат введення

Вводиться натуральне число n.

Формат виведення

Виведіть відповідь до задачі.

Приклади

Тест 1
Вхідні дані:
6
Виведення програми:
8

Тест 2
Вхідні дані:
2
Виведення програми:
1

Тест 3
Вхідні дані:
3
Виведення програми:
3

Розв’язання

n = int(input())
afp = 0
bfn = 1
i = 1
fib = 1
while i < n:
    fib = afp + bfn
    afp = bfn
    bfn = fib
    i += 1
print(fib)