题目描述

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

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

输入格式

第一行输入一个 $t(t \leq 10^3)$，表示有 $t$ 组数据

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

输出格式

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

输入输出样例 #1

输入 #1

5
1 
2 
3 
4 
5

输出 #1

1
3
11
70
629