【模板】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$$