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