前言
一脸懵逼。。。
（(Upt)：后来的我，终于入门成功了——重新入门的Polya定理）
公式
用(m)种颜色染色的本质不同的方案数：
[frac1{|G|}sum_{g∈G}m^{c(g)}
]
其中(c)表示置换(g)中环的个数。
板子题（点此看题面）
考虑本质不同只需要判旋转，因此共有(n)种置换方式，其中第(i)种置换方式就是将所有数移动(i)位。
显然，第(i)种置换中环的个数应该是(gcd(i,n))，因此得到答案的式子为：
[frac1nsum_{i=1}^nn^{gcd(i,n)}
]
看到(gcd)，自然而然想到莫比乌斯反演，于是套路地枚举(gcd)得到：
[frac1nsum_{d|n}n^dsum_{i=1}^{frac nd}[gcd(i,frac nd)=1]
]
其中，后半部分的式子显然就是(phi(frac nd))。
也就是：
[frac 1nsum_{d|n}n^dphi(frac nd)
]
因此，我们枚举(d)，然后暴力计算(phi(frac nd))，这道题就做完了。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define X 1000000007
using namespace std;
int n;I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
I int Phi(RI x)//暴力计算欧拉函数
{
RI i,t=1;for(i=2;i*i<=x;++i) if(!(x%i)) {t*=i-1,x/=i;W(!(x%i)) t*=i,x/=i;}
return x^1&&(t*=x-1),t;
}
int main()
{
RI Tt,i,t;scanf("%d",&Tt);W(Tt--)
{
for(scanf("%d",&n),t=0,i=1;i*i<=n;++i) !(n%i)&&//枚举因数
(t=(1LL*QP(n,i)*Phi(n/i)+t)%X,i^(n/i)&&(t=(1LL*QP(n,n/i)*Phi(i)+t)%X));//统计答案
printf("%d
",1LL*t*QP(n,X-2)%X);//乘上1/n
}return 0;
}