公式解説の内容を前提とします。目標は、\(1\) を \(n\) 個並べたレピュニットを \(R_n\) とするとき、\(R_n\) を \(10007 \times M\) で割った余りを高速に計算することです。

以降、法を \(10007 \times M\) とします。ここで、\(R_{n+1} = 10 \times R_n + 1\) が成立します。

よって、\(\begin{pmatrix}R_{n+1} \\ 1\end{pmatrix} =\begin{pmatrix}10 & 1 \\0 & 1\end{pmatrix}\begin{pmatrix}R_{n} \\ 1\end{pmatrix} \) が成立します。

後は、\(\begin{pmatrix}10 & 1 \\0 & 1\end{pmatrix}^X\) を求めればよく、これは繰り返し二乗法の要領で \(O(\log X)\) で求めることができます。よって、この問題を解くことができました。