Помогите решить задачу

Числа Фибоначчи это последовательность целых чисел, заданная рекуррентным соотношением: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2, n ≥ 2.
Ваша задача найти наибольший общий делитель двух чисел Фибоначчи.
Формат входного файла
Во входном файле два числа i и j (1 ≤ i, j ≤ 106) номера чисел Фибоначчи
Формат выходного файла
В выходной файл выведите остаток от деления наибольшего общего делителя чисел Fi и Fj на 109.
Примеры