等比数列 \(a\)，\(a_i = q^i\)（\(i \ge 0\)）。
令 \(S_n = a_0 + a_1 + \dots + a_{n}\)。
给定正整数 \(M\)，我们要计算 \(S_n\) 除以 \(M\) 的余数。
注意到 \(S_{n} = q S_{n-1} + 1\)（\(i \ge 1\)）。用矩阵来表达，可以写成 \[ \begin{pmatrix} S_n \\ 1 \end{pmatrix} = \begin{pmatrix} q & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} S_{n-1} \\ 1 \end{pmatrix}. \]
于是得 \[ \begin{pmatrix} S_n \\ 1 \end{pmatrix} = \begin{pmatrix} q & 1 \\ 0 & 1 \end{pmatrix}^{n}\begin{pmatrix} 1 \\ 1 \end{pmatrix}. \]
这样计算的好处是不用做除法。
来源：arc050_c LCM 111 的题解。