Problems
Fibonacci numbers
Fibonacci numbers
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 (1 ≤ n, m ≤ 10^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