Description

For the Fibonacci sequence:

$$f_i = \begin{cases} [i = 1] & i \leq 1 \\ f_{i - 1} + f_{i - 2} & i \gt 1 \end{cases}$$

Compute the greatest common divisor of $f_n$ and $f_m$, i.e., $\gcd(f_n, f_m)$.

Input Format

One line contains two positive integers $n$ and $m$.

Output Format

Output one integer, the greatest common divisor of $f_n$ and $f_m$. Print the answer modulo $10^8$.

4 7

1

Hint

• For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^9$.

Translated by ChatGPT 5