Числа Фібоначчі#5203
Числа Фібоначчі — це послідовність цілих чисел, яка задана рекурентним співвідношенням:
Ваша задача — знайти найбільший спільний дільник двох чисел Фібоначчі.
У вхідному файлі задано два числа та (1 \leq i,\ j \leq 10^6) — номери чисел Фібоначчі.
У вихідний файл виведіть залишок від ділення найбільшого спільного дільника чисел F_i та F_j на 10^9.
Приклад 1