Числа Фібоначчі

Числа Фібоначчі - це послідовність цілих чисел, яка задана рекурентним співвідношенням:

F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}, n ≥ 2.

Ваша задача - знайти найбільший спільний дільник двох чисел Фібоначчі.

Вхідні дані

У вхідному файлі два числа i та j (1 ≤ i, j ≤ 10^6) - номери чисел Фібоначчі.

Вихідні дані

У вихідний файл виведіть залишок від ділення найбільшого спільного дільника чисел F_i та F_j на 10^9.

Приклади