fork(2) download
copy 
  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
comments (?)
stdin
copy 
7
1
2
3
4
5
100
2000000
stdout
copy 
0
0
4
4
12
990998587
804665184
https://ideone.com/qDpu3b
language:
Python (cpython 2.7.16)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!