512005 - pólya定理

【题目描述】pólya定理（polya）

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

第一行输入一个t（t≤103），表示有t组数据。 随后t行，每行一个整数n（n≤109）。

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