Задачі
Числа Фібоначчі
Числа Фібоначчі
\textit{Числа Фібоначчі} - це послідовність цілих чисел, яка задана рекурентним співвідношенням:
\textbf{F_0 = 0}, \textbf{F_1 = 1}, \textbf{F_n = F_\{n-1\} + F_\{n-2\}}, \textbf{n} ≥ \textbf{2}.
Ваша задача - знайти найбільший спільний дільник двох чисел Фібоначчі.
\InputFile
У вхідному файлі два числа \textbf{i} та \textbf{j} (\textbf{1} ≤ \textbf{i}, \textbf{j} ≤ \textbf{10^6}) - номери чисел Фібоначчі.
\OutputFile
У вихідний файл виведіть залишок від ділення найбільшого спільного дільника чисел \textbf{F_i} та \textbf{F_j} на \textbf{10^9}.
Вхідні дані #1
5 10
Вихідні дані #1
5