#P4980. 【模板】Pólya 定理

【模板】Pólya 定理

题目描述

给定一个 nn 个点,nn 条边的环,有 nn 种颜色,给每个顶点染色,问有多少种本质不同的染色方案,答案对 109+710^9+7 取模

注意本题的本质不同,定义为:只需要不能通过旋转与别的染色方案相同

输入格式

第一行输入一个 tt,表示有 tt 组数据

第二行开始,一共 tt 行,每行一个整数 nn,意思如题所示。

输出格式

tt行,每行一个数字,表示染色方案数对 109+710^9+7 取模后的结果

5
1 
2 
3 
4 
5 
1
3
11
70
629

提示

n109n \leq 10^9 t103t \leq 10^3