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%