\(S_i\) は等比数列の和になります。しかし、等比数列の和の公式

\[1 + r + r^2 + \cdots + r^{n-1} = \frac{1 - r^n}{1 - r}\]

は、法 \(M\) が素数でない場合には mod 逆元をもたないことがあるためそのままでは使えません（公式解説にあるように \(\bmod \ M(r - 1)\) で考えるというような工夫をすることはできます）。

ここで、

\[\begin{pmatrix} r & 1 \\ 0 & 1 \end{pmatrix}^n = \begin{pmatrix}r^n & 1 + r + r^2 + \cdots + r^{n-1} \\ 0 & 1 \end{pmatrix}\]

が成り立ちます（証明は数学的帰納法でできます）。これを利用すると、行列累乗により項数 \(n\) の等比数列の和を \(O(\log n)\) で計算することができます。よってこの問題は \(O(K \log D_{\max})\) で解けました（\(D_{\max}\) は \(D_i\) たちの最大値）。

関連する問題：

• AtCoder Regular Contest 020 C - A mod B Problem（ほぼ同じです）
• AtCoder Beginner Contest 129 F - Takahashi’s Basics in Education and Learning（\(n + (n - 1)r + (n - 2)r^2 + \cdots + 2r^{n-2} + r^{n-1}\) のようないわゆる「等差×等比」の形の和の計算も似たような感じで行列累乗で求まります）