题意：一个长度为n的项链，m种颜色染色每个珠子。一些限制给出有些颜色珠子不能相邻。旋转后相同视为相同。有多少种不同的项链？
思路：这题有点综合，首先，我们对于每个n的因数i，都考虑这个因数i下的不变置换个数，然后乘以(n/i)的欧拉函数加到ans上面，然后再让ans乘以n在模p下的逆元。至于怎么求因数i下的不变置换个数，相信大家都做过没有限制的，至于有限制的，大家可以考虑一下这样：初始数组a[m][m]都为1，对于每个限制x,y,都令a[x][y]=a[y][x]=0,我们有一个数列：b1,b2,b3,b4...bm，那么对于每个i∈[1,m-1]，都有a[bi][bi+1]=1，这样想到了什么？就是矩阵乘法，对于刚刚的矩阵a我们让s=a^i，然后把每个a[i][i]加起来，这样就代表：每个i出发又回到i的方法数，这样就变成因数i下的不变置换个数了！
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
const int Mod=;
int a[][],b[][],c[][],s[][],n,m,K;
int read(){
char ch=getchar();
int t=,f=;
while (ch<''||ch>''){
if (ch=='-') f=-;
ch=getchar();
}
while (''<=ch&&ch<=''){
t=t*+ch-'';
ch=getchar();
}
return t*f;
}
void exgcd(int a,int b,int &x,int &y){
if (b==){
x=;
y=;
return;
}
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=(t-a/b*y);
}
int inv(int n){
int A,B,x,y;
A=n;B=Mod;
exgcd(A,B,x,y);
return (x+Mod)%Mod;
}
int euler(int n){
int res=n,a=n;
for (int i=;i*i<=n;i++)
if (a%i==){
res=res/i*(i-);
while (a%i==) a/=i;
}
if (a>) res=res/a*(a-);
return res%Mod;
}
void mult_matrix1(){
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
c[i][j]=;
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
for (int k=;k<=m;k++)
c[i][j]=(c[i][j]+s[i][k]*b[k][j])%Mod;
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
s[i][j]=c[i][j];
}
void mult_matrix2(){
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
c[i][j]=;
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
for (int k=;k<=m;k++)
c[i][j]=(c[i][j]+b[i][k]*b[k][j])%Mod;
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
b[i][j]=c[i][j];
}
int work(int x){
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
b[i][j]=a[i][j],s[i][j]=;
int ans=;
for (int i=;i<=m;i++)
s[i][i]=;
while (x){
if (x%) mult_matrix1();
mult_matrix2();
x/=;
}
for (int i=;i<=m;i++) ans=(ans+s[i][i])%Mod;
return ans;
}
int main(){
int T=read();
while (T--){
n=read();m=read();K=read();
for (int i=;i<=m;i++)
for (int j=;j<=m;j++)
a[i][j]=;
for (int i=;i<=K;i++){
int x=read(),y=read();
a[x][y]=a[y][x]=;
}
int ans=;
for (int i=;i*i<=n;i++)
if (n%i==){
ans=(ans+work(i)*euler(n/i))%Mod;
if (i*i!=n)
ans=(ans+work(n/i)*euler(i))%Mod;
}
ans=(ans*inv(n%Mod))%Mod;
printf("%d\n",ans);
}
}