Lee tried so hard to make a good div.2 D problem to balance his recent contest, but it still doesn't feel good at all. Lee invented it so tediously slow that he managed to develop a phobia about div.2 D problem setting instead. And now he is hiding behind the bushes...

Let's define a Rooted Dead Bush (RDB) of level $n$ as a rooted tree constructed as described below.

A rooted dead bush of level $1$ is a single vertex. To construct an RDB of level $i$ we, at first, construct an RDB of level $i-1$, then for each vertex $u$:   if $u$ has no children then we will add a single child to it;  if $u$ has one child then we will add two children to it;  if $u$ has more than one child, then we will skip it. 

 [Image] Rooted Dead Bushes of level $1$, $2$ and $3$. 

Let's define a claw as a rooted tree with four vertices: one root vertex (called also as center) with three children. It looks like a claw:

 [Image] The center of the claw is the vertex with label $1$. 

Lee has a Rooted Dead Bush of level $n$. Initially, all vertices of his RDB are green.

In one move, he can choose a claw in his RDB, if all vertices in the claw are green and all vertices of the claw are children of its center, then he colors the claw's vertices in yellow.

He'd like to know the maximum number of yellow vertices he can achieve. Since the answer might be very large, print it modulo $10^9+7$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Next $t$ lines contain test cases — one per line.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^6$) — the level of Lee's RDB.


-----Output-----

For each test case, print a single integer — the maximum number of yellow vertices Lee can make modulo $10^9 + 7$.


-----Example-----
Input
7
1
2
3
4
5
100
2000000

Output
0
0
4
4
12
990998587
804665184



-----Note-----

It's easy to see that the answer for RDB of level $1$ or $2$ is $0$.

The answer for RDB of level $3$ is $4$ since there is only one claw we can choose: $\{1, 2, 3, 4\}$.

The answer for RDB of level $4$ is $4$ since we can choose either single claw $\{1, 3, 2, 4\}$ or single claw $\{2, 7, 5, 6\}$. There are no other claws in the RDB of level $4$ (for example, we can't choose $\{2, 1, 7, 6\}$, since $1$ is not a child of center vertex $2$).

 $\therefore$ Rooted Dead Bush of level 4.

Difficulty: HARD
Tags: Graph algorithms

Greedy algorithms

Tree algorithms

Dynamic programming

Mathematics
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
max_s = 2000003
c = 1000000007
q = [0] * max_s
for i in range(3, max_s):
	if not i % 3:
		q[i] = (q[i - 1] + 2 * q[i - 2] + 1) % c
	else:
		q[i] = (q[i - 1] + 2 * q[i - 2]) % c
for _ in range(int(input())):
	print(q[int(input())] * 4 % c)


def draw(n):
	MOD = 10 ** 9 + 7
	INV = 47619048
	ADD = [6, -30, -18]

	def fpow(x, n):
		r = 1
		while n > 1:
			if n & 1:
				r = r * x % MOD
			x = x * x % MOD
			n >>= 1
		return x * r % MOD
	return (fpow(2, n + 3) + 14 * (2 * (n & 1) - 1) + ADD[n % 3]) * INV % MOD
t = int(input())
for i in range(t):
	n = int(input())
	print(draw(n))


l = [0, 0, 4]
m = 1000000007
for i in range(4, 2 * 1000000 + 1):
	l.append((l[-1] + 2 * l[-2] + (i % 3 == 0) * 4) % m)
for _ in range(int(input())):
	n = int(input())
	print(l[n - 1])


from collections import deque
t = int(input())
Edge_Nodes = 0
Infant_Nodes = 1
Claw = 0
d = {}
d1 = set()
l = [0]
queue = deque(l)
l1 = []
for i in range(t):
	l1.append(int(input()))
	d1.add(l1[-1])
ans = []
d[1] = 0
for j in range(2, 2 * 10 ** 6 + 1):
	temp = Infant_Nodes
	Infant_Nodes = (2 * Edge_Nodes + Infant_Nodes) % (10 ** 9 + 7)
	Claw = Edge_Nodes % (10 ** 9 + 7)
	Edge_Nodes = temp % (10 ** 9 + 7)
	if j > 3:
		queue.append((Claw + queue.popleft()) % (10 ** 9 + 7))
	else:
		queue.append(Claw)
	if j in d1:
		d[j] = 4 * queue[len(queue) - 1] % (10 ** 9 + 7)
for i in l1:
	print(d[i])


f = [0, 0, 0, 4, 4]
for i in range(5, 2000001):
	f.append((2 * f[-2] + f[-1] + (4 if i % 3 == 0 else 0)) % 1000000007)
for tt in range(int(input())):
	print(f[int(input())])


t = int(input())
dp = []
dp.append(0)
dp.append(0)
dp.append(0)
dp.append(4)
dp.append(4)
mod = 10 ** 9 + 7
for i in range(5, 2000001, 1):
	a = dp[i - 1] + 2 * dp[i - 2]
	if i % 3 == 0:
		a += 4
	a %= mod
	dp.append(a)
for i in range(t):
	n = int(input())
	print(dp[n])


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
ANS = [0, 0, 0, 4, 4]
HEAD = [0, 0, 0, 1, 0]
for i in range(2 * 10 ** 6):
	if HEAD[-1] == 0 and HEAD[-2] == 0:
		ANS.append((ANS[-1] + ANS[-2] * 2 + 4) % mod)
		HEAD.append(1)
	else:
		ANS.append((ANS[-1] + ANS[-2] * 2) % mod)
		HEAD.append(0)
t = int(input())
for tests in range(t):
	n = int(input())
	print(ANS[n])


pe = [0 for i in range(2000001)]
for i in range(3, 2000001):
	if i % 3 == 0:
		pe[i] = (pe[i - 1] + pe[i - 2] * 2 + 1) % 1000000007
	else:
		pe[i] = (pe[i - 1] + pe[i - 2] * 2) % 1000000007
for _ in range(int(input())):
	n = int(input())
	print(pe[n] * 4 % 1000000007)


def preprocess(pref):
	mod = int(1000000000.0) + 7
	for i in range(3, 2000005):
		pref.append((pref[i - 1] + pref[i - 2] * 2 + (4 if i % 3 == 0 else 0)) % mod)

def main():
	pref = [0, 0, 0]
	preprocess(pref)
	for _ in range(int(input())):
		print(pref[int(input())])
main()


mod = 1000000007
dp = [0, 0, 0, 1, 1]
for i in range(5, 2000001):
	if i % 3 == 0:
		dp.append((dp[i - 1] + 2 * dp[i - 2] + 1) % mod)
	else:
		dp.append((dp[i - 1] + 2 * dp[i - 2]) % mod)
t = int(input())
for i in range(t):
	n = int(input())
	print(4 * dp[n] % mod)


d = [0 for _ in range(2000001)]
d[3] = 4
for i in range(4, 2000001):
	if i % 3 == 0:
		d[i] = (2 * d[i - 2] + d[i - 1] + 4) % 1000000007
	else:
		d[i] = (2 * d[i - 2] + d[i - 1]) % 1000000007
n = int(input())
while n > 0:
	x = int(input())
	print(d[x])
	n -= 1


mod = 10 ** 9 + 7
ans = [0, 0, 4, 4]
t = int(input())
for i in range(5, 2000010):
	temp = ans[i - 2] + 2 * ans[i - 3]
	if i % 3 == 0:
		temp += 4
	ans.append(temp % mod)
for _ in range(t):
	n = int(input())
	print(ans[n - 1])


solution = [0, 0, 0, 4, 4]

def store(n):
	(prev1, prev2, sol) = (1, 1, 0)
	for i in range(5, n + 1):
		sol = 2 * prev2 + prev1
		if i % 3 == 0:
			sol += 1
		sol = sol % 1000000007
		(prev2, prev1) = (prev1, sol)
		solution.append(sol * 4 % 1000000007)
t = int(input())
store(2000000)
while t > 0:
	print(solution[int(input())])
	t -= 1


m = 1000000007
k = 2000001
x = [0] * k
x[3] = 4
c = 3
for t in range(int(input())):
	n = int(input())
	if n <= c:
		print(x[n])
	else:
		for i in range(c + 1, n + 1):
			a = x[i - 1] + 2 * x[i - 2]
			if i % 3 == 0:
				a += 4
			x[i] = a % m
		c = n
		print(x[n])


def gns():
	return list(map(int, input().split()))
t = int(input())
ns = []
ans = [0, 0, 0, 4, 4, 12]
for _ in range(t):
	n = int(input())
	ns.append(n)
mx = max(ns)
md = 10 ** 9 + 7
for i in range(6, mx + 6):
	ans.append((ans[-2] * 2 + ans[-1] + (4 if i % 3 == 0 else 0)) % md)
for ni in ns:
	print(ans[ni])


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 19
MOD = 10 ** 9 + 7

def mat_pow(mat, init, K, MOD):

	def mat_dot(A, B, MOD):
		if not isinstance(A[0], list) and (not isinstance(A[0], tuple)):
			A = [A]
		if not isinstance(B[0], list) and (not isinstance(A[0], tuple)):
			B = [[b] for b in B]
		n1 = len(A)
		n2 = len(A[0])
		_ = len(B)
		m2 = len(B[0])
		res = list2d(n1, m2, 0)
		for i in range(n1):
			for j in range(m2):
				for k in range(n2):
					res[i][j] += A[i][k] * B[k][j]
					res[i][j] %= MOD
		return res

	def _mat_pow(mat, k, MOD):
		n = len(mat)
		res = list2d(n, n, 0)
		for i in range(n):
			res[i][i] = 1
		while k > 0:
			if k & 1:
				res = mat_dot(res, mat, MOD)
			mat = mat_dot(mat, mat, MOD)
			k >>= 1
		return res
	res = _mat_pow(mat, K, MOD)
	res = mat_dot(res, init, MOD)
	return [a[0] for a in res]
for _ in range(INT()):
	N = INT()
	mat = [[5, 6, 0, 4], [3, 2, 0, 0], [1, 2, 0, 0], [0, 0, 0, 1]]
	init = [4, 0, 0, 1]
	if N % 3 == 0:
		res = mat_pow(mat, init, N // 3 - 1, MOD)
		ans = res[0]
		print(ans)
	else:
		res = mat_pow(mat, init, N // 3, MOD)
		ans = res[3 - N % 3]
		print(ans)


p = [0, 0, 4]
n = 1000000007
for i in range(4, 2 * 1000000 + 1):
	p.append((p[-1] + 2 * p[-2] + (i % 3 == 0) * 4) % n)
for i in range(int(input())):
	n = int(input())
	print(p[n - 1])


limit = 10 ** 9 + 7
k = 2000001
A = [0] * k
A[3] = 4
for i in range(4, 2000001):
	save = A[i - 1] + 2 * A[i - 2]
	if i % 3 == 0:
		save += 4
	A[i] = save % limit
for t in range(int(input())):
	n = int(input())
	print(A[n])


s = [0] * 3
for i in range(3, 2000001):
	s.append((2 * s[-2] + s[-1] + (0 if i % 3 else 4)) % (10 ** 9 + 7))
for d in range(int(input())):
	print(s[int(input())])


mod = 1000000007
MAX = 2000000
arr = [int(-1)] * (MAX + 1)
arr[0] = 0
arr[1] = 0
arr[2] = 0
arr[3] = 4
arr[4] = 4
for i in range(5, MAX + 1):
	arr[i] = (arr[i - 1] + 2 * arr[i - 2] + 4 * (i % 3 == 0)) % mod
t = int(input())
while t > 0:
	n = int(input())
	print(arr[n])
	t -= 1


import sys
pprint = lambda s: print(' '.join(map(str, s)))
input = lambda : sys.stdin.readline().strip()
ipnut = input
n = 2000000
dp = [0] * n
mod = 1000000007
for i in range(2, n):
	dp[i] = (dp[i - 1] + 2 * dp[i - 2] + int(i % 3 == 2)) % mod
for i in range(int(input())):
	print(dp[int(input()) - 1] * 4 % mod)


dp = [0, 0, 0, 4, 4, 12]
for n in range(2000000 // 6):
	dp.append(dp[-1] * 2 % (10 ** 9 + 7))
	dp.append(dp[-1] * 2 % (10 ** 9 + 7))
	dp.append(dp[-1] * 2 % (10 ** 9 + 7))
	dp.append((dp[-1] * 2 + 4) % (10 ** 9 + 7))
	dp.append((dp[-1] * 2 - 4) % (10 ** 9 + 7))
	dp.append((dp[-1] * 2 + 4) % (10 ** 9 + 7))
T = int(input())
for i in range(T):
	n = int(input())
	print(dp[n] % (10 ** 9 + 7))


import atexit
import io
import sys
import math
from collections import defaultdict, Counter
m = pow(10, 9) + 7
dp = [0] * 2000001
for j in range(2, 2000001):
	dp[j] = (2 * dp[j - 2] + dp[j - 1] + (4 if j % 3 == 0 else 0)) % m
t = int(input())
for i in range(t):
	n = int(input())
	print(dp[n])


a = [0, 0, 1, 1]
m = 10 ** 9 + 7
for i in range(5, 2000001):
	x = a[i - 2] + 2 * a[i - 3]
	if i % 3 == 0:
		a.append((x + 1) % m)
	else:
		a.append(x % m)
for _ in range(int(input())):
	n = int(input())
	print(a[n - 1] * 4 % m)


total = 2000001
arr = [0] * total
arr[3] = 4
mod = 10 ** 9 + 7
for i in range(4, total):
	res = arr[i - 1] + 2 * arr[i - 2]
	if i % 3 == 0:
		res += 4
	arr[i] = res % mod
for _ in range(int(input())):
	n = int(input())
	print(arr[n])


mod = 1000000007
dp = [(0, 0), (0, 0)]
for i in range(2, 2000001):
	dp.append(((max(dp[-1]) + 2 * max(dp[-2])) % mod, (dp[-1][0] + 2 * dp[-2][0] + 1) % mod))
for o in range(int(input())):
	print(max(dp[int(input()) - 1]) * 4 % mod)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	md = 10 ** 9 + 7
	mx = 2000005
	dp = [0] * mx
	dp[3] = dp[4] = 4
	for i in range(5, mx):
		if i % 3 == 0:
			dp[i] = (dp[i - 2] * 2 + dp[i - 1] + 4) % md
		else:
			dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % md
	for _ in range(II()):
		n = II()
		print(dp[n])
main()


from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7
dp = [0, 0, 0, 4, 4, 12]
for x in range(6, 2000001):
	if x % 6 == 3 or x % 6 == 5:
		dp.append((dp[-1] * 2 + 4) % mod)
	elif x % 6 == 4:
		dp.append((dp[-1] * 2 - 4) % mod)
	else:
		dp.append(dp[-1] * 2 % mod)
for _ in range(int(input())):
	print(dp[int(input())])


k = 2000005
l = [0] * k
l[1] = 0
l[2] = 0
l[3] = 4
l[4] = 4

def ans():
	mod = 1000000000.0 + 7
	for i in range(5, k):
		if i % 3 == 0:
			ans = l[i - 1] + 2 * l[i - 2] + 4
		else:
			ans = l[i - 1] + 2 * l[i - 2]
		ans = ans % mod
		l[i] = int(ans)
ans()
for _ in range(int(input())):
	n = int(input())
	print(l[n])


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
cache = [0] * (2 * 10 ** 6 + 1)
cache[3] = 4
cache[4] = 4

def solve(last):
	n = ri()
	if cache[n] != 0:
		print(cache[n])
		return last
	mod = 10 ** 9 + 7
	if n <= 2:
		print(0)
		return last
	elif n <= 4:
		print(4)
		return last
	else:
		(j, k) = last
		(a, b) = (cache[j], cache[k])
		for i in range(k + 1, n + 1):
			(a, b) = (b, (2 * a + b) % mod)
			if i % 3 == 0:
				b = (b + 4) % mod
			cache[i] = b
		last = [n - 1, n]
		print(b)
		return last
mode = 'T'
if mode == 'T':
	t = ri()
	last = [3, 4]
	for i in range(t):
		last = solve(last)
else:
	solve()


l = [0, 0, 0]
mod = int(1000000000.0) + 7
for i in range(3, 2000005):
	l.append((l[i - 1] + l[i - 2] * 2 + (4 if i % 3 == 0 else 0)) % mod)
t = int(input())
for _ in range(t):
	n = int(input())
	print(l[n])


from sys import stdin, stdout
from sys import maxsize

def solve():
	pass
val = 10 ** 9 + 7
dp = [0, 0, 0, 4]
for n in range(4, 2 * 10 ** 6 + 1):
	if n % 3 == 0:
		dp.append((dp[n - 1] + 2 * dp[n - 2] + 4) % val)
	else:
		dp.append((dp[n - 1] + 2 * dp[n - 2]) % val)
test = 1
test = int(input())
for t in range(0, test):
	n = int(input())
	print(dp[n])
	ans = solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 10 ** 9 + 7
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	ans = [0, 0, 0, 1, 1]
	up = 2000001
	(a, b) = (1, 1)
	for i in range(5, up + 1):
		(a, b) = (b, (a * 2 + b) % mod)
		if i % 3 == 0:
			b += 1
		ans.append(b)
	for _ in range(N()):
		print(ans[N()] * 4 % mod)
main()


inp = lambda : int(input())
inpm = lambda : map(int, input().split())
inpl = lambda : list(inpm())
l2mn = lambda _n, _m: [[0 for __ in range(_m)] for _ in range(_n)]
l2n = lambda _n: l2mn(_n, _n)
INF = int(1e+18)
MOD = int(1000000000.0) + 7
N = 2000009
dp = [0] * N
for i in range(3, N):
	dp[i] = (dp[i - 2] * 2 + dp[i - 1] + (1 if i % 3 == 0 else 0)) % MOD

def solve():
	n = inp()
	print(dp[n] * 4 % MOD)

def main():
	t = inp()
	for i in range(t):
		solve()
main()


(MOD, N) = (10 ** 9 + 7, 2 * 1001 * 1001)
dp = [0] * N
for i in range(3, N):
	dp[i] = (2 * dp[i - 2] + dp[i - 1] + 4 * (i % 3 == 0)) % MOD
for _ in range(int(input())):
	print(dp[int(input())])


t = int(input())
maxn = int(1000000.0 * 2 + 7)
mod = int(1000000000.0 + 7)
dp = list(bytearray(maxn))
for i in range(3, maxn):
	add4 = 4 if i % 3 == 0 else 0
	dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % mod + add4
for _ in range(t):
	n = int(input())
	print(dp[n])


t = int(input())
dp = [0 for i in range(2 * 10 ** 6 + 1)]
dp[0] = 0
dp[1] = 0
dp[2] = 0
dp[3] = 4
for i in range(4, 2 * 10 ** 6 + 1):
	if i % 3 == 0:
		dp[i] = (dp[i - 2] * 2 + dp[i - 1] + 4) % (10 ** 9 + 7)
	else:
		dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % (10 ** 9 + 7)
for _ in range(t):
	n = int(input())
	print(dp[n])