DP

다이나믹 프로그래밍  중 하나

리스트의 값이 점점 커지기 떄문에 답이 나머지를 출력하는거라면 중간에 계속 나눠준다

수의 크기가 작아지기 때문에 그게 더 빠르다 

더하기라서 가능 곱하기면 더 큰수로 나눠야함 

n1=1000000
a=[0]*n1
b=[0]*n1
c=[0]*n1
c1=[0]*n1

c2=[0]*n1
c3=[0]*n1
a[0]=c[0]=b[0]=c2[0]=1
mi=10**7
for n in range(1,n1):
    a[n]=(a[n-1]+b[n-1]+c[n-1])%mi
    b[n]=(b[n-1]+c2[n-1])%mi
    c3[n]=(c2[n-2]-c3[n-1])%mi
    c2[n]=(b[n]-c3[n])%mi
    c1[n]=(c[n-2]-c1[n-1])%mi
    c[n]=(a[n]-c1[n])%mi
    #a[n-3]=b[n-3]=c[n-3]=c1[n-3]=c2[n-3]=c3[n-3]=0
    
print((a[n1-1]+b[n1-1]+c[n1-1])%1000000)
#a[-1]+b[-1]+c[-1]