Числа Фибоначчи

Как известно, последовательность Фибоначчи определяется следующим образом:

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.

Примеры