Chef is playing a game, which he starts with a score of S = 0. He also has an integer N.

In one move, Chef does the following:
Uniformly randomly pick an integer X between 0 and 2^{N} - 1 (inclusive of both ends)
Update his score as S \rightarrow S \mid X, where \mid denotes the [bitwise OR] operation

For example, if Chef's current score is S = 6 and he picks X = 10, his new score is 6\mid 10 = 14.

Chef stops when his score S becomes equal to 2^{N}-1.  What is the expected number of moves Chef performs?

Output the answer modulo 10^{9} + 7. That is, the answer can be expressed as a fraction P/Q, where \gcd(Q, 10^{9} + 7) = 1. Print P\cdot Q^{-1} \pmod{\ 10^{9} + 7}, where Q^{-1} denotes the modular multiplicative inverse of Q with respect to 10^{9} + 7.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case contains a single integer N.

------ Output Format ------ 

For each test case, output on a new line the expected number of moves Chef performs, modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 3 \cdot 10^{5}$
- Sum of $N$ over all test cases do not exceed $3 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (30 points):
$1 ≤ N ≤ 10^{3}$
Sum of $N$ over all test cases doesn't exceed $10^{3}$

Subtask 2 (70 points):
Original constraints

----- Sample Input 1 ------ 
3
1
2
100

----- Sample Output 1 ------ 
2
666666674
328238032

----- explanation 1 ------ 
Test case $1$: In each move, Chef chooses either $0$ or $1$, each with a probability of $1/2$. The game ends as soon as Chef chooses $1$. Thus, the probability that the game takes exactly $k$ moves is $2^{-k}$.

The required expected value is then $\displaystyle\sum_{k=1}^\infty k\cdot 2^{-k}$, which [equals $2$]. 

Test case $2$: In each move, Chef chooses an integer in $[0, 3]$. The answer is $8/3$.

Source: codechef | Difficulty: VERY_HARD
Tags: Matrices

Combinatorics

Mathematics

Probability


Solutions:
MOD = 10 ** 9 + 7
MAXN = 3 * 10 ** 5

def modpow(base, exp, mod):
	result = 1
	while exp:
		if exp & 1:
			result = result * base % mod
		base = base * base % mod
		exp >>= 1
	return result

def modinv(base, mod):
	return modpow(base, mod - 2, mod)
FACT = [1] * (MAXN + 1)
FACTINV = [1] * (MAXN + 1)
POW2 = [1] * (MAXN + 1)
POW2_1INV = [1] * (MAXN + 1)
for n in range(1, MAXN + 1):
	FACT[n] = n * FACT[n - 1] % MOD
	FACTINV[n] = modinv(FACT[n], MOD)
	POW2[n] = 2 * POW2[n - 1] % MOD
	POW2_1INV[n] = modinv(POW2[n] - 1, MOD)

def binomial(N, K):
	return FACT[N] * FACTINV[K] * FACTINV[N - K]

def main(N):
	expect = 0
	for K in range(1, N + 1):
		expect = (expect - (-1) ** K * binomial(N, K) * POW2[K] * POW2_1INV[K]) % MOD
	return expect
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	print(main(N))