【模板】Polya定理

题目描述

给定一个$n$个点,$n$条边的环,有$n$种颜色,给每个顶点染色,问有多少种**本质不同**的染色方案,答案对$10^9+7$取模 注意本题的本质不同,定义为:**只需要不能通过旋转与别的染色方案相同**。

输入输出格式

输入格式


第一行输入一个$t$,表示有$t$组数据 第二行开始,一共$t$行,每行一个整数$n$,意思如题所示。

输出格式


共$t$行,每行一个数字,表示染色方案数对$10^9+7$取模后的结果

输入输出样例

输入样例 #1

5
1 
2 
3 
4 
5 

输出样例 #1

1
3
11
70
629

说明

$$n \leq 10^9$$ $$t \leq 10^3$$