# Fibonacci Problem Again

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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

Input #1

Answer #1

Submissions 592

Acceptance rate 18%