概要
公式解説より簡潔な気がする．
解法
すごろくの設定で説明します．状態数 $12NM$ の dp で解くことを考えます．
dp[i][j][k] は，次のような状態 $(i,j,k)$ にいたる出目の列の数え上げです．
- $0\leq i\leq NM$: $i$ 番目のマスについて
- $0\leq j\leq 5$：次に止まるマスが $i+j$（つまりサイコロによる移動が $j$ 残っている）
- $k=0,1$：特別なマスに既に止まっていない・止まった（ただし特別とは番号が $\text{mod } N$ で $C$ であること）
答えるべきは dp[NM][-][true] の総和です．
dp[i] から dp[i+1] への遷移は行列で書くことができます．
$(j,k)$ から $(j-1,k)$，$(0,k)$ から $(j,k)$ といった遷移があります．ただしマス $i+1$ が特別なマスのときには $(0,0)$ に向かう遷移は $(0,1)$ に向かう遷移に置き換えます．
結局，次のような問題になります：
$12\times 12$ 行列 $A,B$ が与えられる．ベクトル $v$ も与えられる．$(A^{N-C}BA^C)^Mv$ を求めよ．
$B$ は $(0,0)$ を $(0,1)$ に置き換える操作を表す行列です．サイコロの目の上限を $d$ として，これで $O(d^3\log NM)$ 時間の解法になります（高速な行列累乗を使えば $O(d^3)$ 時間）．
この計算が $C$ によらないことを利用すれば，より高速になります．計算すべきは
$A^{N-C}(BA^N)^MBA^Cv$ したがって $A^{N-C}XA^Cv$というようにかけて，$A,X$ は $C$ によらない行列です．$X$ はクエリに依らないので前計算できます．
$A^C$ をベクトルに作用させることは，例えば $A^{2^i}$ の形の行列を前計算しておけば，$O(d^2)$ 時間で行えます．行列積のベクトルへの作用を $XYv = (XY)v$ ではなく $XYv=X(Yv)$ と計算することで計算量が変わることに注意してください．
これで，前計算 $O(d^3\log NM)$ 時間，クエリごとに $O(d^2\log N)$ 時間になります．
他にも高速化の方法はいろいろあります．（$A$ の最小多項式を求めておき，$x^N \pmod f(x)$ の計算に帰着する方法．$x^{2^i}N \pmod{f(x)}$ ではなく，$x^{K^ij}\pmod{f(x)}$ を前計算する方法など．）
