光速幂板子

光速幂（矩阵光速幂类似）

时间复杂度O（T+sqrt(m)）(T是询问次数，m是模数大小)

$$\begin{gathered} s=sqrt(p)p是模数大小 \\ {a}^x\equiv a^{\frac{x}{s}\ast s+x\%s}modp \end{gathered}$$

// 代码没有验证过正确性，大致是这个样子
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int sqrtm=sqrt(mod);
int f1[sqrtm+5],f2[sqrtm+5];
int main()
{
   
	f1[0]=f2[0]=1;
	for(int i=1;i<=sqrtm;i++)f1[i]=1ll*f1[i-1]*a%mod;
	for(int i=1;i<=sqrtm;i++)f2[i]=1ll*f2[i-1]*f1[sqrtm]%mod;
	//求a^q次
	int res=1ll*f2[q/sqrtm]*f1[q%sqrtm]%mod;
	
}