After the hundred years of war started by the Fire Nation, its time for the Water Tribes to bring it to an end. Avatar asked Sokka to go to the Southern WarZone from The Northern WarZone and gave him some money in a bag for his journey. Sokka has the World Map to guide him during his journey . The World Map is described as a $N$x$N$ grid where the Northern WarZone is denoted by $(0,0)$ and the Southern WarZone is denoted by $(N-1,N-1)$. Each location on the world map is denoted in a similar way by two integers r and c. For each location having:  
- $r = c$ denotes neutral land ( $(0,0)$ and $(N-1,N-1)$ also come under this category)       
- $r < c$ denotes the land under the rule of Water Tribes     
- $r > c$ denotes the land under the rule of Fire Kingdom   
Being wise Sokka travels only from one location to any other valid location (by valid location we mean a location which exists on the world map grid i.e. for that location $0 \leq r < N$ and $0 \leq c < N$ ) just to the right $(r,c+1)$ or below $(r+1,c)$ the current location randomly. Due to the times of war , Sokka has to pay one coin  each time he transitions from one nation to another. Here a transition is counted when Sokka is in Water Tribe land and moves to Fire Nation Land crossing the neutral land or vice versa .The first move is obviously never counted as a transition. Moreover , the coin is to be payed exactly once for one such transition (eg. if he makes this transition k times he has to pay k coins).  
The initial number of coins Sokka has is $2*N$. The probability that the coins he has when he reaches his destination is lesser than the number of coins he started his journey with can be expressed as a fraction $P/Q$, where P and Q are integers $(P \geq 0, Q > 0)$  and Q is co-prime with $(10^9)+7$. You should compute $P/Q$ modulo $(10^9)+7$ for $T$ values of $N$.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, one integer $N$, the size of the world map grid. 

-----Output:-----
For each testcase, output in a single line , the Probability modulo (10^9)+7.

-----Constraints-----
- $1 \leq T \leq 100000$
- $2 \leq N \leq 10^9$

-----Sample Input:-----
2    

5

2    

-----Sample Output:-----
200000002     

0  

-----EXPLANATION:-----
For N=2, there is no possible path in which Sokka has to spend money, so the final number of coins in the bag is not lesser than the initial amount.

Difficulty: interview

Starter code:

Solutions:
m=1000000007
def gcd(a, b): 
    if (a == 0): 
        return b 
    return gcd(b % a, a)
def modexp(x, n): 
    if (n == 0) : 
        return 1
    elif (n % 2 == 0) : 
        return modexp((x * x) % m, n // 2) 
    else : 
        return (x * modexp((x * x) % m,  
                           (n - 1) / 2) % m)
def getFractionModulo(a, b): 
    c = gcd(a, b)
    a = a // c 
    b = b // c 
    d = modexp(b, m - 2) 
    ans = ((a % m) * (d % m)) % m
    return ans
t=int(input())
for i in range(t):
    n=int(input())
    n=n-1
    print(getFractionModulo(n-1,n+1))