在此之前需要知道兩個知識點。

第一個是快速冪，在的時間內(nèi)求出的值。
這個算法事實上就是二進制的思想，將b看成是二進制的數(shù)來進行分割。
鑒于這個網(wǎng)上博客已經(jīng)講到爛了（跟歐幾里得算法差不多簡單），我就不再啰嗦了。

第二個是分步取余。對于只有加法，減法，乘法的運算中，滿足如下性質(zhì)：

(a+b)%m=((a%m)+(b%m))%m
(a-b)%m=((a%m)-(b%m))%m
(a*b)%m=((a%m)*(b%m))%m

由于乘方事實上就是多次乘法，所以也符合上面的性質(zhì)。
也就是說，如果不包含除法的話，你可以在整個運算中的任意位置對數(shù)字進行取余，都不影響結(jié)果。

關(guān)于這個的證明如下：

首先假設(shè)a=a1+a2*c,b=b1+b2*c，其中a1和b1是a%c和b%c的結(jié)果
于是就有：
(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的倍數(shù)的部分再進行運算。

而至于除法的，詳見群文件，那里有長篇大論講這個的。由于這里并不涉及就不詳細展開了。

于是我們可以知道，在求問題中的式子的時候，我們可以在其快要溢出的時候先對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;
}