注意一下你的复杂度是否达到了三只 $\log$。

如果你的复杂度到达了三只 $\log$，可以采取：

$c^{x}\operatorname{mod}m=c^{\lfloor x/S\rfloor}\cdot c^{x\operatorname{mod} S}\operatorname{mod} m,S=10^4$

的形式，对 $\mathcal{O}(\log)$ 个模数在 $\mathcal{O}(S\log p)$ 的时间内预处理出幂次，以此时间复杂度降为两只 $\log$。