Watson gives a square of side length 1 to Sherlock. Now, after each second, each square of some arbitrary side $\boldsymbol{\mbox{I}}$ will break into four squares each of side $L/2$(as shown in the image below). 

Now, Watson asks Sherlock: What will be the sum of length of solid lines after $N$ seconds?  

As the number can be large print result mod $(10^9+7)$.

For example, after 0 seconds, the length is 4. 

After 1 second, the length is 6.

Input Format 

First line contains $\mathbf{T}$, the number of testcases. Each testcase contains $N$ in one line.   

Output Format

For each testcase, print the required answer in a new line. 

Constraints 

$1\leq T\leq10^5$ 

$0\leq N\leq10^9$

Sample input

3
0
1
5

Sample output

4
6
66

Difficulty: MEDIUM_HARD
Tags: Matrices

Starter code:

Solutions:
t = int(input())
P = 10 ** 9 + 7

def f(x):
	return (pow(2, x, P) + 1) * 2 % P
for _ in range(t):
	print(f(int(input())))


t = int(input())
base = 1000000007
while t > 0:
	t -= 1
	n = int(input())
	k = 1
	n += 1
	a = 2
	while n > 0:
		if n % 2 == 1:
			k = k * a % base
		n //= 2
		a = a * a % base
	k = (k + 2) % base
	print(k)


_mod = 10 ** 9 + 7

def f(n):
	return (2 + pow(2, n + 1, _mod)) % _mod
T = int(input())
for _ in range(T):
	N = int(input())
	print(f(N))


def LineSum(N):
	modulo = 10 ** 9 + 7
	p2 = pow(2, N, modulo)
	res = 2 * (p2 + 1) % modulo
	return res
T = int(input())
while T:
	T = T - 1
	N = int(input())
	print(LineSum(N))


m = 10 ** 9 + 7
for _ in range(int(input())):
	print((pow(2, int(input()) + 1, m) + 2) % m)


N = int(input())
for i in range(N):
	n = int(input())
	print(pow(2, n + 1, 1000000007) + 2 % 1000000007)


t = int(input())
for _ in range(t):
	n = int(input())
	print(pow(2, n + 1, 1000000007) + 2)


import math
n = int(input())
base = [2]
for i in range(n):
	x = int(input()) + 1
	while len(base) <= math.log2(x):
		base.append(base[-1] * base[-1] % (10 ** 9 + 7))
	pos = [len(bin(x)) - 1 - i for (i, c) in enumerate(bin(x)) if c == '1']
	prod = 1
	for p in pos:
		prod *= base[p] % (10 ** 9 + 7)
	print((prod + 2) % (10 ** 9 + 7))


modulus = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	print(str(pow(2, N + 1, modulus) + 2))


t = int(input())
ans = ''
mod = 1000000007
for i in range(0, t):
	n = int(input())
	x = (2 + pow(2, n + 1, mod)) % mod
	ans += str(x) + '\n'
print(ans)


p = int(1000000000.0) + 7
t = int(input())
for i in range(t):
	n = int(input())
	ans = 4
	if n > 0:
		ans += 2 * (pow(2, n, p) - 1)
		ans %= p
	print(ans)


m = 10 ** 9 + 7

def l(t):
	return (2 + pow(2, t + 1, m)) % m
for case in range(int(input())):
	print(l(int(input())))


for T in range(int(input())):
	(N, MOD) = (int(input()), 10 ** 9 + 7)
	print(pow(2, N + 1, MOD) + 2)


MOD = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	print((pow(2, N, MOD) + 1) * 2 % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((pow(2, N + 1, MOD) + 2) % MOD)


for _ in range(int(input())):
	print(2 + pow(2, int(input()) + 1, 1000000007))


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	print((2 + pow(2, n + 1, mod)) % mod)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((pow(2, N + 1, MOD) + 2) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((pow(2, N + 1, MOD) + 2) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((pow(2, N + 1, MOD) + 2) % MOD)


test_cases = int(input())
MOD = 10 ** 9 + 7

def two_to_the(n):
	if n == 0:
		return 1
	if n % 2 == 0:
		k = two_to_the(n // 2)
		return k * k % MOD
	else:
		k = two_to_the(n // 2)
		return k * k * 2 % MOD
for t in range(test_cases):
	seconds = int(input()) + 1
	result = 2 + two_to_the(seconds)
	print(result % MOD)


p = 1000000007
for _ in range(int(input())):
	print((2 + pow(2, int(input()) + 1, p)) % p)


T = int(input())
modulo = 10 ** 9 + 7
for cnt_T in range(T):
	N = int(input())
	out = pow(2, N + 1, modulo)
	out = (out + 2) % modulo
	print(out)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((pow(2, N + 1, MOD) + 2) % MOD)


n = int(input().strip())
for _ in range(n):
	val = int(input().strip())
	print((pow(2, val + 1, 10 ** 9 + 7) + 2) % (10 ** 9 + 7))


MOD = 1000000007

def solve():
	N = int(input())
	ans = pow(2, N + 1, MOD)
	ans = (ans + 2) % MOD
	print(ans)

def main():
	T = int(input())
	while T > 0:
		solve()
		T -= 1
main()


mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	print((pow(2, n + 1, mod) + 2) % mod)


modo = 10 ** 9 + 7
for _ in range(int(input().strip())):
	print((2 + pow(2, 1 + int(input().strip()), modo)) % modo)


print(*((4 + 2 * (pow(2, int(input()), 1000000007) - 1)) % 1000000007 for _ in range(int(input()))), sep='\n')


t = int(input())
M = 1000000007
while t > 0:
	t -= 1
	n = int(input())
	ans = pow(2, n + 1, M)
	ans = (2 + ans) % M
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	print((pow(2, n + 1, 1000000007) + 2) % 1000000007)


p = 1000000007
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	print((pow(2, n, p) + 1) % p * 2 % p)


t = int(input())
for _ in range(t):
	n = int(input())
	print((pow(2, n + 1, 1000000007) + 2) % 1000000007)


P = 10 ** 9 + 7

def sqr(a):
	return a * a % P

def mul(a, c):
	return a * c % P

def exp(a, n):
	A = [a]
	rr = 1
	lim = len(bin(n)) - 2
	for i in range(lim):
		c = A[-1]
		A.append(sqr(c))
		if n % 2 == 1:
			rr = mul(A[i], rr)
		n >>= 1
	return rr
T = int(input())
for i in range(T):
	N = int(input())
	print((exp(2, N + 1) + 2) % P)


N = int(1000000000.0) + 7

def gp(r, n):
	return (pow(r, n + 1, N) - r) // (r - 1)

def result(n):
	return (4 + gp(2, n)) % N
for _ in range(int(input())):
	print(result(int(input())))


T = int(input())
m = 1000000007
for i in range(T):
	N = int(input())
	print((pow(2, N + 1, m) + 2) % m)


for _ in range(0, int(input())):
	n = int(input())
	print((4 + pow(2, n + 1, 1000000007) - 2) % 1000000007)


for i in range(int(input())):
	print(pow(2, int(input()) + 1, 10 ** 9 + 7) + 2)


M = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	print((pow(2, n + 1, M) + 2) % M)


m = 10 ** 9 + 7

def fast_exp(x, n):
	r = 1
	while n:
		if n % 2:
			r = r * x % m
		x = x * x % m
		n //= 2
	return r
for t in range(int(input())):
	n = int(input())
	print((fast_exp(2, n + 1) + 2) % m)


t = int(input())
mm = 10 ** 9 + 7

def power_mod(k):
	p = 2
	ret = 1
	while k > 0:
		if k & 1 == 1:
			ret = ret * p % mm
		p = p ** 2 % mm
		k >>= 1
	return ret
while t > 0:
	t -= 1
	n = int(input())
	print(2 * (power_mod(n) + 1) % mm)


def find(n):
	return 2 * (pow(2, n, 10 ** 9 + 7) + 1) % (10 ** 9 + 7)
for _ in range(int(input())):
	print(find(int(input())))


for _ in range(int(input())):
	n = int(input())
	p = 10 ** 9 + 7
	print((pow(2, n + 1, p) + 2) % p)


def power(a, b, mod):
	if b == 0:
		return 1
	else:
		result = 1
		c = a
		while b > 0:
			if b % 2 == 1:
				result = result * c % mod
			c = c ** 2 % mod
			b = b // 2
		return result
for i in range(int(input())):
	n = int(input())
	modulo = pow(10, 9) + 7
	result = 2 + power(2, n + 1, modulo)
	print(result)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	print(pow(2, n + 1, 10 ** 9 + 7) + 2)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((pow(2, N + 1, MOD) + 2) % MOD)


t = int(input())
for _ in range(t):
	k = int(input())
	r = pow(2, k, 10 ** 9 + 7)
	print((r + 1) * 2 % (10 ** 9 + 7))


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m
T = int(input())
modulus = pow(10, 9) + 7
for _ in range(0, T):
	n = int(input())
	print(pow_mod(2, n + 1, modulus) + 2)


import sys

def f(k, m):
	return (pow(2, k + 1, m) + 2) % m

def solve(n, m):
	if n == 0:
		return 4
	u = f(n, m)
	return u
m = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n, m))


def le(n):
	r = pow(2, n, 10 ** 9 + 7)
	return (r + 2) % (10 ** 9 + 7)
for _ in range(int(input())):
	print(le(int(input()) + 1))


mod = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	n = int(input())
	print((pow(2, n + 1, mod) - 2 + 4) % mod)


t = int(input())
for _ in range(t):
	n = int(input())
	y = 4 + pow(2, n + 1, 10 ** 9 + 7) - 1
	print((y - 1) % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	print((pow(2, n + 1, MOD) + 2) % MOD)


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	print((pow(2, n + 1, MOD) + 2) % MOD)


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
p = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = power(2, n + 1, p)
	print((a + 2) % p)


t = int(input())
P = 10 ** 9 + 7

def f(x):
	return (pow(2, x, P) + 1) * 2 % P
for _ in range(t):
	print(f(int(input())))


p = 10 ** 9 + 7
for _ in range(int(input())):
	print(2 * (1 + pow(2, int(input()), p)) % p)


P = 10 ** 9 + 7

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		print((2 + pow(2, N + 1, P)) % P)
main()


import os
import sys
MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	print((pow(2, n + 1, MOD) + 2) % MOD)


t = int(input())
while t > 0:
	n = int(input())
	ans = (pow(2, n + 1, 1000000007) + 2) % 1000000007
	print(ans)
	t -= 1


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	print((pow(2, n + 1, MOD) + 2) % MOD)


test = int(input())
for i in range(test):
	n = int(input())
	print((pow(2, n + 1, 1000000007) + 2) % 1000000007)


import os
import sys

def LineSum(N):
	modulo = 10 ** 9 + 7
	p2 = pow(2, N, modulo)
	res = 2 * (p2 + 1) % modulo
	return res
T = int(input())
while T:
	T = T - 1
	N = int(input())
	print(LineSum(N))


for _ in range(int(input())):
	print(pow(2, int(input()) + 1, 1000000007) + 2)


m = 10 ** 9 + 7

def pew(a, b):
	t = 1
	while b > 0:
		if b % 2 == 1:
			t = t % m * (a % m)
		a = a % m * (a % m)
		b >>= 1
	return t % m
for _ in range(int(input())):
	n = int(input())
	print((pew(2, n + 1) + 2) % m)