Fibonaççi ədədi - rekurent münasibətlə verilmiş tam ədədlər ardıcıllığıdır:
F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}, n ≥ 2.
Sizin vəzifəniz - İki Fibonaççi ədədinin ən böyük ortaq bölənini tapmaqdan ibarətdir.
Giriş faylında Fibonaççi ədədlərinin nömrələrini ifadə edən iki i və j (1 ≤ i, j ≤ 10^6) ədədləri verilir.
Çıxış faylına F_i və F_j ədədlərinin ən böyük ortaq böləninin 10^9- bölünməsindən alınan qalığı verin.