Shared code

import bisect
from sys import stdin
input = stdin.readline

N = (int)(1e6 + 10)
MOD = (int)(1e9 + 7)

OneBlock = [1 for _ in range (N)]
TwoBlocks = [1 for _ in range (N)]

OneBlock[1] = 1
TwoBlocks[1] = 1

for i in range(2, N):
    OneBlock[i] = (2 * OneBlock[i - 1] + TwoBlocks[i - 1]) % MOD
    TwoBlocks[i] = (4 * TwoBlocks[i - 1] + OneBlock[i - 1]) % MOD

t = int(stdin.readline())
while (t > 0):
    n = int(stdin.readline())
    print((OneBlock[n] + TwoBlocks[n]) % MOD)
    t -= 1