There is a regular polygon with N sides (and hence N vertices). N ants are sitting on it; one at each vertex. In one move, each ant randomly picks a direction (either left or right) and starts to move along the side of the polygon.
Your task is to find the probability that atleast two of the ants will collide after one move.
If the probability is expressed as P/Q (such that P,Q are integers), print the value ( P ∗ Q-1 ) modulo 1000000007, where Q−1 denotes the Modular Inverse of Q with respect to 109+7.
Note: in one move, an ant should take exactly one step - either left or right.
Input Format
The first line contains an integer T denoting the number of test cases. (1<=T<=100)
Next T lines contain an integer N, denoting the number of sides of the polygon.(3<=N<=100)
Output Format
For each case print the required probablity in a new line.