Задачі
Числа Фібоначчі
Числа Фібоначчі
Як відомо, послідовність Фібоначчі визначається наступним чином:
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.
Приклад
Вхідні дані #1
2 3 1 1 100 200
Вихідні дані #1
1 1 61915075