#110. czq的模法数列

给定一个整数$p$，任意一个整数$a$，一定存在等式$a = kp + r$，其中$k$, $r$是整数，且 $0 \leq r < p$。

称$k$为$n$除以$p$的商，$r$为$n$除以$p$的余数。$r$就是$a$对$p$取模的结果，记做$a\bmod p$。

对于正整数$p$和正整数$a$，C++定义的%运算：$a \% p = a\bmod p$，%和$\mathrm{mod}$的优先级与乘除运算同级。

需要注意在$a$为负数时，C++的%运算的答案实际上为 $- (a\bmod p)$, 而不是我们期望的$a\bmod p$。一个通用的取模写法是(a%mod+mod)%mod。

模运算有着很好的性质：

$$\begin{aligned} (a+b) \bmod p &= (a\bmod p+b\bmod p) \bmod p\\ (a-b) \bmod p &= (a\bmod p-b\bmod p) \bmod p\\ (a*b) \bmod p &= (a\bmod p)*(b\bmod p) \bmod p\\ (a^b) \bmod p &= (a\bmod p)^b \bmod p \end{aligned}$$

在要求答案对$p$取模的时候，你应当利用模运算的性质，最好在每次运算之后进行取模，以避免答案超出变量所能表示的范围上限。同时，负数取模需要额外注意。

负数 $x$ 取模可以写成这样 ((x%p)+p)%p.

如果 WA 了，建议检查数据类型选用是否合适，以及是否及时取模。检查是否会出现溢出的情况。

如果 TLE 了，试试看能不能在累乘 $q$ 的时候顺手统计答案？