Числа Фибоначчи, обычно обозначаемые как, F(n) образуют последовательность, называемую последовательностью Фибоначчи, в которой каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1

F(n) = F(n - 1) + F(n - 2), for n > 1.

Пример 1:

Вход: n = 2

Выход: 1

Пояснение: F(2) = F(1) + F(0) = 1 + 0 = 1.

Пример 2:

Вход: n = 3

Выход: 2

Пояснение: F(3) = F(2) + F(1) = 1 + 1 = 2.

Пример 3:

Вход: n = 4

Выход: 3

Пояснение: F(4) = F(3) + F(2) = 2 + 1 = 3.

Ограничения:

0 <= n <= 30