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