Let's first solve a simpler problem – when the sequence ~c~ is cyclic, i.e. when ~c_i = c_{i \bmod N}~, for ~i \ge 0~.

This simpler version is similar to Fibonacci sequence. Actually, for ~N = 1~ and ~c_0 = 1~, it is the Fibonacci sequence. To find the ~K^\text{th}~ number of these kinds of recursive sequences fast we should first write them in their matrix form. Matrix form of this sequence is:

$$\displaystyle \begin{pmatrix}F_i \\ F_{i-1}\end{pmatrix} = \begin{pmatrix}c_{i-1} & c_{i-2} \\ 1 & 0\end{pmatrix} \begin{pmatrix}F_{i-1} \\ F_{i-2}\end{pmatrix}$$

Expanding this, we can see that

$$\displaystyle \begin{pmatrix}F_K \\ F_{K-1}\end{pmatrix} = C_{K-1} C_{K-2} \dots C_2 C_1 \begin{pmatrix}F_1 \\ F_0\end{pmatrix}, \text{ where } C_i = \begin{pmatrix}c_i & c_{i-1} \\ 1 & 0\end{pmatrix}$$

How do we calculate this efficiently?

For relatively small ~K~, and we will take ~K < N~ for this case, we can do this just by multiplying all the matrices. For large ~K~ ~(K \ge N)~, we will take advantage of the fact that ~c~ is cyclic. Since ~c~ is cyclic with cycle of length ~N~, we know that ~C_{N-1} C_{N-2} \dots C_1 C_0 = C_{iN+(N-1)} C_{iN+(N-2)} \dots C_{iN+1} C_{iN}~, for ~i \ge 0~ (note that ~C_0 = \begin{pmatrix}c_0 & c_{N-1} \\ 1 & 0\end{pmatrix}~). Let's define this product of matrices as ~S = C_{N-1} C_{N-2} \dots C_1 C_0~.

Now, we can write a formula for ~F_K~ that can be calculated quickly:

$$\displaystyle \begin{pmatrix}F_K \\ F_{K-1}\end{pmatrix} = C_{a-1} C_{a-2} \dots C_1 C_0 S^b C_{N-1} C_{N-2} \dots C_2 C_1 \begin{pmatrix}F_1 \\ F_0\end{pmatrix},\text{ where } b = (K-N) \mathbin{\text{div}} N\text{ and } a = K \bmod N$$

We can calculate ~S^b~ in ~\mathcal{O}(\log b)~ steps using exponentiation by squaring, and then we can just multiply everything in the expression to get ~F_K~ quickly.

Let's get back to the full problem, when ~c~ is almost cyclic. In this case, we cannot just use ~S^b~ in the formula above, because some matrices in ~S^b~ may not respect the cyclic property. Instead of ~S^b~, we will have something like

$$\displaystyle S \cdot S \cdot \ldots \cdot S \cdot E_1 \cdot S \cdot S \cdot \ldots \cdot S \cdot E_2 \cdot \ldots = S^{t_1} \cdot E_1 \cdot S^{t_2} \cdot E_2 \cdot S^{t_3} \cdot \ldots$$

where ~E_i~ denotes the product of matrices of the cycle, with some matrices being different than the matrices of the original cycle. Also, ~i \le 2M~ since each of the ~M~ values of ~c~ are different than values of the original cycle appears in exactly two matrices, so at most ~2M~ of cycles are affected.

We can still calculate each ~S^{t_i}~ quickly, using exponentiation by squaring. Since there are at most ~2M~ of those, total complexity of this would be ~\mathcal{O}(M \log K)~.

Now we only need to calculate each ~E_i~. Naive way would be to just multiply all matrices of ~E_i~. Since the number of matrices is ~N~, this would be ~\mathcal{O}(NM)~ worst case, which is too slow. To quickly calculate ~E_i~, we will initially create a segment tree of matrices, with matrices of original cycle in the leaves. Internal nodes of the tree will represent the product of their children. This means that the root will represent the product of all matrices in the cycle. To calculate ~E_i~, we will just update our segment tree with those values that are different than the original values of the cycle. We will do this by updating the corresponding leaves of the tree, moving up to the root and updating the products in the internal nodes. After we're done updating the tree with all of the matrices that are different than matrices of the original cycle, we will just use the product in the root of the tree. Finally, we will update the tree back with matrices of the original cycle in order to reuse the segment tree for ~E_{i+1}~.

Since there are ~\mathcal{O}(N)~ nodes in the segment tree, the complexity of updating is ~\mathcal{O}(\log N)~. The total complexity is then ~\mathcal{O}(M \log N + M \log K)~. We should also mention that the constant factor is not very small, since we operate on matrices and not just integers.

Note that we need to find ~F_K \bmod P~ and ~P~ may not even be a prime number. However, this does not affect us since we only deal with operations of addition and multiplication throughout the whole procedure and we can just do them all modulo ~P~.