Can anybody help?

Easy solution without optimization efforts.
Use Matrix A=
[0   1  0  0  0  0]
[0   0  1  0  0  0]
[0   0  0  0  1  0]
[0   0  0  0  0  1]
[c1 c2 c3 c4 c5 c6]
Answer=[[A^(X-N)]*K][N]
Thus we must calculate pow A^(X-N)
Use famous O(lg) pow in groop of matrix
__int64 in inner calculations and int (rez)%Y as result

My such solution ran for 2.9 seconds with 3 for TL. So it's still not enogh for stable solution.

I had to differentiate between M^2 and M*A matrix multiplications (the latter can be implemeted via int, +, - and >=), then it ran for 1.5 sec :)

My such realisation works in 0.609.

This time even without optimizations on +- for fast modulus, and not using fact that matrix is sparse in those cases (so multiplication can be done at O(N^2)) - it's 0.078 sec. With these optimizations - 0.046 sec.

Edited by author 17.08.2022 11:56