Problems
Числа Фибоначчи
Числа Фибоначчи
\textit{Числа Фибоначчи} - это последовательность целых чисел, заданная рекурентным соотношением:
\textbf{F_0 = 0}, \textbf{F_1 = 1}, \textbf{F_n = F_\{n-1\} + F_\{n-2\}}, \textbf{n} ≥ \textbf{2}.
Ваша задача - найти наибольший общий делитель двух чисел Фибоначчи.
\InputFile
Во входном файле два числа \textbf{i} и \textbf{j} (\textbf{1} ≤ \textbf{i}, \textbf{j} ≤ \textbf{10^6}) - номера чисел Фибоначчи.
\OutputFile
В выходной файл выведите остаток от деления наибольшего общего делителя чисел \textbf{F_i} и \textbf{F_j} на \textbf{10^9}.
Input example #1
5 10
Output example #1
5