Mr. DeMello has decided to sabotage the marks of his ~N_i~ student advisory!

To do this, he will assign each student the exams of another student in the advisory, ensuring no student gets their original exams.

Since you are not in Mr. DeMello's advisory (and want to ruin your friends' marks), he asks you to calculate the number of ways for him to assign the exams in his advisory ~\bmod 10^9 + 7~.

Can you help him?

Constraints

~1 \le T \le 100~

Subtask 1 [30%]

~1 \le N_i \le 8~

Subtask 2 [70%]

~1 \le N_i \le 10^6~

Input Specification

The first line will contain an integer, ~T~, the number of test cases.

The next ~T~ lines will contain an integer, ~N_i~, the number of students in his advisory.

Output Specification

Output ~T~ lines, the number of ways to assign each student the exams of another student in each advisory ~\bmod 10^9 + 7~.

Sample Input

3
3
8
13

Sample Output

2
14833
290792918

Explanation for Sample Output

For the first test case, there are ~2~ different assignments: