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