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

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

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

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

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

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