# [POJ 2888]Magic Bracelet[Polya(Burnside) 置换 矩阵]

$Description$

$\left(1\le n\le 1{0}^{9},gcd\left(n,9973\right)=1\right),m\left(1\le m\le 10\right),k\left(1\le k\le m\left(m-1\right)/2\right)$
$Solution$

$burnside$定理解决(发现大家标题都打得polya,于是也这么打标题了)

$f\left[i\right]\left[j\right]$表示从 $i$出发，走 $n$步，最后结束在 $j$有多少种走法。

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年07月04日 星期四 14时25分13秒 *******************************/
#include <cstdio>
#include <fstream>
#include <cstring>
using namespace std;
const int maxn = 25;
const int mod = 9973;
//{{{cin 读入优化
struct IO{
template<typename T>
IO & operator>>(T&res){
res=0;
bool flag=false;
char ch;
while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
if (flag)	 res=~res+1;
return *this;
}
}cin;
//}}}
int t,n,m,k,x,y,ni,ans;
//{{{Matrix
struct Matrix{
int rec[maxn][maxn];
Matrix(){	memset(rec,0,sizeof(rec));}
Matrix operator = (const Matrix &y){
for (int i=1;i<=m;++i)
for (int j=1;j<=m;++j)
rec[i][j]=y.rec[i][j];
return *this;
}
friend Matrix operator * (const Matrix &a,const Matrix &b){
Matrix t;
for (int i=1;i<=m;++i)
for (int j=1;j<=m;++j)
for (int k=1;k<=m;++k)
t.rec[i][j]=(t.rec[i][j]+a.rec[i][k]*b.rec[k][j])%mod;
return t;
}
Matrix operator ^ (int b){
Matrix s,a;
a=*this;
for (int i=1;i<=m;++i)	s.rec[i][i]=1;
for (;b;b>>=1,a=a*a)
if (b&1)	s=s*a;
return s;
}
}a,b;
//}}}Martix
//{{{get_phi
int get_phi (int x)
{
int res=x;
for (int i=2;i*i<=x;++i)
if (x%i==0){
res=res/i*(i-1);
while (x%i==0)	x/=i;
}
if (x>1)	res=res/x*(x-1);
return res%mod;//此处要取模
}
//}}}
//{{{ksm
int ksm (int a,int b)
{
int s=1;
a%=mod;
for (;b;a=1ll*a*a%mod,b>>=1)
if (b&1)	s=1ll*s*a%mod;
return s;
}
//}}}
//{{{calc
int calc (int x)
{
b=a^x;
int res=0;
for (int i=1;i<=m;++i)	res=(res+b.rec[i][i])%mod;
return res;
}
//}}}
int main()
{
cin>>t;
while (t--){
cin>>n>>m>>k;
ans=0,ni=ksm(n,mod-2);//ni n的逆元
for (int i=1;i<=m;++i)
for (int j=1;j<=m;++j)
a.rec[i][j]=1;
while (k--){
cin>>x>>y;
a.rec[x][y]=a.rec[y][x]=0;
}
for (int i=1;i*i<=n;++i)
if (n%i==0){
ans=(ans+get_phi(i)*calc(n/i)%mod)%mod;
if (i*i!=n)	ans=(ans+get_phi(n/i)*calc(i)%mod)%mod;
}
ans=ans*ni%mod;
printf("%d\n",ans);
}
return 0;
}