Sum of Fibonacci Numbers

Time limit2sMemory limit128 MB

Summary
Compute the sum of Fibonacci numbers between two indices up to 9x10^18, modulo 1e9, requiring matrix exponentiation with modular arithmetic.
Level

Hard8 of 10

Topics
Math, Matrix, Number theory
Solved
No attempts yet

Problem

The Fibonacci sequence is defined by F_1 = 1 and F_2 = 1. For n >= 3, F_n is the sum of the previous two terms. Therefore F_3 = 2 and F_4 = 3.

Given integers a and b, compute F_a + F_(a+1) + ... + F_b. Since the sum can be very large, output only its remainder modulo 1,000,000,000.

Input

The first line contains two integers a and b separated by a space.

Output

Print the requested sum modulo 1,000,000,000 on the first line.

Constraints

  • 1 <= a <= b <= 9,000,000,000,000,000,000

Examples2

  1. Example 1

    Input
    4 10
    Expected output
    139

  2. Example 2

    Input
    2 2
    Expected output
    1