Как известно, последовательность Фибоначчи определяется следующим образом:
\(F(0) = 0,\ F(1) = 1,\ F(n) = F(n – 1) + F(n – 2)\), для всех \(n > 1\).
Названа она в честь итальянского математика Леонардо Фибоначчи, известного также под именем Леонардо Пизанского.
Входные данные
Строка содержит целое число n
(\(1 <= n <= 10^{18}\)).
Выходные данные
Вывести значение F(n)
, вычисленное по модулю \(10^8\).
Вставьте в программу недостающий фрагмент кода.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
30 |
832040 |