这题虽然很老了但是挺好的
仍然套Burnside引理(因为有限制你并不能套Polya定理)，思路和这个题一样，问题主要是如何求方案。
思路是把放珠子的方案看成一张图，然后就巧妙的变成了一个经典的路径计数问题，这里可以多矩乘一次然后统计对角线，即强行让它走回一开始的珠子，比较方便
注：这代码T了，我不想卡了，但是复杂度和正确性没问题，请根据自己的情况食用
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=;
int T,n,m,k,t1,t2,mapp[][];
struct a
{
int mat[][];
void Clean()
{
memset(mat,,sizeof mat);
}
void Init()
{
for(int i=;i<=m;i++)
for(int j=;j<=m;j++)
mat[i][j]=mapp[i][j];
}
};
a Matime(a x,a y)
{
a ret; ret.Clean();
for(int i=;i<=m;i++)
for(int k=;k<=m;k++)
for(int j=;j<=m;j++)
ret.mat[i][j]+=x.mat[i][k]*y.mat[k][j]%mod,ret.mat[i][j]%=mod;
return ret;
}
a Maqpow(a x,int k)
{
if(k==) return x;
a tmp=Maqpow(x,k/);
return k%?Matime(x,Matime(tmp,tmp)):Matime(tmp,tmp);
}
int Calc(int x)
{
a cal; int ret=;
cal.Init(),cal=Maqpow(cal,x);
for(int i=;i<=m;i++)
ret+=cal.mat[i][i],ret%=mod;
return ret;
}
int Phi(int x)
{
int ret=x;
for(int i=;i*i<=x;i++)
if(x%i==)
{
ret/=i,ret*=i-;
while(x%i==) x/=i;
}
if(x!=) ret/=x,ret*=x-;
return ret;
}
void exGCD(int a,int b,int &x,int &y)
{
if(!b) x=,y=;
else exGCD(b,a%b,y,x),y-=a/b*x;
}
int Inv(int x)
{
int xx,yy;
exGCD(x,mod,xx,yy);
return (xx%mod+mod)%mod;
}
int Solve(int x)
{
int ret=;
for(int i=;i*i<=x;i++)
if(x%i==)
{
ret+=Phi(x/i)*Calc(i)%mod,ret%=mod;
if(i*i!=x) ret+=Phi(i)*Calc(x/i)%mod,ret%=mod;
}
return ret*Inv(x)%mod;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++)
for(int j=;j<=m;j++)
mapp[i][j]=;
for(int i=;i<=k;i++)
{
scanf("%d%d",&t1,&t2);
mapp[t1][t2]=mapp[t2][t1]=;
}
printf("%d\n",Solve(n));
}
return ;
}