Problem: You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:    * The string does not contain characters other than `A`, `C`, `G` and `T`.   * The string does not contain `AGC` as a substring.   * The condition above cannot be violated by swapping two adjacent characters once.

Submission attempts (in order):
N=int(input())
MOD=10**9+7
a=[[0 for i in range(64)] for j in range(101)]
a[3]=[1 for i in range(101)]
a[3][6],a[3][9],a[3][18]=0,0,0
for i in range(4,N+1):
  a[i][0]=(a[i-1][0]+a[i-1][16]+a[i-1][32]+a[i-1][48])%MOD
  a[i][1]=a[i][0]
  a[i][2]=a[i][0]
  a[i][3]=a[i][0]
  a[i][4]=(a[i-1][1]+a[i-1][17]+a[i-1][33]+a[i-1][49])%MOD
  a[i][5]=a[i][4]
  a[i][6]=0
  a[i][7]=a[i][4]
  a[i][8]=(a[i-1][2]+a[i-1][18]+a[i-1][34]+a[i-1][50])%MOD
  a[i][9]=0
  a[i][10]=a[i][8]
  a[i][11]=a[i][8]
  a[i][12]=(a[i-1][3]+a[i-1][19]+a[i-1][35]+a[i-1][51])%MOD
  a[i][13]=a[i][12]
  a[i][14]=a[i][12]
  a[i][15]=a[i][12]
  a[i][16]=(a[i-1][4]+a[i-1][20]+a[i-1][36]+a[i-1][52])%MOD
  a[i][17]=a[i][16]
  a[i][18]=0
  a[i][19]=a[i][16]
  a[i][20]=(a[i-1][5]+a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][21]=a[i][20]
  a[i][22]=(a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][23]=a[i][20]
  a[i][24]=(a[i-1][6]+a[i-1][22]+a[i-1][38]+a[i-1][54])%MOD
  a[i][25]=a[i][24]
  a[i][26]=a[i][24]
  a[i][27]=a[i][24]
  a[i][28]=(a[i-1][7]+a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][29]=a[i][28]
  a[i][30]=(a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][31]=a[i][28]
  a[i][32]=(a[i-1][8]+a[i-1][24]+a[i-1][40]+a[i-1][56])%MOD
  a[i][33]=a[i][32]
  a[i][34]=a[i][32]
  a[i][35]=a[i][32]
  a[i][36]=(a[i-1][9]+a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][37]=a[i][36]
  a[i][38]=(a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][39]=a[i][36]
  a[i][40]=(a[i-1][10]+a[i-1][26]+a[i-1][42]+a[i-1][58])%MOD
  a[i][41]=a[i][40]
  a[i][42]=a[i][40]
  a[i][43]=a[i][40]
  a[i][44]=(a[i-1][11]+a[i-1][27]+a[i-1][43]+a[i-1][59])%MOD
  a[i][45]=a[i][44]
  a[i][46]=a[i][44]
  a[i][47]=a[i][44]
  a[i][48]=(a[i-1][12]+a[i-1][28]+a[i-1][44]+a[i-1][60])%MOD
  a[i][49]=a[i][48]
  a[i][50]=a[i][48]
  a[i][51]=a[i][48]
  a[i][52]=(a[i-1][13]+a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][53]=a[i][52]
  a[i][54]=(a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][55]=a[i][52]
  a[i][56]=(a[i-1][14]+a[i-1][30]+a[i-1][46]+a[i-1][62])%MOD
  a[i][57]=a[i][56]
  a[i][58]=a[i][56]
  a[i][59]=a[i][56]
  a[i][60]=(a[i-1][15]+a[i-1][31]+a[i-1][47]+a[i-1][63])%MOD
  a[i][61]=a[i][60]
  a[i][62]=a[i][60]
  a[i][63]=a[i][60]
print(sum(a[N])%MOD)

N=int(input())
MOD=10**9+7
a=[[0 for i in range(64)] for j in range(101)]
a[3]=[1 for i in range(64)]
a[3][6],a[3][9],a[3][18]=0,0,0
for i in range(4,N+1):
  a[i][0]=(a[i-1][0]+a[i-1][16]+a[i-1][32]+a[i-1][48])%MOD
  a[i][1]=a[i][0]
  a[i][2]=a[i][0]
  a[i][3]=a[i][0]
  a[i][4]=(a[i-1][1]+a[i-1][17]+a[i-1][33]+a[i-1][49])%MOD
  a[i][5]=a[i][4]
  a[i][6]=0
  a[i][7]=a[i][4]
  a[i][8]=(a[i-1][2]+a[i-1][18]+a[i-1][34]+a[i-1][50])%MOD
  a[i][9]=0
  a[i][10]=a[i][8]
  a[i][11]=a[i][8]
  a[i][12]=(a[i-1][3]+a[i-1][19]+a[i-1][35]+a[i-1][51])%MOD
  a[i][13]=a[i][12]
  a[i][14]=a[i][12]
  a[i][15]=a[i][12]
  a[i][16]=(a[i-1][4]+a[i-1][20]+a[i-1][36]+a[i-1][52])%MOD
  a[i][17]=a[i][16]
  a[i][18]=0
  a[i][19]=a[i][16]
  a[i][20]=(a[i-1][5]+a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][21]=a[i][20]
  a[i][22]=(a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][23]=a[i][20]
  a[i][24]=(a[i-1][6]+a[i-1][22]+a[i-1][38]+a[i-1][54])%MOD
  a[i][25]=a[i][24]
  a[i][26]=a[i][24]
  a[i][27]=a[i][24]
  a[i][28]=(a[i-1][7]+a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][29]=a[i][28]
  a[i][30]=(a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][31]=a[i][28]
  a[i][32]=(a[i-1][8]+a[i-1][24]+a[i-1][40]+a[i-1][56])%MOD
  a[i][33]=a[i][32]
  a[i][34]=a[i][32]
  a[i][35]=a[i][32]
  a[i][36]=(a[i-1][9]+a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][37]=a[i][36]
  a[i][38]=(a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][39]=a[i][36]
  a[i][40]=(a[i-1][10]+a[i-1][26]+a[i-1][42]+a[i-1][58])%MOD
  a[i][41]=a[i][40]
  a[i][42]=a[i][40]
  a[i][43]=a[i][40]
  a[i][44]=(a[i-1][11]+a[i-1][27]+a[i-1][43]+a[i-1][59])%MOD
  a[i][45]=a[i][44]
  a[i][46]=a[i][44]
  a[i][47]=a[i][44]
  a[i][48]=(a[i-1][12]+a[i-1][28]+a[i-1][44]+a[i-1][60])%MOD
  a[i][49]=a[i][48]
  a[i][50]=a[i][48]
  a[i][51]=a[i][48]
  a[i][52]=(a[i-1][13]+a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][53]=a[i][52]
  a[i][54]=(a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][55]=a[i][52]
  a[i][56]=(a[i-1][14]+a[i-1][30]+a[i-1][46]+a[i-1][62])%MOD
  a[i][57]=a[i][56]
  a[i][58]=a[i][56]
  a[i][59]=a[i][56]
  a[i][60]=(a[i-1][15]+a[i-1][31]+a[i-1][47]+a[i-1][63])%MOD
  a[i][61]=a[i][60]
  a[i][62]=a[i][60]
  a[i][63]=a[i][60]
print(sum(a[N])%MOD)

Verdicts: Wrong Answer

Accepted