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

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

Output

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