群论

置换群

置换：给定一个序列a，将a重新排列后一一映射即为置换

循环置换：将序列a整体向右平移1位后一一映射。

任意一个置换都可以拆分成若干个循环置换的乘积（乘积：设两个置换映射为f(x),g(x)，这其乘积为g(f(x))）

其实是废话，因为循环置换太特殊啦！

置换群：对于一个长度为n的序列a，其所有置换有n!种，选择其中若干种即为一个置换群。

Polya定理

Burnside引理：每个置换的**不动点**个数的平均值就是不同方案数。

Polya定理：假设有一个置换可以拆成k个循环，每个循环有c种选法，那么这个置换的不动点的个数就是\(c^k\)

std

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ps second
#define pf first


#define rd read()
inline int read()
{
    int xx=0,ff=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') ff=-1;c=getchar();}
    while(c>='0'&&c<='9') xx=xx*10+(c-'0'),c=getchar();
    return xx*ff;
}
inline void write(int out)
{
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}


const int N=2e5+5;
const int M=5e5+5;
const int INF=1e9+5;
const int MOD=1e9+7;
bool f1;
int m,k,n,qzh;

int q;
int T,mn=INF,ans;

int ksm(int a,int b){ 
    int res=1;
    while(b){
        if(b&1)res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>= 1;
    }
    return res;
}

int euler(int n) { //欧拉函数
    int res=1;
    for(int i=2; i*i<=n; i++)
        if(n%i==0) {
            n/=i,res=res*(i-1);
            while(n%i==0) n/=i,res=res*i;
        }
    if(n>1) res=res*(n-1);
    return res;
}

int polya(int m,int n) {
    int tot=0;
    for(int i=1; i*i<=n; i++) {
        if(n%i) continue;
        tot+=euler(i)*ksm(m,n/i-1);
        if(i*i!=n) tot+=euler(n/i)*ksm(m,i-1);
    }
    return tot%MOD;
}

signed main(){
    int t=rd;
    while(t--){
        int n=rd;
        cout<<polya(n,n)<<endl;
    }
}