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

Проста

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

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

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

Вхідні дані

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

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

Вхідні дані #1

Відповідь #1

Відправки 594

Коефіцієнт прийняття 18%