ABC293 - E - Geometric Progression
問題
$ a_k=\sum_{i=0}^{k}A^iとすると
$ a_{n+1} = Aa_n+1
これを行列で書くと
$ \begin{pmatrix} a_{n+1} & 1 \end{pmatrix}=\begin{pmatrix} a_n & 1 \end{pmatrix}\begin{pmatrix} A & 0 \\ 1 & 1\end{pmatrix}
よって
$ \begin{pmatrix} a_{X-1} & 1 \end{pmatrix}=\begin{pmatrix} a_0 & 1 \end{pmatrix}\begin{pmatrix} A & 0 \\ 1 & 1\end{pmatrix}^{X-1}
code: e.py
A, X, mod = map(int, input().split())
p = 1, 1
q = A, 0], [1, 1
B = matpow(q, X-1)
ans = matmul(p, B)