Fibonaççi ədədi

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ş verilənləri

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ış verilənləri

Çı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.

Nümunələr