Как известно, последовательность Фибоначчи определяется следующим образом:
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 ≤ 10^18
). Количество тестов не превышает 1000.
Для каждого теста в отдельной строке вывести значение НОД(F(n), F(m)), вычисленное по модулю 10^8
.