eolymp
bolt
Try our new interface for solving problems
Problems

Fibonacci numbers

Fibonacci numbers

Time limit 1 second
Memory limit 128 MiB

As is known, the Fibonacci sequence is defined as:

F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) for all n > 1

It was named after the Italian mathematician Leonardo Fibonacci, also known as Leonardo of Pisa.

Given the values of n and m, find the greatest common divisor of F(n) and F(m).

Input data

Each line is a separate test case that contains two integers n and m (1n, m10^18). The number of test cases does not exceed 1000.

Output data

For each test case print in a separate line the value of GCD(F(n),F(m)), taken by modulo 10^8.

Examples

Input example #1
2 3
1 1
100 200
Output example #1
1
1
61915075