Задачи
Числа Фибоначчи
Числа Фибоначчи
Как известно, последовательность Фибоначчи определяется следующим образом:
F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) для всех n > 1
Названа она в честь итальянского математика Леонардо Фибоначчи, известного также под именем Леонардо Пизанского.
По заданным n и m вычислить наибольший общий делитель чисел F(n) и F(m).
Входные данные
Каждая строка является отдельным тестом и содержит два целых числа n и m (1 ≤ n, m ≤ 1018
). Количество тестов не превышает 1000.
Выходные данные
Для каждого теста в отдельной строке вывести значение НОД(F(n), F(m)), вычисленное по модулю 108
.
Входные данные #1
2 3 1 1 100 200
Выходные данные #1
1 1 61915075