Ограничение по времени: 1.000 секунд
Ограничение по памяти: 100.000 мегабайт
На вход подается одно целое число N (1 ≤ N ≤ 109). Выведите N-ое число Фибоначчи.
Т.к. ответ может быть очень большим, то выведите его по модулю 108
| input | output |
|---|---|
1 |
1 |
38 |
39088169 |