If N=10^18 "digits" then complexity can be too big.
Also I didn't quite understand the logic of mod M, if the test is 2 10 5: then correct answer is 0, if the test is 2 10 13, then correct answer is 3 {10, 11, 12}?

Thank you!
Your test case helped me getting an AC.

No. N=10^18 is correct

If use recurrence to calculating n = 1 then n = 2 then n = 3 etc then complexity too big

But there is shortcut to make exponential jumps in calculating (hint: matrix)