Вычислить n-й член последовательности Фибоначчи по модулю m
Последовательность Фибоначчи определяется так, что каждое новое число получается путём сложения двух предыдущих, причём первые два элемента равны 0 и 1:
Задано число n. Необходимо вычислить n-е число Фибоначчи по модулю m.
Так как нам нужен только результат по модулю m, значение n может быть очень большим.
Входные данные
В единственной строке находятся два целых числа n (0 ≤ n ≤ ) и m (1 ≤ m ≤ 50).
Выходные данные
Программа должна вывести результат вычисления .
Примеры
Вход | Выход |
|---|---|
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Пояснение
fib(0) = 0 ⇒ 0 mod 5 = 0
fib(1) = 1 ⇒ 1 mod 5 = 1
fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
Поскольку мы вычисляем числа Фибоначчи по модулю m, и каждое следующее число зависит от двух предыдущих, в каком-то месте значения начинают повторяться. Можно попробовать вывести много чисел по модулю m и заметить закономерность повторений.
Hint 2
Когда значения начинают повторяться, можно напрямую определить n-е число Фибоначчи, не вычисляя все числа подряд.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB