eolymp
Задачі

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

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

Як відомо, послідовність Фібоначчі визначається наступним чином:

F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2) (для усіх n > 1).

Названо її на честь італійського математика Леонардо Фібоначчі, відомого також під іменем Леонардо Пізанського.

За заданими n та m обчислити найбільший спільний дільник чисел F(n) та F(m).

Вхідні дані

Кожний рядок є окремим тестом та містить два цілих числа n та m (1n, m1018). Кількість тестів не перевищує 1000.

Вихідні дані

Для кожного тесту в окремому рядку вивести значення НСД(F(n),F(m)), обчислене за модулем 108.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
2 3
1 1
100 200
Вихідні дані #1
1
1
61915075