Опять числа Фибоначчи

Простая

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

Как известно, числа Фибоначчи определяются следующим образом:

Зная a и b вычислить .

Входные данные

Состоит их нескольких тестов. Каждый тест содержится в одной строке и содержит два неотрицательных целых числа a и b (0 ≤ a ≤ b ≤ 10^9).

Для каждого теста выведите в отдельной строке S mod 10^9, так как S может быть очень большим.

Ввод #1

Ответ #1

Отправки 594

Коэффициент принятия 18 %