【题目】

People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow:

Each player chooses two numbersand and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers.

You should write a program that calculates the result and is able to find out who won the game.

【题意】

T组测试样例，一个取余用的数M。输入一个N，表示有N组A和B。然后求，这些组的和的取余。

【题解】

对于刚入算法的人，也许是有点不知所措，这道题的做法就是快速幂。即利用的原理，还有就是快速幂的核心思想。便是反复平方，即，,不停的缩减指数的大小，因为是二进制移位的运算，所以时间复杂度为。反复平方是缩减指数的大小，那之前提到的则是用来缩减用来运算时的数的大小，以防在运算的过程中，超出精度的范围，从而无法进行计算。而目前取余的意义，就在于把一个很大的数变成一个在可以接受范围内浮动的数。

时间复杂度：

#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define lc (p<<1)
#define rc (p<<1|1)    
#define MID (tree[p].l+tree[p].r)>>1
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define STOP system("pause")
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }  
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=20+5;
int qpow(ll a,int k,int MOD){
    ll ans=1;
    while(k){
        if(k&1) ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        k>>=1; 
    }
    return ans;
}
int main(){
    int T; Sca(T);
    while(T--){
        int MOD; Sca(MOD);
        int n; Sca(n);
        int ans=0;
        For(i,1,n){
            int a,k; Sca2(a,k);
            ans=(ans+qpow(a,k,MOD))%MOD;
        } 
        Pri(ans);
    }
}