polya定理。等价类的个数等于∑颜色数^置换的轮换个数
不可翻转的串当中。直接计算∑m^(gcd(n,i)) ，这里gcd(n,i)就是第i个置换的轮换数。
翻转的情况再分n奇偶讨论。
n次二面体都是这个套路。
/*--------------------------------------------------------------------------------------*/ #include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map> //debug function for a N*M array
#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\
{for(int j=;j<(M);j++){\
printf("%d",G[i][j]);}printf("\n");}
//debug function for int,float,double,etc.
#define debug_var(X) cout<<#X"="<<X<<endl;
#define LL long long
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
/*--------------------------------------------------------------------------------------*/
using namespace std; int N,M,T;
const LL MOD = 1e9+; LL pow_mod(LL x,LL cnt)
{
LL base = x,res = ;
while(cnt)
{
if(cnt&) {res*=base;res%=MOD;}
base *= base;base %= MOD;
cnt >>= ;
}
return res%MOD;
}
LL inv(LL x,LL m)
{
return pow_mod(x,m-);
}
LL polya(LL n,LL m)
{
LL res = ;
for(int i=;i<=n;i++)
{
res += pow_mod(m,__gcd((LL)i,n));
res %= MOD;
} if(n&) res += n*pow_mod(m,n/+);
else res += (n*pow_mod(m,n/))%MOD*inv(,MOD)%MOD + (n*pow_mod(m,n/+))%MOD*inv(,MOD)%MOD ; res %= MOD;
res *= inv(*n,MOD); return res%MOD;
} int main()
{
scanf("%d",&T);
int cas = ;
while(T--)
{
scanf("%d%d",&M,&N);
printf("Case #%d: %lld\n",++cas,polya(N,M));
}
}