给定一个\(n\)个点\(n\)条边的環，有\(n\)种颜色给每个顶点染色，问有多少种本质不同的染色方案答案对\(10^9+7\)取模

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

第一行输入一个\(t\)，表示有\(t\)组数据

第二行开始一共\(t\)行，每行一个整数\(n\)意思如题所示。

共\(t\)行每行一個数字，表示染色方案数对\(10^9+7\)取模后的结果

就是将え素的对应以表格形式来表示

相当于经过变换原来1的位置到了\(a_1\)，2的位置到了\(a_2\)。

根据题意，本质不同即为旋转

对于每个置换f我们定义C(f)为在置换f下保持不变的方案数。

则有： 本质不同的方案数為C(f)的平均数

其中，n为置换长度m是染色种类，\(x_i\)是i次置换的循环个数

比如长度为6的三次置换个数为3

但实际上，求\(\varphi\)的根号48化简只会被调用log次