fork(1) download
  1. dp=[1]*(2*(10**6)+1)
  2. m=10**9+7
  3. for i in range(3,2*(10**6)+1):
  4. dp[i]=dp[i-1]+dp[i-2]*2
  5. dp[i]%=m
  6. o=[0]*(2*(10**6)+1)
  7. for i in range(3,2*(10**6)+1):
  8. o[i]=o[i-3]+dp[i-2]*4
  9. o[i]%=m
  10. for _ in range(input()):
  11. print o[input()]
  12.  
Success #stdin #stdout 1.33s 198000KB
stdin
7
1
2
3
4
5
100
2000000
stdout
0
0
4
4
12
990998587
804665184