You are given a cycle with $n$ vertices and $n$ edges, where there are $n$ different colors. Each vertex must be colored with one of the $n$ colors. Determine the number of different colorings, where the result is taken modulo $10^9 + 7$.
### Input
- The first line contains one positive integer $t.$
- $t$ lines later, each line contains one number $n.$
### Output
- Output $t$ lines, each line is the answer for the respective testcase.
### Constraints
- $1 \le t \le 10^3.$
- $1 \le n \le 10^9.$
### Example
Input
```
4
2
3
4
5
```
Output
```
3
11
70
629
```
