Fibonacci Numbers#5203
Sign in

Fibonacci Numbers

1 second
64 megabytes
Medium

Fibonacci numbers is a sequence of numbers defined by the recurrence relation:

F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1} + F_{n-2},\quad n \ge 2.

Your task is to find the greatest common divisor of two Fibonacci numbers.

Input

Two numbers and (1 \leq i, j \leq 10^6) — the indices of the Fibonacci numbers.

Output

Print the remainder of the greatest common divisor of the numbers F_i and F_j when divided by 10^9.

Examples

Example 1

Loading
Loading