Score : 600 points
Given is an integer N. Snuke will choose integers s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1, and e_2 so that all of the following six conditions will be satisfied:
For every possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2), compute (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1), and find the sum of all computed values, modulo (10^{9} +7).
Solve this problem for each of the T test cases given.
Input is given from Standard Input in the following format:
T \mathrm{case}_1 \vdots \mathrm{case}_T
Each case is given in the following format:
N
Print T lines. The i-th line should contain the answer to the i-th test case.
4 4 6 10 1000000000
0 11 4598 257255556