Problem:
 Score : 400 points    Problem Statement 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.       Notes A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T .  For example, the substrings of ATCODER include TCO , AT , CODER , ATCODER and (the empty string), but not AC .      Constraints  3 \leq N \leq 100         Input Input is given from Standard Input in the following format:  N       Output Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7 .        Sample Input 1 3      Sample Output 1 61  There are 4^3 = 64 strings of length 3 that do not contain characters other than A , C , G and T . Among them, only AGC , ACG and GAC violate the condition, so the answer is 64 - 3 = 61 .       Sample Input 2 4      Sample Output 2 230       Sample Input 3 100      Sample Output 3 388130742  Be sure to print the number of strings modulo 10^9+7 .

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7


def is_ok(last4):
    for j in range(4):
        t = list(last4)
        if j != 3:
            t[j], t[j + 1] = t[j + 1], t[j]
        if 'AGC' in ''.join(t):
            return False
    return True


def rec(length, last3):
    if last3 in m[length]:
        return m[length][last3]

    if length == n:
        return 1

    res = 0
    for c in 'ACGT':
        if is_ok(last3 + c):
            res += rec(length + 1, last3[1:] + c)
            res %= mod

    m[length][last3] = res
    return res


n = int(input())
m = [dict() for _ in range(n + 1)]
print(rec(0, 'zzz'))

Solution (Python):
n = int(input())
MOD = 10**9 + 7

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n - 2)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[0][i][j][k] = 1
dp[0][0][2][1] = 0
dp[0][0][1][2] = 0
dp[0][2][0][1] = 0

for i in range(n - 3):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    dp[i + 1][k][l][m] += dp[i][j][k][l]
                    dp[i + 1][k][l][m] %= MOD
                    if j == 0 and k == 2 and m == 1:
                        dp[i + 1][k][l][m] = 0
                    elif j == 0 and l == 2 and m == 1:
                        dp[i + 1][k][l][m] = 0
                dp[i + 1][0][2][1] = 0
                dp[i + 1][0][1][2] = 0
                dp[i + 1][2][0][1] = 0
print(sum(sum(sum(dp[n - 3], []), [])) % MOD)

Solution (Python):
N = int(input())
mod = 10 ** 9 + 7


last_a = [1, 4, 16]
last_g = [1, 4, 15]
last_c = [1, 4, 14]
last_t = [1, 4, 16]
for i in range(3, N):
    last_a.append(last_a[i - 1] + last_g[i - 1] + last_c[i - 1] + last_t[i - 1])
    last_g.append(last_a[i - 1] + last_g[i - 1] + (last_c[i - 1] - last_a[i - 2] + last_g[i - 3]) + last_t[i - 1])
    last_c.append((last_a[i - 1] - last_g[i - 2]) + (last_g[i - 1] - last_a[i - 2] - (last_a[i - 3] * 2)) + last_c[i - 1] + (last_t[i - 1] - last_a[i - 3]))
    last_t.append(last_a[i - 1] + last_g[i - 1] + last_c[i - 1] + last_t[i - 1])

N -= 1
print((last_a[N] + last_g[N] + last_c[N] + last_t[N]) % mod)

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ in range(101)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).find('AGC') != -1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ in range(101)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).find('AGC') != -1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(last3 + c):
            
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Solution (Python):
N = int(input())
MOD = 10 ** 9 + 7
memo = [{} for _ in range(101)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).find('AGC') != -1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(last3 + c):
            
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ in range(101)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).find('AGC') != -1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Solution (Python):

N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Solution (Python):
from itertools import product
from collections import defaultdict
MOD = 10**9 + 7
N = int(input())
D, L = 4, 3
AGC = list(range(L))
ATGC = range(D)
cur = defaultdict(lambda: 1)

flip = lambda x, n: x[:n] + [x[n+1],x[n]] + x[n+2:]
prohibited1 = [tuple(AGC)] + [tuple(flip(AGC,i)) for i in range(L-1)]
prohibited2 = ({(X,) + p for p in prohibited1 for X in ATGC} | 
             {tuple(flip([X]+AGC,0)) for X in ATGC} |
             {tuple(flip(AGC+[X],L-1)) for X in ATGC})
for p in prohibited1:
    cur[p] = 0
for _ in range(L,N):
    prev = cur
    cur = defaultdict(int)
    for recent in product(ATGC, repeat=L+1):
        if recent in prohibited2:
            continue
        else:
            cur[recent[1:]] += prev[recent[:-1]]
    for latest in product(ATGC, repeat=L):
        cur[latest] %= MOD

ans = sum(cur.values()) % MOD
if N < L:
    print(D**N)
elif N == L:
    print(D**L - len(prohibited1))
else:
    print(ans)

Solution (Python):
from itertools import product
from collections import defaultdict
MOD = 10**9 + 7
N = int(input())

A=0; C=1; G=2; T=3
cur = defaultdict(lambda: 1)
cur[(A,G,C)] = cur[(G,A,C)] = cur[(A,C,G)] = 0
for _ in range(3,N):
    prev = cur
    cur = defaultdict(int)
    for (i,j,k,l) in product(range(4),repeat=4):
        if ((j,k,l)==(A,G,C) or (j,k,l)==(G,A,C) or (i,k,l)==(A,G,C) or
            (i,j,l)==(A,G,C) or (j,k,l)==(A,C,G)):
            continue
        else:
            cur[(j,k,l)] += prev[(i,j,k)]
    for ijk in product(range(4),repeat=3):
        cur[ijk] %= MOD

ans = sum(cur.values()) % MOD
if N <= 3:
    print([1,4,16,61][N])
else:
    print(ans)

Solution (Python):

p=10**9+7
N=int(input())

a=[[0 for i in range(101)] for x in range(64)]


for x in range(64):
    if x in [6,9,33]:
        a[x][3]=0
    else:
        a[x][3]=1


for i in range(3,N):
    for x in range(64):
        if x in [9,33,6]: 
            a[x][i+1]=0
        elif x in [25,41,57,37,45]: 
            a[x][i+1]=(a[x//4+16][i]+a[x//4+32][i]+a[x//4+48][i])%p
        else:
            a[x][i+1]=(a[x//4][i]+a[x//4+16][i]+a[x//4+32][i]+a[x//4+48][i])%p

ans=0
for x in range(64):
    ans+=a[x][N]
print(ans%p)

Solution (Python):
from itertools import product
MOD = 10**9 + 7
N = int(input())

A=0; C=1; G=2; T=3
cur = [[[1]*4 for j in range(4)] for k in range(4)]
for i in range(4):
    cur[A][G][C] = cur[G][A][C] = cur[A][C][G] = 0

for _ in range(3,N):
    prev = cur
    cur = [[[0]*4 for j in range(4)] for k in range(4)]
    for i, j, k in product(range(4),repeat=3):
        if (j==A and k==G) or (j==G and k==A) or (i==A and k==G) or (i==A and j==G):
            for l in [A,G,T]:
                cur[j][k][l] += prev[i][j][k]
        elif j==A and k==C:
            for l in [A,C,T]:
                cur[j][k][l] += prev[i][j][k]
        else:
            for l in range(4):
                cur[j][k][l] += prev[i][j][k]
    for i, j, k in product(range(4),repeat=3):
        cur[i][j][k] %= MOD

ans = sum(sum(sum(cur[i][j]) for j in range(4)) for i in range(4)) % MOD
print(ans)

Solution (Python):
n = int(input())

dp = [[0]*16 for i in range(n)]
for j in range(16):
  dp[1][j] = 1

for i in range(2,n):
  for j in range(16):
    k = j//4
    dp[i][j] = dp[i-1][k]+dp[i-1][k+4]+dp[i-1][k+8]+dp[i-1][k+12]
    if j == 1:
      dp[i][j] -= dp[i-1][8]
    elif j == 6:
      dp[i][j] -= dp[i-1][1]
    elif j == 9:
      dp[i][j] -= dp[i-1][2]+dp[i-2][2]+dp[i-2][3]
    elif j == 13:
      dp[i][j] -= dp[i-2][2]
    else:
      continue

count = 0
for j in range(16):
  count += dp[n-1][j]

print(count%1000000007)

Solution (Python):
n=int(input())
mod=10**9+7

table=[1]*(64)
data=[[] for i in range(64)]
for i in range(64):
    z=i
    num=""
    for j in range(3):
        if i//(4**(2-j))==1:
            num+="1"
            i%=(4**(2-j))
        elif i//(4**(2-j))==2:
            num+="2"
            i%=(4**(2-j))*2
        elif i//(4**(2-j))==3:
            num+="3"
            i%=(4**(2-j))*3
        else:
            num+="0"
    for j in range(4):
        a=num+str(j)
        b=a[1]+a[0]+a[2]+a[3]
        c=a[0]+a[2]+a[1]+a[3]
        d=a[0]+a[1]+a[3]+a[2]
        if "021" in a or "021" in b or "021" in c or "021" in d:
            continue
        else:
            data[z].append(16*int(a[1])+4*int(a[2])+int(a[3]))
table[6]=0
table[9]=0
table[33]=0
for i in range(n-3):
    h=[0]*64
    for j in range(64):
        for u in data[j]:
            h[u]=(h[u]+table[j])%mod
    table=h
ans=0
for i in range(64):
    ans=(ans+table[i])%mod
print(ans)

Solution (Python):
n = int(input())

dp = [[0]*16 for i in range(n)]
for j in range(16):
  if j in [1,6,9]:
    dp[1][j] = 1
  else:
    dp[1][j] = 1

for i in range(2,n):
  for j in range(16):
    k = j//4
    dp[i][j] = dp[i-1][k]+dp[i-1][k+4]+dp[i-1][k+8]+dp[i-1][k+12]
    if j == 1:
      dp[i][j] -= dp[i-1][8]
    elif j == 6:
      dp[i][j] -= dp[i-1][1]
    elif j == 9:
      dp[i][j] -= dp[i-1][2]+dp[i-2][2]+dp[i-2][3]
    elif j == 13:
      dp[i][j] -= dp[i-2][2]
    else:
      continue

count = 0
for j in range(16):
  count += dp[n-1][j]

print(count%1000000007)

Solution (Python):
N = int(input())
mod = 10 ** 9 + 7

if N < 3 :
    print(0)
else :
    
    
    
    
    dp = [1] * 64
    dp[6] = dp[9] = dp[18] = 0
     
    for _ in range(N-3) :
        dp_ = [0] * 64
        for i in range(64) :
            for j in range(4) :
                if j == 2 and i in [1, 4, 5, 7, 13] :
                    continue
                ni = (i*4+j)%64
                dp_[ni] += dp[i]
                dp_[ni] %= mod
        dp = dp_
        dp[6] = dp[9] = dp[18] = 0
        
    print(sum(dp) % mod)

Solution (Python):
mod = 10**9 + 7
n = int(input())
caps = ['A','G','C','T']
agct = []
for a in caps:
    for b in caps:
        for c in caps:
            if a+b+c not in ['AGC','GAC','ACG']:
                agct.append(a+b+c)

ngs = set(['AGC','GAC','ACG','AGGC','ATGC','AAGC','AGAC','AGTC'])           
dic = {}
for trio in agct:
        dic[trio] =1
for _ in range(n-3):
    dic2 = {x:0 for x in agct}
    for trio in agct:
        for cap in caps:
            quad = trio + cap
            if (not quad in ngs) and (not quad[1:] in ngs):
                dic2[quad[1:]] += dic[trio]
    dic = dic2

print(sum(dic.values())%mod)

Solution (Python):
N=int(input())
M=10**9+7
batu4=['AGG','AGT','ACG','ATG']
batu3=['AGC','ACG','GAC']
l=['A','G','C','T']
lx=['A','G','T']

def hash_index(s):
  num=0
  length=len(s)
  for i in range(length):
    letter=s[length-1-i]
    if letter=='A': k=0
    elif letter=='G': k=1
    elif letter=='C': k=2
    else: k=3
    num=num+k*4**i
  return num
hash_table=[]
for l1 in l:
  for l2 in l:
    for l3 in l:
      s_a=l1+l2+l3
      if s_a in batu3:
        hash_table.append([set()])
      elif s_a in batu4:
        s=set()
        for l4 in lx:
          s.add(l2+l3+l4)
        hash_table.append(s)
      else:
        s=set()
        for l4 in l:
            s_b=l2+l3+l4
            if not s_b in batu3:
              s.add(s_b)
        hash_table.append(s)
l_p=[1]*64
for l1 in l:
  for l2 in l:
    for l3 in l:
      s=l1+l2+l3
      if s in batu3:
        l_p[hash_index(s)]=0
  

for i in range(N-3):
  l_current=[0]*64
  for j in range(64):
    s_s=hash_table[j]
    for s in s_s:
      if not len(s)==0:
      	l_current[hash_index(s)]=(l_p[j]+l_current[hash_index(s)])%M
  l_p=l_current

num=0
for n in l_p:
  num=(num+n)%M
print(num)

Solution (Python):
n = int(input())
mod = 10**9+7
d = [{},{}]

def judge(s):
    if s[:3] == 'AGC' or s[:3] == 'GAC' or s[:3] == 'ACG' or s[0]+s[2:]=='AGC' or s[:2]+s[3]=='AGC':
        return False
    return True

d[0] = {'TTT':1}

for i in range(n):
    d[(i+1)%2] = {}
    for ne in 'AGCT':
        for elt in d[i%2]:
            if judge(ne+elt[:3]):
                if ne+elt[:2] in d[(i+1)%2]:
                    d[(i+1)%2][ne+elt[:2]] = (d[(i+1)%2][ne+elt[:2]]+d[i%2][elt])%mod
                else:
                    d[(i+1)%2][ne+elt[:2]] = d[i%2][elt]
res = 0
for e in d[n%2]:
    res = (res + d[n%2][e])%mod
print(res%mod)

Solution (Python):
n = int(input())
mod = 10**9+7
d = [{},{}]

def judge(s):
    if s[:3] == 'AGC' or s[:3] == 'GAC' or s[:3] == 'ACG' or s[0]+s[2:]=='AGC' or s[:2]+s[3]=='AGC':
        return False
    return True

d[0] = {'TTT':1}

for i in range(n):
    d[(i+1)%2] = {}
    for ne in 'AGCT':
        for elt in d[i%2]:
            if judge(ne+elt[:3]):
                if ne+elt[:2] in d[(i+1)%2]:
                    d[(i+1)%2][ne+elt[:2]] = (d[(i+1)%2][ne+elt[:2]]+d[i%2][elt])%mod
                else:
                    d[(i+1)%2][ne+elt[:2]] = d[i%2][elt]
res = 0
for e in d[n%2]:
    res = (res + d[n%2][e])%mod
print(res%mod)

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N + 1)]


def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i - 1], t[i] = t[i], t[i - 1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))

Solution (Python):
N = int(input())
M = 10**9+7

memo = [{} for _ in range(N+1)] 

def ok(last4):

    for i in range(4):
        t = list(last4)
        if  i >= 1:
            t[i-1],t[i] = t[i],t[i-1]   
        if "".join(t).count("AGC") >= 1:
            return False
    return True

def dfs(cur, last3):    


    if last3 in memo[cur]:  
        return memo[cur][last3] 
    if cur == N:    
        return 1    
    ret = 0 
    for c in "ACGT":
        if ok(last3+c): 
            ret = (ret+dfs(cur+1, last3[1:]+c)) % M
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Solution (Python):
N = int(input())

C = 10**9+7
n = 5
num = max(N+1, 6)
L = [0 for i in range(num)]
X = [0 for i in range(num)]
Y = [0 for i in range(num)]
Z = [0 for i in range(num)]
W = [0 for i in range(num)]
G = [0 for i in range(num)]
L[3] = 61
L[4] = 230
X[3] = 3
X[4] = 12
Y[3] = 4
Y[4] = 16
Z[3] = 4
Z[4] = 15
W[3] = 3
W[4] = 12
W[5] = 48
G[3] = 15
G[4] = 58
while n <= N:
    L[n] = 4*L[n-1] - (X[n-1]+Y[n-1]+Z[n-1]+W[n-1])
    G[n] = L[n-1]-X[n-1]
    X[n] = L[n-2]-G[n-2]
    Y[n] = L[n-2]
    Z[n] = L[n-2]-X[n-2]
    if n > 5:
        W[n] = L[n-3]*3
    n += 1

print(L[N]%C)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    dp = [[0] * 4 if i != 3 else [1] * 4 for i in range(N+3)]
    MOD = int(1e9) + 7
    for i in range(4, N+3):
        sum_pre = sum(dp[i-1]) % MOD
        
        dp[i][0] = sum_pre
        
        dp[i][1] = (sum_pre - dp[i-2][0] - dp[i-2][2] - dp[i-3][0] * 3) % MOD
        
        dp[i][2] = (sum_pre - dp[i-2][0] + dp[i-3][2]) % MOD
        
        dp[i][3] = sum_pre
    print(sum(dp[-1]) % MOD)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
mod = 10**9 + 7
dp = [[[[0 for _ in range(n+1)] for _ in range(4)]for _ in range(4)] for _ in range(4)]

for i in range(4):
  for j in range(4):
    for k in range(4):
      if((i == 0 and j == 1 and k == 2) or (i == 0 and j == 2 and k == 1) or (i == 1 and j == 0 and k == 2)):
        pass
      else:
        dp[i][j][k][3] = 1
        
for length in range(3, n):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if(j == 0 and k == 2):
          dp[j][k][0][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][2][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][3][length + 1] += (dp[i][j][k][length])%mod
        elif((i == 0 and k == 1) or (i == 0 and j == 1) or (j == 0 and k == 1) or (j == 1 and k == 0)):
          dp[j][k][0][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][1][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][3][length + 1] += (dp[i][j][k][length])%mod
        else:
          dp[j][k][0][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][1][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][2][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][3][length + 1] += (dp[i][j][k][length])%mod
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans += dp[i][j][k][n]
      
print(ans%mod)

Solution (Python):
n = int(input())
mod = 10 ** 9 + 7
now = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(4)]
now[3][3][3][3] = 1
for _ in range(n):
  last = now
  now = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(4)]
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          for m in range(4):
            now[j][k][l][m] += last[i][j][k][l]
            now[j][k][l][m] %= mod
  for h in range(4):
    now[h][0][1][2] = 0
    now[h][1][0][2] = 0
    now[h][0][2][1] = 0
    now[0][h][1][2] = 0
    now[0][1][h][2] = 0
ans = 0
for j in range(4):
  for k in range(4):
    for l in range(4):
      for m in range(4):
        ans += now[j][k][l][m]
        ans %= mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    N=int(input())
    dp=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    
    NG={(0,1,2),(1,0,2),(0,2,1)}
    from itertools import product
    for i,j,k in product(range(4),repeat=3):
        if (i,j,k) in NG: continue
        dp[3][i][j][k]=1
    
    for n in range(4,N+1):
        for i,j,k,l in product(range(4),repeat=4):
            if dp[n-1][i][j][k]==0: continue
            if (j,k,l) in NG: continue
            if (i,j,l)==(0,1,2): continue
            if (i,k,l)==(0,1,2): continue
            dp[n][j][k][l]+=dp[n-1][i][j][k]
            dp[n][j][k][l]%=MOD
    
    ans=0
    for i,j,k in product(range(4),repeat=3):
        ans+=dp[N][i][j][k]
    print(ans%MOD)

resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    N=int(input())
    dp=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    
    NG={(0,1,2),(1,0,2),(0,2,1)}
    from itertools import product
    for i,j,k in product(range(4),repeat=3):
        if (i,j,k) in NG: continue
        dp[3][i][j][k]=1
    
    for n in range(4,N+1):
        for i,j,k,l in product(range(4),repeat=4):
            if dp[n-1][i][j][k]==0: continue
            if (j,k,l) in NG: continue
            if (i,j,l)==(0,1,2): continue
            if (i,k,l)==(0,1,2): continue
            dp[n][j][k][l]+=dp[n-1][i][j][k]
    
    ans=0
    for i,j,k in product(range(4),repeat=3):
        ans+=dp[N][i][j][k]
    print(ans%MOD)

resolve()

Solution (Python):
import functools
import itertools
import collections

l = list("ACGT")

@functools.lru_cache(maxsize=None)
def f(d, sl, e):
    if e == d:
        return 1
    else:
        cnt = 0
        for v in l:
            tsl = collections.deque(sl)
            if len(sl) == 4:
                tsl.popleft()
            tsl.append(v)
            ts = "".join(tsl)
            if len(ts) >= 3 and (ts[-3:] == "AGC" or ts[-3:] == "GAC" or ts[-3:] == "ACG"):
                continue
            if len(ts) >= 4 and ts[0] == "A" and ts[2:] == "GC":
                continue
            if len(ts) >= 4 and ts[:2] == "AG" and ts[3] == "C":
                continue
            cnt += f(d + 1, ts, e)
        return cnt


def slove():
    import sys
    input = sys.stdin.readline
    e = int(input().rstrip('\n'))
    sl = []
    print(f(0, "".join(sl), e) % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()

Solution (Python):

n = int(input())
mod = 10 ** 9 + 7
now = [[[[0 for _ in range(4)]
            for _ in range(4)]
            for _ in range(4)]
            for _ in range(4)]
now[3][3][3][3] = 1
for _ in range(n):
  last = now
  now = [[[[0 for _ in range(4)]
              for _ in range(4)]
              for _ in range(4)]
              for _ in range(4)]
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          for m in range(4):
            now[j][k][l][m] += last[i][j][k][l]
            now[j][k][l][m] %= mod
  for j in range(4):
    now[j][0][1][2] = 0
    now[j][1][0][2] = 0
    now[j][0][2][1] = 0
  for k in range(4):
    now[0][k][1][2] = 0
  for l in range(4):
    now[0][1][l][2] = 0
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        ans += now[i][j][k][l]
print(ans % mod)

Solution (Python):
N = int(input())

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]







dp[0][3][3][3] = 1
MOD = 10**9 + 7

for i in range(N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                
                    
                for add in range(4): 
                    
                    if add == 2 and j == 1 and k == 0:
                        continue
                    if add == 2 and j == 0 and k == 1:
                        continue
                    if add == 1 and j == 2 and k == 0:
                        continue
                    if add == 2 and j == 1 and l == 0:
                        continue
                    if add == 2 and k == 1 and l == 0:
                        continue
                    
                    
                    dp[i+1][add][j][k] += dp[i][j][k][l]
                    dp[i+1][add][j][k] %= MOD

ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N][j][k][l]
            ans %= MOD

print(ans)

Solution (Python):
N = int(input())

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]







dp[0][3][3][3] = 1
MOD = 10**9 + 7

for i in range(N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if dp[i][j][k][l] == 0: 
                    continue
                for add in range(4): 
                    
                    if add == 2 and j == 1 and k == 0:
                        continue
                    if add == 2 and j == 0 and k == 1:
                        continue
                    if add == 1 and j == 2 and k == 0:
                        continue
                    if add == 2 and j == 1 and l == 0:
                        continue
                    if add == 2 and k == 1 and l == 0:
                        continue
                    
                    
                    dp[i+1][add][j][k] += dp[i][j][k][l]
                    dp[i+1][add][j][k] %= MOD

ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N][j][k][l]
            ans %= MOD

print(ans)

Solution (Python):
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

MOD = int(1e9) + 7

acgt = ["A", "C", "G", "T"]
changed = list(map(lambda pat: re.compile(pat), [r"AGC", r"GAC", r"ACG", r"A.GC", r"AG.C"]))
abcl = [ a+b+c for a in acgt for b in acgt for c in acgt]

dp = {}
for now in abcl:
    if any(map(lambda ch: ch.search(now), changed)):
        dp[now] = 0
    else:
        dp[now] = 1

N -= 3

while N > 0:
    dpNow = {}
    for abc in abcl:
        abc = abc[:min(N, 3)]
        dpNow[abc] = 0
        for key, value in dp.items():
            now = key + abc
            if not any(map(lambda ch: ch.search(now), changed)):
                dpNow[abc] += value
                dpNow[abc] %= MOD
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Solution (Python):
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

MOD = int(1e9) + 7

acgt = ["A", "C", "G", "T"]
changed = list(map(lambda pat: re.compile(pat), [r"AGC", r"GAC", r"ACG", r"A.GC", r"AG.C"]))
abcl = [ a+b+c for a in acgt for b in acgt for c in acgt]

dp = {}
for now in abcl:
    if any(map(lambda ch: ch.search(now), changed)):
        dp[now] = 0
    else:
        dp[now] = 1

N -= 3

while N > 0:
    dpNow = {}
    for abc in abcl:
        abc = abc[:min(N, 3)]
        dpNow[abc] = 0
        for key, value in dp.items():
            now = key + abc
            if not any(map(lambda ch: ch.search(now), changed)):
                dpNow[abc] += value
                dpNow[abc] %= MOD
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Solution (Python):
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

MOD = int(1e9) + 7

acgt = ["A", "C", "G", "T"]
changed = list(map(lambda pat: re.compile(pat), [r".*AGC", r".*GAC", r".*ACG", r".*A.GC", r".*AG.C"]))
abcl = [ a+b+c for a in acgt for b in acgt for c in acgt]

dp = {}
for now in abcl:
    if any(map(lambda ch: ch.match(now), changed)):
        dp[now] = 0
    else:
        dp[now] = 1

N -= 3

while N > 0:
    dpNow = {}
    for abc in abcl:
        abc = abc[:min(N, 3)]
        dpNow[abc] = 0
        for key, value in dp.items():
            now = key + abc
            if not any(map(lambda ch: ch.match(now), changed)):
                dpNow[abc] += value
                dpNow[abc] %= MOD
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Solution (Python):
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

MOD = int(1e9) + 7

acgt = ["A", "C", "G", "T"]
changed = [".*AGC", ".*GAC", ".*ACG", ".*A.GC", ".*AG.C"]
abcl = [ a+b+c for a in acgt for b in acgt for c in acgt]

dp = {}
for now in abcl:
    if any(map(lambda ch: re.match(ch, now), changed)):
        dp[now] = 0
    else:
        dp[now] = 1

N -= 3

while N > 0:
    dpNow = {}
    for abc in abcl:
        abc = abc[:min(N, 3)]
        dpNow[abc] = 0
        for key, value in dp.items():
            now = key + abc
            if not any(map(lambda ch: re.match(ch, now), changed)):
                dpNow[abc] += value
                dpNow[abc] %= MOD
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Solution (Python):
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

acgt = ["A", "C", "G", "T"]
changed = [".*AGC", ".*GAC", ".*ACG", ".*A.GC", ".*AG.C"]



dp = {}
for a in acgt:
    for b in acgt:
        for c in acgt:
            now = a+b+c
            
            if any(map(lambda ch: re.match(ch, now), changed)):
                dp[now] = 0
            else:
                dp[now] = 1

N -= 3

MOD = int(1e9) + 7

while N > 0:
    dpNow = {}
    for a in acgt:
        for b in acgt:
            for c in acgt:
                abc = (a + b + c)[:min(N, 3)]
                dpNow[abc] = 0
                for key, value in dp.items():
                    now = key + abc

                    if not any(map(lambda ch: re.match(ch, now), changed)):
                        dpNow[abc] += value
                        dpNow[abc] %= MOD
                        
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Solution (Python):
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

acgt = ["A", "C", "G", "T"]
changed = [".*GAC.*", ".*ACG.*", ".*A.GC.*", ".*AG.C.*"]
bad = ".*AGC"



dp = {}
for a in acgt:
    for b in acgt:
        for c in acgt:
            now = a+b+c
            
            if re.match(bad, now):
                dp[now] = 0
            elif any(map(lambda ch: re.match(ch, now), changed)):
                dp[now] = 0
            else:
                dp[now] = 1

N -= 3

MOD = int(1e9) + 7

while N > 0:
    dpNow = {}
    for a in acgt:
        for b in acgt:
            for c in acgt:
                abc = (a + b + c)[:min(N, 3)]
                dpNow[abc] = 0
                for key, value in dp.items():
                    now = key + abc

                    if re.match(bad, now):
                        ()
                    elif any(map(lambda ch: re.match(ch, now), changed)):
                        ()
                    else:
                        dpNow[abc] += value
                        dpNow[abc] %= MOD
                        
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)