All Tracks Math Combinatorics Problem

Twins Fight
Tag(s):

Combinatorics, Easy, Math

Problem
Editorial
Analytics

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

SAMPLE INPUT
2
2 
7
SAMPLE OUTPUT
2
429
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

National Institute of Technology, Jamshedpur

Challenge Name

CodeGenesis 1.0

Notifications
View All Notifications