Задача источник: Даны целые числа 1≤n≤10^18 и 2≤m≤10^5, необходимо найти остаток от деления n-го числа Фибоначчи на m.

Так как 5 последних цифр в числах последовательности Фибоначчи повторяются с периодичностью 150000 членов. То достаточно просчитать 300000 чисел Фибоначчи по модулю 10^6 например и потом получать ответ sequence[n % 150000 + 150000] % m. Я вообще правильно рассуждаю? Что-то мне подсказывает что я не прав.