N-е число Фибоначчи (Nth Fibonacci Number)

Условие:
Последовательность Фибоначчи задаётся так: F(0) = 0, F(1) = 1, а каждое следующее число равно сумме двух предыдущих: F(n) = F(n - 1) + F(n - 2) при n >= 2. Начало последовательности: 0, 1, 1, 2, 3, 5, 8, 13, ...

Напишите функцию, которая по номеру n (нумерация с 0) возвращает F(n). Хранить всю последовательность не требуется. Решение должно работать за O(n) по времени и использовать O(1) дополнительной памяти.

Входные данные:
n — целое неотрицательное число, номер числа Фибоначчи (нумерация с 0)

Выходные данные:
Целое число — значение F(n)

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

• 0 <= n <= 40 (результат помещается в 32-битный int)

Пример:

Вход: n = 0
Выход: 0

Вход: n = 1
Выход: 1

Вход: n = 3
Выход: 2

Вход: n = 10
Выход: 55