P1306 Fibonacci GCD

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)$.

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

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

- For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^9$. Translated by ChatGPT 5