eolymp
Задачі

Знову числа Фібоначчі

Знову числа Фібоначчі

Як відомо, числа Фібоначчі визначаються наступним чином:

prb1250

Знаючи a та b обчислити prb1250-1.

Вхідні дані

Складаються з декількох тестів. Кожен тест міститься в окремому рядку в якому задано два невід'ємних цілих числа a та b (0ab109).

Вихідні дані

Для кожного тесту в окремому рядку виведіть S mod 109, оскільки S може бути дуже великим.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
1 1
3 5
10 1000
Вихідні дані #1
1
16
496035733