N pairs of twins were taken on a picnic in the kumbh mela 12 years ago by two uncles A and B. Both the uncles divided the kids in a manner such that each one (uncle) of them had one kid of each pair{ say from a pair of Ram-Shyam(1-1) and Sita-Gita(2-2), A takes Ram and Sita(1 and 2)and B takes Shyam and Gita(1 and 2)}. B being the wicked uncle filled them with negative energies and kept them apart for 12 years!
You being a senior member of the family thought of ending their grudges so that they can meet and live happily.. But the meeting and get together has to happen in the following pattern!
Note- the negative transformation initially can be seemed as multiplying each element in the array of B by - 1
Note - the positive people should be in sorted order always.
Rule 1- all the negative people (twins) should come after their positive counterparts in the queue.
Rule 2- if positive twin is followed by a negative person, that negative person should be the twin of that very counter part Eg (1 2 - 2 - 1 or 1 - 1 2 - 2) but not (1 2 - 1 - 2).
Rule 3- always the latter positive person should have its negative counterpart first eg.(2 3.......-3.... - 2).
Help them in finding the number of ways in which they can meet.
Input
The first line contains number of test cases.
Every test case contains an integer n denoting the number of pair of twins.
Output
Print the number of valid arrangements of twins to avoid grudges. The answer could be very large so you have to print answer modulo 1000000007.
Constraints
1 <= T <= 1000
1<= N <= 1000000