Як відомо, числа Фібоначчі визначаються наступним чином:
Знаючи a та b обчислити .
Складаються з декількох тестів. Кожен тест міститься в окремому рядку в якому задано два невід'ємних цілих числа a та b (0 ≤ a ≤ b ≤ 10^9
).
Для кожного тесту в окремому рядку виведіть S mod 10^9
, оскільки S може бути дуже великим.