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

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

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.

Приклади