在此之前需要知道两个知识点。
第一个是快速幂，在的时间内求出
的值。
这个算法事实上就是二进制的思想，将b看成是二进制的数来进行分割。
鉴于这个网上博客已经讲到烂了（跟欧几里得算法差不多简单），我就不再啰嗦了。
第二个是分步取余。对于只有加法，减法，乘法的运算中，满足如下性质：
(a+b)%m=((a%m)+(b%m))%m
(a-b)%m=((a%m)-(b%m))%m
(a*b)%m=((a%m)*(b%m))%m
由于乘方事实上就是多次乘法，所以也符合上面的性质。
也就是说，如果不包含除法的话，你可以在整个运算中的任意位置对数字进行取余，都不影响结果。
关于这个的证明如下：
首先假设a=a1+a2*c,b=b1+b2*c，其中a1和b1是a%c和b%c的结果
于是就有：
(a+b)%c=(a1+a2*c+b1+b2*c)%c=(a1+b1)%c+((a2+b2)*c)%c=(a1+b1)%c=((a%c)+(b%c))%c
(a-b)%c=(a1+a2*c-b1-b2*c)%c=(a1-b1)%c+((a2-b2)*c)%c=(a1-b1)%c=((a%c)-(b%c))%c
(a*b)%c=((a1+a2*c)*(b1+b2*c))%c=(a1*b1)%c+((a1*b2+a2*b1+a2*b2*c)*c)%c=(a1*b1)%c=((a%c)*(b%c))%c
证毕
事实上也很好理解，就是把a和b切割掉c的倍数的部分再进行运算。
而至于除法的，详见群文件，那里有长篇大论讲这个的。由于这里并不涉及就不详细展开了。
于是我们可以知道，在求问题中的式子的时候，我们可以在其快要溢出的时候先对m取余，防止它接下来会溢出，再进行接下去的操作。
那么代码中怎么处理呢？简单粗暴的方法是在每一次运算后都对m取余。（事实上我就是这样做的）
那么，知道这两个知识的话，问题就变得十分简单了，照着它说的做就行了。
#include <cstdio>
using namespace std;
typedef long long LL;
LL Pow(LL a,LL b,LL m)
{
LL ret=1;
while(b)
{
if(b&1)ret=(ret*a)%m;
a=(a*a)%m;
b>>=1;
}
return ret;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
LL m;
scanf("%lld",&m);
int n;
scanf("%d",&n);
LL ans=0;
while(n--)
{
LL a,b;
scanf("%lld%lld",&a,&b);
ans=(ans+Pow(a,b,m))%m;
}
printf("%d\n",ans);
}
return 0;
}
