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

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

Вхідні дані

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

Вихідні дані

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