Fibonacci Problem Again

As we know, the Fibonacci numbers are defined as follows::

Given two numbers a and b, calculate .

Input

Consists of several test cases. Each test case is a separate line with two non-negative integers a and b (0 ≤ a ≤ b ≤ 10^9).

Output

For each test case output S mod 10^9, since S may be quite large.

Examples