512005 - pólya定理

【题目描述】pólya定理(polya)

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

输入

第一行输入一个t(t≤103),表示有t组数据。 随后t行,每行一个整数n(n≤109)。

输出

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

样例

输入

5
1 
2 
3 
4 
5

输出

1
3
11
70
629
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题