给定一个 个点， 条边的环，有 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 取模。
注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。
第一行输入一个 ，表示有 组数据
第二行开始，一共 行，每行一个整数 ，意思如题所示。
共 行，每行一个数字，表示染色方案数对 取模后的结果
5 1 2 3 4 5
1 3 11 70 629
