Числа Фибоначчи - это последовательность целых чисел, заданная рекурентным соотношением:
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.