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):
"""
?AGC
AG?C
A?GC
?ACG
?CAG
"""

n = int(input())


import itertools
l = ["A", "G", "C", "T"]
pl = itertools.product(l, repeat=3)

dic = dict()
dic2 = dict()
from collections import defaultdict
ng_list = defaultdict(int)


for idx, p in enumerate(pl):
    dic[idx] = p
    dic2[p] = idx

pl = itertools.product(l, repeat=4)
for idx, p in enumerate(pl):
    if p[1] == "A" and p[2] == "G" and p[3] == "C":
        ng_list[p] = 1
    elif p[0] == "A" and p[1] == "G" and p[3] == "C":
        ng_list[p] = 1
    elif p[1] == "A" and p[2] == "C" and p[3] == "G":
        ng_list[p] = 1
    elif p[1] == "G" and p[2] == "A" and p[3] == "C":
        ng_list[p] = 1
    elif p[0] == "A" and p[2] == "G" and p[3] == "C":
        ng_list[p] = 1

pl = itertools.product(l, repeat=3)
dic3 = dict()
dic4 = dict()
for idx, p in enumerate(pl):
    dic3[idx] = p
    dic4[p] = idx

dp = [[0 for _ in range(4**3)] for _ in range(n+1)]
dp[0][dic4[("T", "T", "T")]] = 1
MOD = 10 ** 9 + 7
for i in range(n):
    for j in range(4**3):
        for k in l:
            if ng_list[dic3[j] + (k,)] == 0:
                dp[i+1][dic4[dic3[j][1:] + (k,)]] += dp[i][j]
                dp[i+1][dic4[dic3[j][1:] + (k,)]] %= MOD

print(sum(dp[-1]) % MOD)

Solution (Python):


from collections import defaultdict

MOD = 10**9+7
N = int(input())
charactors = ['A', 'G', 'C', 'T']


dp = [defaultdict(int) for _ in range(N+1)]


dp[0]['ZZZ'] = 1


def check(s, c):
    if c=='C':
        if s[1:]=='AG' or s[1:]=='GA' or \
            (s[0]=='A' and (s[1]=='G' or s[2]=='G')):
            return False
        else:
            return True
    elif c=='G':
        if s[1:]=='AC':
            return False
        else:
            return True
    else:
        return True

for i in range(N):
    for s in dp[i].keys():
        for c in charactors:
            
            if check(s, c): 
                dp[i+1][s[1:]+c] += dp[i][s]
                dp[i+1][s[1:]+c] %= MOD

print(sum(dp[N].values())%MOD)

Solution (Python):
import numpy as np
N = int(input())
dp = np.zeros((N+1, 5, 5, 5), dtype = np.int64)


p = 10**9 + 7
dp[0, 0, 0, 0] = 1
for n in range(N):
  for i in range(5):
    for j in range(5):
      for k in range(5):
        for l in range(1, 5):
          if j == 1 and k == 3 and l == 2:continue 
          if j == 3 and k == 1 and l == 2:continue 
          if j == 1 and k == 2 and l == 3:continue 
          if i == 1 and k == 3 and l == 2:continue 
          if i == 1 and j == 3 and l == 2:continue 
          dp[n+1, j, k, l] += dp[n, i, j, k]
          dp[n+1, j, k, l] %= p
ans = 0
for i in range(1, 5):
  for j in range(1, 5):
    for k in range(1, 5):
      ans += dp[N, i, j, k]
      ans %=  p
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()

dp = [[[[0 for _ in  range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i == 0 and j == 2 and k == 1 or \
                i == 0 and j == 1 and k == 2 or \
                i == 2 and j == 0 and k == 1:
                dp[3][i][j][k] = 0
            else:
                dp[3][i][j][k] = 1

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

ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[-1][i][j][k]

print (ans % MOD)

Solution (Python):
N=int(input())
mod=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 'AGCT':
        if ok(last3+c):
            ret+=dfs(cur+1,last3[1:]+c)
            ret%=mod
    memo[cur][last3]=ret
    return ret
print(dfs(0,'TTT'))

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007



def like_agc3(www):
	lkagc=['AGC','ACG','GAC']
	return  not (www in lkagc)

def like_agc(www,w):
	if www[0]+www[2]+w =='AGC':
		return False
	if www[0]+www[1]+w == 'AGC':
		return False
	return like_agc3(www[1]+www[2]+w)
	

def main():
	ll=['AAA','AAC','AAG','AAT','ACA',       'ACC', 'ACG', 'ACT',"AGA", "AGC",     "AGG", "AGT", "ATA", "ATC" ,"ATG",     "ATT", "CAA", "CAC", "CAG", "CAT",     "CCA", "CCC", "CCG", "CCT", "CGA" , "CGC" ,"CGG" ,"CGT" ,"CTA" ,"CTC" , "CTG" ,"CTT" ,"GAA" ,"GAC" ,"GAG" , "GAT" ,"GCA" ,"GCC" ,"GCG" ,"GCT" , "GGA" ,"GGC" ,"GGG" ,"GGT" ,"GTA" , "GTC" ,"GTG" ,"GTT" ,"TAA" ,"TAC" , "TAG" ,"TAT" ,"TCA" ,"TCC" ,"TCG" , "TCT" ,"TGA" ,"TGC" ,"TGG" ,"TGT" , "TTA" ,"TTC" ,"TTG" ,"TTT"]
	dll={}
	for i,w in enumerate(ll):
		dll[w]=i
	
	n = int(input())
	
	
	
	
	
	
	cll='AGCT'
	cc = [1 if like_agc3(w) else 0 for w in ll]
	for i in range(4,n+1):
		
		ncc=[0]*64
		for word in ll:
			for c in cll:
				if like_agc(word, c):
					next_word=word[1:]+c
					ncc[dll[next_word]]+=cc[dll[word]]
					ncc[dll[next_word]] %= mod
		cc=ncc
	ret = sum(cc) % mod
	print(ret)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import copy
def main():
    N = int(input())
    if N == 3:
        return 61
    mod = 10**9 + 7
    d = {'A':0, 'C':1, 'G':2, 'T':3}
    AGC = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    AGC[d['A']][d['G']][d['C']] = 0
    AGC[d['A']][d['C']][d['G']] = 0
    AGC[d['G']][d['A']][d['C']] = 0
    NAGC = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    for i in range(3, N):
        for i1 in range(4):
            for i2 in range(4):
                for i3 in range(4):
                    t = 0
                    if (i2 == d['G'] or i1 == d['G']) and i3 == d['C']:
                        for i4 in range(1, 4):
                            t += AGC[i4][i1][i2]
                    else:
                        for i4 in range(4):
                            t += AGC[i4][i1][i2]
                    if i1 == d['A'] and i2 == d['G'] and i3 == d['C']:
                        t = 0
                    if i1 == d['A'] and i2 == d['C'] and i3 == d['G']:
                        t = 0
                    if i1 == d['G'] and i2 == d['A'] and i3 == d['C']:
                        t = 0
                    t %= mod
                    NAGC[i1][i2][i3] = t
        AGC = copy.deepcopy(NAGC)
    return sum(sum(sum(j) for j in i) for i in AGC) % mod
print(main())

Solution (Python):

"""
条件を満たす文字列は、
xをACGTのいずれかとして
AGC
GAC
ACG
AxGC
AGxC
のいずれも文字列内に無い状態のことを言う。
上の条件から、末尾に文字を付け足そうとした時に、それに関与する文字列は
末尾3文字のみであり、それより前の状態は関係ない。
つまり、前3文字の結果を保存し続ければ3**4のdpテーブルを用いて求めることができる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n = int(readline())

dic1 = {"A":0,"G":1,"C":2,"T":3}



dp = [[[[0]*4 for b in range(4)] for a in range(4)]for _ in range(n+1)]
dp[0][3][3][3] = 1

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 m in range(4):
                    if k == dic1["A"] and l == dic1["G"] and m == dic1["C"]: 
                        continue
                    if k == dic1["G"] and l == dic1["A"] and m == dic1["C"]: 
                        continue
                    if k == dic1["A"] and l == dic1["C"] and m == dic1["G"]: 
                        continue
                    if j == dic1["A"] and l == dic1["G"] and m == dic1["C"]: 
                        continue
                    if j == dic1["A"] and k == dic1["G"] and m == dic1["C"]: 
                        continue
                    
                    dp[i+1][k][l][m] += dp[i][j][k][l] 
                    dp[i+1][k][l][m] %= mod
                    


ans = 0
i = n
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[i][j][k][l]

print(ans%mod)

Solution (Python):


data=int(input())
M=10**9+7

dp={b:1 for b in 'ACGT'}
for i in range(data-1):
    dp_next={}
    for j in dp:
        for k in 'AGCT':
            elem=j[-3:]+k
            if elem[-3:] in ('AGC','GAC','ACG') or elem in ('AGGC','ATGC','ACGC','AGTC','AGGC'):
                continue
            else:
                dp_next.setdefault(elem,0)
                dp_next[elem]+=dp[j]
    dp=dp_next
print(sum(dp.values())%M)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
memo = [{} for _ in range(N+1)]

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

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

answer = dfs(0, 'TTT')
print(answer % MOD)

Solution (Python):

import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()

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

@lru_cache(None)
def dfs(i, last3):
    if i == N:
        return 1
    ret = 0
    for la in 'AGCT':
        if ok(last3+la):
            ret += dfs(i+1, last3[1:]+la)
    return ret % MOD

answer = dfs(0, 'TTT')
print(answer % MOD)

Solution (Python):
n=int(input())
dp=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n)]
mod=10**9+7
for i in range(4):
  for j in range(4):
    for k in range(4):
      if (i,j,k) in ((1,2,3),(1,3,2),(2,1,3)):
        continue
      dp[2][i][j][k]+=1

for i in range(1,n):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        for m in range(4):
          if (k,l,m) in ((1,2,3),(2,1,3),(1,3,2)):
            continue
          if (j,l,m)==(1,2,3) or (j,k,m)==(1,2,3):
            continue
          dp[i][k][l][m]+=dp[i-1][j][k][l]
          dp[i][k][l][m]%=mod
ans=0

for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=dp[n-1][i][j][k]
      ans%=mod
print(ans)

Solution (Python):
N=int(input())
MOD=10**9+7
dp=[[0]*4 for i in range(N)]
for i in range(4):
  dp[0][i]=1
  dp[1][i]=4
dic={'AG':1,'AC':1,'GA':1,'AGA':0,'AGG':0,'AGT':0,'AAG':0,'ATG':0,'AA':1,'AT':1}
def chk(i,j):
  global dp,dic
  if j==0:
    return 0
  elif j==1:
    return dic['AGG']+dic['AGT']+dic['ATG']+dic['AG']+dic['GA']
  elif j==2:
    return dic['AC']
  else:
    return 0
dp[2][0]=sum(dp[1])
dp[2][1]=sum(dp[1])-dp[0][0]-dp[0][2]
dp[2][2]=sum(dp[1])-dp[0][0]
dp[2][3]=sum(dp[1])

dic['AGG']=dic['AG']
dic['AGT']=dic['AG']

dic['ATG']=dic['AT']
dic['AG']=dp[1][0]
dic['AC']=dp[1][0]-dic['GA']
dic['GA']=dp[1][2]
dic['AT']=dp[1][0]
for i in range(3,N):
  _=sum(dp[i-1])
  for j in range(4):
    dp[i][j]=_-chk(i,j)
  dic['AGG']=dic['AG']
  dic['AGT']=dic['AG']
  dic['ATG']=dic['AT']
  dic['AG']=dp[i-1][0]
  dic['AC']=dp[i-1][0]-dic['GA']
  dic['GA']=dp[i-1][2]
  dic['AT']=dp[i-1][0]
print(sum(dp[-1])%MOD)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

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


ans = 0
memo = [{} for i in range(N+1)]
def dfs(idx, last3):
    
    if last3 in memo[idx]:
        return memo[idx][last3]

    if idx == N:
        return 1
    ret = 0
    for c in "AGCT":
        if no_agc(last3 + c):
            last3_new = (last3 + c)[1:]
            idx_new = idx + 1
            ret = (ret + dfs(idx_new, last3_new)) % mod
    memo[idx][last3] = ret

    return ret
print(dfs(0, "TTT"))

Solution (Python):
n=int(input())
d={}
drev={}
a=["A","C","G","T"]
judge=["AGC","ACG","GAC"]
ans=[[1 for i in range(61)]]+[[0 for i in range(61)] for j in range(n-3)]
cnt=0
mod=10**9+7
for i in range(4):
    for j in range(4):
        for k in range(4):
            s=a[i]+a[j]+a[k]
            if s == "AGC" or s =="ACG" or s == "GAC":continue
            d[s]=cnt
            drev[cnt]=s
            cnt+=1
for i in range(1,n-2):
    for j in range(61):
        for k in range(4):
            h=drev[j]+a[k]
            if h[1:] in judge or h[0]+h[2:]=="AGC" or h[:2]+h[3]=="AGC":continue
            ans[i][d[h[1:]]]+=ans[i-1][j]
            ans[i][d[h[1:]]]%=mod
print(sum(ans[-1])%mod)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

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

ans = 0
memo = [{} for i in range(N+1)]
def dfs(idx, last3):
    if last3 in memo[idx]:
        return memo[idx][last3]
    if idx == N:
        return 1
    ret = 0
    for c in "AGCT":
        if no_agc(last3 + c):
            ret = (ret + dfs(idx + 1, (last3 + c)[1:])) % mod
    memo[idx][last3] = ret
    

    return ret

print(dfs(0, "TTT"))

Solution (Python):
N = int(input())
mod = 10**9+7
dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N+2)]
banc = [(i,0,2) for i in range(4)] + [(0,2,i) for i in range(4)] + [(i,2,0) for i in range(4)] + [(0,i,2) for i in range(4)]
bang = [(i,0,1) for i in range(4)]
if N == 3:
    print(61)

else:

    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in ((0,2,1),(0,1,2),(2,0,1)):
                    continue
                dp[3][i][j][k] += 1
    
    for n in range(4,N+2):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        if (i,j,k) in ((0,2,1),(0,1,2),(2,0,1)):
                            continue
                        if (l,i,j) in ((0,2,1),(0,1,2),(2,0,1)):
                            continue
                        if (l,i,j) in banc:
                            if k==1:
                                continue
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= mod
                        elif (l,i,j) in bang:
                            if k==2:
                                continue
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= mod
                        else:
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= mod
    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                ans += dp[N][i][j][k]
                ans %= mod
    print(ans)

Solution (Python):

import sys
input = sys.stdin.readline









N = int(input())

mod = 10**9+7

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


dp[0][0][0][0] = 1

for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4):
                    
                    if (a==1 and b==2 and d==3) or (a==1 and c==2 and d==3):
                        continue
                    
                    if (b==1 and c==2 and d==3):
                        continue
                    
                    if (b==2 and c==1 and d==3) or (b==1 and c==3 and d==2):
                        continue
                    dp[i+1][b][c][d] += dp[i][a][b][c]
                    dp[i+1][b][c][d] %= mod

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

print(ans%mod)

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce

MOD = 1000000000 + 7
LETTERS = ["A", "C", "G", "T"]
PROHIBIT = ["AGC", "ACG", "GAC", "AGGC", "AGTC", "ATGC"]

def main():
    n = int(input().strip())

    table = {}

    for first in LETTERS:
        for second in LETTERS:
            for third in LETTERS:
                codon = first+second+third
                if not codon in PROHIBIT:
                    table[codon] = [1]

    for i in range(n-3):
        for codon in table.keys():
            table[codon].append(0)

        for codon in table.keys():
            for append in LETTERS:
                three_letters = codon[1:] + append
                four_letters = codon + append

                if (not four_letters in PROHIBIT) and (not three_letters in PROHIBIT):
                    table[three_letters][i+1] = (table[three_letters][i+1] + table[codon][i]) % MOD

    print(reduce(lambda acc, x: (acc + x[-1]) % MOD, table.values(), 0))

if __name__ == "__main__":
    main()

Solution (Python):

MOD = 10**9 + 7
N = int(input())
dp = [[[[0]*5 for i in range(5)] for i in range(5)] for i in range(N+1)]

dp[0][0][0][0] = 1
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                for l in range(1,5):
                    if j == 1 and k == 2 and l == 3: continue  
                    if j == 2 and k == 1 and l == 3: continue  
                    if j == 1 and k == 3 and l == 2: continue  
                    if i == 1 and k == 2 and l == 3: continue  
                    if i == 1 and j == 2 and l == 3: continue  
                    dp[n+1][j][k][l] += dp[n][i][j][k]

ans = 0
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            ans += dp[N][i][j][k]
            ans %= MOD
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

n = int(input())

from functools import lru_cache
@lru_cache(None)
def dfs(v=0, parent=-1):

    if v == n:
        return 1

    if parent[-3] == 'A' and parent[-1] == 'G':
        return sum([dfs(v+1, parent[-2:]+'A'), dfs(v+1, parent[-2:]+'G'), dfs(v+1,parent[-2:]+'T')])%p
    elif parent[-3:-1] == 'AG':
        return sum([dfs(v+1,parent[-2:]+'A'), dfs(v+1,parent[-2:]+'G'), dfs(v+1,parent[-2:]+'T')])%p
    elif parent[-2:] == 'AC':
        return sum([dfs(v+1,'ACA'), dfs(v+1,'ACC'), dfs(v+1,'ACT')])%p
    elif parent[-2:] == 'GA':
        return sum([dfs(v+1,'GAG'), dfs(v+1,'GAA'), dfs(v+1,'GAT')])%p
    elif parent[-2:] == 'AG':
        return sum([dfs(v+1,'AGA'), dfs(v+1,'AGG'), dfs(v+1,'AGT')])%p
    else:
        return sum([dfs(v+1, parent[-2:]+'A')%p, dfs(v+1,parent[-2:]+'G')%p, dfs(v+1,parent[-2:]+'C')%p, dfs(v+1,parent[-2:]+'T')%p])%p


ans = 0

agc = 'AGCT'

for i in range(4):
    for j in range(4):
        word = 'T' +agc[i] + agc[j]
        ans += dfs(2,word)%p

print(ans%p)

Solution (Python):

N=int(input())
MOD=10**9+7
dp =[[[[0 for i in range(4)] for i in range(4)] for i in range(4)]for i in range(N+1)]
dp[0][0][0][0]=1

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

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

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

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 l in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[l][i][j][k] == 0:
                    continue
                
                for n in range(4):
                    if j == 0 and k == 2 and n == 1: continue
                    if j == 0 and k == 1 and n == 2: continue
                    if j == 1 and k == 0 and n == 2: continue

                    if i == 0 and j == 1 and n == 2: continue
                    if i == 0 and k == 1 and n == 2: continue 

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

Solution (Python):



import copy

n=int(input())
A=[[1,1,1,1],[1,1,0,1],[1,0,1,1],[1,1,1,1]] 
B=[[3,3,2,3],[3,3,3,3],[3,3,3,3],[3,3,3,3]] 
mod=10**9+7

for _ in range(n-3):
    nA=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    nB=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    for i in range(4):
        for j in range(4): 
            if j!=2: 
                if not (i==2 and j==1): 
                    nA[i][j]+=A[0][i]
                nB[i][j]+=A[1][i]
                nB[i][j]+=A[2][i]
                nB[i][j]+=A[3][i]
            else: 
                if i!=1: 
                    nA[i][j]+=A[0][i]
                    
                    nB[i][j]+=A[2][i]
                    nB[i][j]+=A[3][i]
            
            if not i*j==2: 
                nA[i][j]+=B[0][i]
            if not (i==0 and j==2): 
                nB[i][j]+=B[1][i]
            nB[i][j]+=B[2][i]
            nB[i][j]+=B[3][i]
    for a in nA:
        for i in range(4):
            a[i]%=mod
    for b in nB:
        for i in range(4):
            b[i]%=mod
    A=copy.copy(nA)
    B=copy.copy(nB)
    
ans=0
for a in A:
    ans+=sum(a)%mod
for b in B:
    ans+=sum(b)%mod 
print(ans%mod)

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

MOD = 10 ** 9 + 7

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

for l in range(N):
    
    for last3 in range(4):
        
        for last2 in range(4):
            
            for last1 in range(4):
                
                if dp[l][last3][last2][last1] == 0: 
                    continue
                
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1: continue
                    if last2 == 0 and last1 == 1 and now == 2: continue
                    if last2 == 2 and last1 == 0 and now == 1: continue
                    if last3 == 0 and last1 == 2 and now == 1: continue
                    if last3 == 0 and last2 == 2 and now == 1: continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD


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

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

MOD = 10 ** 9 + 7

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

for l in range(N):
    
    for last3 in range(4):
        
        for last2 in range(4):
            
            for last1 in range(4):
                
                
                
                
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1: continue
                    if last2 == 0 and last1 == 1 and now == 2: continue
                    if last2 == 2 and last1 == 0 and now == 1: continue
                    if last3 == 0 and last1 == 2 and now == 1: continue
                    if last3 == 0 and last2 == 2 and now == 1: continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD


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

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

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


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
@lru_cache(None)
def dfs(cur,last3):

 
    if cur == n:
        return 1
    ret = 0
    for i in 'ACGT':
        if ok(last3 + i):
            ret = (ret + dfs(cur+1,last3[1:]+i)) % mod
  
    return ret
print(dfs(0,'   '))

Solution (Python):
n=int(input())
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

mod=10**9+7

def dfs(cur,last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==n:
        return 1
    ret=0
    for i in 'ACGT':
        if ok(last3+i):
            ret=(ret+dfs(cur+1,last3[1:]+i))%mod
    memo[cur][last3]=ret
    return ret
print(dfs(0,'TTT'))

Solution (Python):
n = int(input())
mod = 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 i in 'ACGT':
        if ok(last3 + i):
            ret = (ret + dfs(cur+1,last3[1:]+i)) % mod
    memo[cur][last3] = ret
    return ret
print(dfs(0,'   '))

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

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

for i in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for nxt in range(4):
                    if nxt == 3 and c1 == 2 and c2 == 1: continue
                    if nxt == 2 and c1 == 3 and c2 == 1: continue
                    if nxt == 3 and c1 == 1 and c2 == 2: continue
                    if nxt == 3 and c2 == 2 and c3 == 1: continue
                    if nxt == 3 and c1 == 2 and c3 == 1: continue
                    dp[i+1][nxt][c1][c2] += dp[i][c1][c2][c3]
                    dp[i+1][nxt][c1][c2] %= MOD

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

print(ans)