Polya定理是一个关于置换群中组合计数的定理。
首先我们来了解Burnside引理。这个引理的证明较为复杂，在这里仅介绍其内容。
Burnside引理的内容是这样的：在置换意义下本质不同的染色方案数，等于单个置换不会改变的染色方案数的平均值。
那么，单个置换不会改变的染色方案数要怎么求呢？我们不妨把置换关系建成一张图，那么这张图必然由若干个环构成。也就是说，对于同一种置换，可能存在若干个环，而每个初始状态就是环上的一个节点。Polya定理描述的就是，某一种置换不会改变的方案数，等于颜色数的「这个置换对应的循环节个数」
阐述了上述两个定理，现在我们来看这一题。
我们观察到，这个环上存在 n 种置换。对于置换 i 而言，它的循环大小是：
$$
\frac{n}{\gcd(n,i)}
$$
这也就意味着，它的循环个数是：
$$
\gcd(n,i)
$$
那么我们要求的答案就是：
$$
\frac{\sum_{i=1}^nn^{(n,i)}}{n}
$$
然而这样计算答案的复杂度是 O(n) 的，我们无法接受。
我们不妨考虑枚举这个公因子。那么，容易证明的是，每一个公因子d对应的置换个数是\(\varphi(\frac{n}{d})\)
这是因为， d 是 \(\frac{n}{d}\) 个数的因数，而这些数中，如果它和\(\frac{n}{d}\)存在公因子的话，那么它和n的最大公因数必然大于d。
所以，我们求的就是：
$$
\frac{\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}}}{n}=\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}-1}
$$
我们只要枚举n的因数即可。
然而求这里的 \(\varphi\) 倒可能存在一些问题。事实上，由于我们要取的因数的值域是 \(10^9\) ，我们无法使用欧拉筛来预处理，而需要现场做。
这样的复杂度是不是对的呢？它的最坏情况是 \(O(Tn^{\frac{3}{4}})\) 的，但由于我并不会分析的一些性质，它不会达到这个值。因此可以通过此题。
另：括号忘记加，爆O泪两行。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=1000005;
inline ll pw(ll A,ll X){
ll RT=1;
while(X){
if(X&1){
RT*=A;RT%=MOD;
}
A*=A;A%=MOD,X>>=1;
}
return RT;
}
int n;
inline int phi(int X){
int RT=1;
for(int i=2;i*i<=X;++i){
if(X%i==0){
X/=i;RT*=i-1;
while(X%i==0){
X/=i;RT*=i;
}
}
if(X==1){
break;
}
}
if(X>1){
RT*=X-1;
}
return RT;
}
void init(){
scanf("%d",&n);
ll ans=0;
for(int i=1;i*i<=n;++i){
if(n%i==0){
ans+=(1ll*phi(n/i)*pw(n,i-1))%MOD;
if(i*i!=n){
ans+=(1ll*phi(i)*pw(n,n/i-1))%MOD;
}
ans%=MOD;
// printf("%d %lld\n",i,ans);
}
}
printf("%lld\n",ans);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}