Ginny’s birthday is coming soon. Harry Potter is preparing a birthday present for his new girlfriend. The present is a magic bracelet which consists of n magic beads. The are m kinds of different magic beads. Each kind of beads has its unique characteristic. Stringing many beads together a beautiful circular magic bracelet will be made. As Harry Potter’s friend Hermione has pointed out, beads of certain pairs of kinds will interact with each other and explode, Harry Potter must be very careful to make sure that beads of these pairs are not stringed next to each other.

There infinite beads of each kind. How many different bracelets can Harry make if repetitions produced by rotation around the center of the bracelet are neglected? Find the answer taken modulo 9973.

The first line of the input contains the number of test cases.

Each test cases starts with a line containing three integers n (1 ≤ n ≤ 10⁹, gcd(n, 9973) = 1), m (1 ≤ m ≤ 10), k (1 ≤ k ≤ m(m − 1) ⁄ 2). The next k lines each contain two integers a and b (1 ≤ a, b ≤ m), indicating beads of kind a cannot be stringed to beads of kind b.

Output the answer of each test case on a separate line.

  1 #include<cstdio>    2 #include<cstring>    3 #include<algorithm>    4 using namespace std;    5 const int MOD = 9973;    6 typedef long long LL;    7 int m,k,n,a,b,T,mat[10][10],tmp[10][10],tp[10][10],prime[36000],is[36000];    8 void getprime()    9 {   10     int cnt=0;   11     for(int i=2;i<36000;i++)   12     {   13         if(!is[i])   14         {   15             prime[cnt++]=i;   16             for(int j=i;j<36000;j+=i)   17                 is[j]=1;   18         }   19     }   20 }   21 int pow(int x,int y)   22 {   23     x=x%MOD;   24     int t=1;   25     while(y)   26     {   27         if(y&1)t=(t*x)%MOD;   28         x=(x*x)%MOD;   29         y>>=1;   30     }   31     return t;   32 }   33 void mul(int a[10][10],int b[10][10],int m)   34 {   35     int c[10][10];   36     memset(c,0,sizeof(c));   37     for(int i=0;i<m;i++)   38         for(int j=0;j<m;j++)   39             for(int k=0;k<m;k++)   40                 c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;   41     for(int i=0;i<m;i++)   42         for(int j=0;j<m;j++)   43             a[i][j]=c[i][j];   44 }   45 int get(int x)   46 {   47     memset(tmp,0,sizeof(tmp));   48     for(int i=0;i<m;i++)   49         for(int j=0;j<m;j++)   50             tp[i][j]=mat[i][j];   51     for(int i=0;i<m;i++)tmp[i][i]=1;   52     while(x)           53     {   54         if(x&1)   55             mul(tmp,tp,m);   56         mul(tp,tp,m);   57         x>>=1;   58     }   59     int ans=0;   60     for(int i=0;i<m;i++)   61         ans=(ans+tmp[i][i])%MOD;   62     return ans;   63 }   64 int eular(int x)   65 {   66     if(x==1)return 1;   67     int rep=x;   68     for(int i=0;prime[i]*prime[i]<=x;i++)   69     {   70         if(x%prime[i]==0)   71         {   72             rep-=rep/prime[i];   73             x/=prime[i];   74         }   75         while(x%prime[i]==0)x/=prime[i];   76         if(x==1)break;   77     }   78     if(x!=1)   79         rep-=rep/x;   80     return rep%MOD;   81 }   82 int inv(int n)   83 {   84     return pow(n,MOD-2)%MOD;   85 }   86 int main()   87 {   88     scanf("%d",&T);   89     getprime();   90     while(T--)   91     {   92         scanf("%d%d%d",&n,&m,&k);   93         for(int i=0;i<m;i++)   94             for(int j=0;j<m;j++)   95                 mat[i][j]=1;   96         for(int i=0;i<k;i++)   97         {   98             scanf("%d%d",&a,&b);   99             a--;  100             b--;  101             mat[a][b]=mat[b][a]=0;  102         }  103         int ans=0;  104         int i;  105         for(i=1;i*i<n;i++)  106         {  107             if(n%i==0)  108             {  109                 ans=(ans+(get(i)*eular(n/i))%MOD)%MOD;  110                 ans=(ans+(get(n/i)*eular(i))%MOD)%MOD;  111             }  112         }  113         if(i*i==n)  114             ans=(ans+(get(i)*eular(n/i))%MOD)%MOD;  115         printf("%d\n",(ans*inv(n))%MOD);  116     }  117     return 0;  118 }