Dexter loves to solve problems. This time his friend Ashish decides to challenge him.
Ashish gives him number N, all the numbers from 1 to N can be arranged in a 2-D matrix. There can be multiple arrangements such that the value of a palpak is maximized.
What is palpak?
Suppose the matrix made by arranging the numbers is A
A new matrix is made from A (say B) whose values are calculated as:
Let the number of rows be N
Let the number of columns be M

for i from 1 to N  
      for j from 1 to M  
            B[i][j]=A[i][j]  
            for k from i+1 to N  
                  B[i][j]=B[i][j]%A[k][j]

palpak is the value calculated from the matrix B as follows:

palpak=1 
for i from 1 to N
      sum=0
      for j from 1 to M
            sum=sum+B[i][j]
            palpak=palpak*sum

Dexter is trying hard to solve this problem. Please help Dexter in solving this problem.

Input Format
The first line contains T, the number of test cases.
Then N numbers follow.

Output Format
Output the query of Dexter mod 1000000007.

Constraints
1 <= T <= 10
1 <= N <= 1000