Problem Statement
Given is an integer N. Snuke will choose integers s1, s2, n1, n2, u1, u2, k1, k2, e1, and e2 so that all of the following six conditions will be satisfied:
- 0leqs1<s2
- 0leqn1<n2
- 0lequ1<u2
- 0leqk1<k2
- 0leqe1<e2
- s1+s2+n1+n2+u1+u2+k1+k2+e1+e2leqN
For every possible choice (s1,s2,n1,n2,u1,u2,k1,k2,e1,e2), compute (s2−s1)(n2−n1)(u2−u1)(k2−k1)(e2−e1), and find the sum of all computed values, modulo (109+7).
Solve this problem for each of the T test cases given.
Constraints
- All values in input are integers.
- 1leqTleq100
- 1leqNleq109
Input is given from Standard Input in the following format:
T
mathrmcase1
vdots
mathrmcaseT
Each case is given in the following format:
N
Output
Print T lines. The i-th line should contain the answer to the i-th test case.
Sample Output 1
- When N=4, there is no possible choice (s1,s2,n1,n2,u1,u2,k1,k2,e1,e2). Thus, the answer is 0.
- When N=6, there are six possible choices (s1,s2,n1,n2,u1,u2,k1,k2,e1,e2) as follows:
- (0,1,0,1,0,1,0,1,0,1)
- (0,2,0,1,0,1,0,1,0,1)
- (0,1,0,2,0,1,0,1,0,1)
- (0,1,0,1,0,2,0,1,0,1)
- (0,1,0,1,0,1,0,2,0,1)
- (0,1,0,1,0,1,0,1,0,2)
- We have one choice where (s2−s1)(n2−n1)(u2−u1)(k2−k1)(e2−e1) is 1 and five choices where (s2−s1)(n2−n1)(u2−u1)(k2−k1)(e2−e1) is 2, so the answer is 11.
- Be sure to find the sum modulo (109+7).