做到了 ABC448E，感觉很精妙。
题目中有个部分是模意义下等比数列求和。那么来讲讲它的几种做法。
公式
直接套公式。
$$ \sum_{i=0}^n a^i = \frac{a^{n+1}-1}{a-1} $$然后用逆元。不讲。
如果等比数列不是从 1 开始的，提取首项为公因数即可。下面所有讨论都默认 1 为首项。
更好的方法
公式法需要逆元，在逆元不存在时就寄了。而恰好，448E 的模数不是质数。
我们有几种方法来处理这个情况
下文定义
$$ f(l, a) = \sum_{i = 0}^{l-1} a^i $$分治求和
洛谷已经有篇文章讲过这种手法了。我在场上推出来也受到了它的启发。
大概来说，我们将序列平均分为两部分。
$$ f(l, a) = \begin{cases} (1+a^{l/2})x, \; l \text{ is even}\\ x+a^{(l-1)/2}(ax+1), \; l \text{ is odd} \end{cases} $$其中 $x := f(\lfloor \frac{l}{2} \rfloor, a)$。
这样，做分治再套快速幂就可以以 2log 复杂度解决。不过这样不够优秀。
两种优化的分治
维护幂信息
注意到每层递归重算快速幂非常不优。我们在计算 $f(l, a)$ 时顺便维护 $a^l$，在计算完 $x$ 之后将 $a^{\lfloor \frac{l}{2} \rfloor}$ 平方就得到 $a^l$。
复杂度单 log。
奇偶分拆
从中部分开不是非常优秀。考虑类似 FFT 的方法，把奇数和偶数位置拆开算。
$$ f(l, a) = \begin{cases} (1+a)x, \; l \text{ is even}\\ a(1+a)x+1, \; l \text{ is odd} \end{cases} $$其中 $x := f(\lfloor \frac{l}{2} \rfloor, a^2)$。
同样复杂度 1log。
矩阵快速幂
注意到等比数列求和是一种常系数线性递推：
$$ f(l, a) = \begin{cases} 1, \; l=1\\ af(l-1,a)+1, \; \text{otherwise} \end{cases} $$于是自然可以矩阵快速幂维护。用 2 阶方阵作为转移矩阵。
$$ T := \begin{bmatrix} a & 1 \\ 0 & 1 \end{bmatrix} $$有
$$ T \begin{bmatrix} x \\ 1 \end{bmatrix} = \begin{bmatrix} ax+1 \\ 1 \end{bmatrix} $$于是：
$$ T^{l-1} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} f(l, a) \\ 1 \end{bmatrix} $$模数扩张
非常精妙的一种做法。
回想 448E 里我们用的另一个技巧。为了维护一个数除以另一个数下取整的值模 10007，我们推导出了这个式子：
$$ \lfloor \frac{a}{b} \rfloor \bmod p = \lfloor \frac{a \bmod pb}{b} \rfloor \bmod p $$回到最初的公式：
$$ f(l, a) = \frac{a^l-1}{a-1} $$那么：
$$ \frac{a^l-1}{a-1} \bmod p = \frac{(a^l-1) \bmod p(a-1)}{a-1} \bmod p $$只需要算一次快速幂即可。
注意特判 $a = 1$ 的情况（和普通公式法一样）。