【題目分析】
? ? 同樣是Burnside引理。但是有幾種顏色是不能放在一起的。
? ? 所以DP就好了。
? ? 然后T掉
? ? 所以矩陣乘法就好了。
? ? 然后T掉
? ? 所以取模取的少一些，矩陣乘法里的取模尤其要注意，就可以了。
? ? A掉
【代碼】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define maxn 11
#define ll long long
#define inf 0x3f3f3f3f
#define maxm 100005
const int md=9973;int T,n,m,k,ni,ispr[maxm],pr[maxm],top=0,sum;struct Matrix{int x[maxn][maxn];void init(){memset(x,0,sizeof x);}void clear(){F(i,1,m)F(j,1,m)x[i][j]=1;}void print(){F(i,1,m){F(j,1,m) printf("%d ",x[i][j]);printf("\n");}}
}A,B,C,D;Matrix operator * (const Matrix a,const Matrix b) {Matrix c;for (int i=1;i<maxn;++i)for (int j=1;j<maxn;++j){c.x[i][j]=0;for (int k=1;k<maxn;++k)c.x[i][j]+=a.x[i][k]*b.x[k][j];c.x[i][j]%=md;}return c;
}void init()
{F(i,2,maxm-1){if (!ispr[i]) pr[++top]=i;F(j,2,inf){if (i*j>=maxm) break;ispr[i*j]=1;}}
}int qpow(int a,int b)
{int ret=1;a%=md;while (b){if (b&1) (ret*=a)%=md;(a*=a)%=md;b>>=1;}return ret;
}int phi(int n)
{int ret=n;for (int i=1;pr[i]*pr[i]<=n&&i<=top;++i)if (n%pr[i]==0){ret=ret-ret/pr[i];while (n%pr[i]==0) n/=pr[i];}if (n>1) ret=ret-ret/n;return ret%md;
}int tak(int b)
{int ret=0;D.init();F(i,1,m)D.x[i][i]=1;C=B;while (b){if (b&1) D=D*C;C=C*C;b>>=1;}F(i,1,m) ret+=D.x[i][i];return ret;
}int main()
{init();scanf("%d",&T);while (T--){sum=0;scanf("%d%d%d",&n,&m,&k);ni=qpow(n,md-2);B.init();B.clear();F(i,1,k){int a,b;scanf("%d%d",&a,&b);B.x[a][b]=B.x[b][a]=0;}for (int i=1;(ll)i*(ll)i<=(ll)n;++i){if (n%i==0){sum=(sum+tak(i)*phi(n/i))%md;if (i*i!=n)sum=(sum+tak(n/i)*phi(i))%md;}}printf("%d\n",(sum*ni)%md);}
}
