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):
N = int(input())
dpA = [0, 1, 4]
dpC = [0, 1, 4]
dpG = [0, 1, 4]
dpT = [0, 1, 4]
dpAG = [0, 0, 1]
dpGA = [0, 0, 1]
dpAC = [0, 0, 1]
dpAT = [0, 0, 1]
dpAGG = [0, 0, 0]
dpATG = [0, 0, 0]
dpAGT = [0, 0, 0]

for i in range(2, N):
	newA = dpA[i] + dpC[i] + dpG[i] + dpT[i]
	newC = dpA[i] + dpC[i] + dpG[i] + dpT[i] - dpAG[i] - dpGA[i] - dpAGG[i] - dpATG[i] - dpAGT[i]
	newG = dpA[i] + dpC[i] + dpG[i] + dpT[i] - dpAC[i]
	newT = dpA[i] + dpC[i] + dpG[i] + dpT[i]
	newAG = dpA[i]
	newGA = dpG[i]
	newAC = dpA[i] - dpGA[i]
	newAT = dpA[i]
	newAGG = dpAG[i]
	newATG = dpAT[i]
	newAGT = dpAG[i]
	dpA.append(newA)
	dpC.append(newC)
	dpG.append(newG)
	dpT.append(newT)
	dpAG.append(newAG)
	dpGA.append(newGA)
	dpAC.append(newAC)
	dpAT.append(newAT)
	dpAGG.append(newAGG)
	dpATG.append(newATG)
	dpAGT.append(newAGT)
print((dpA[N]+dpC[N]+dpG[N]+dpT[N])%1000000007)

Solution (Python):
mod=10**9+7
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 0
    return 1

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):
"""
1.4種類の文字ATGC
2.AGCを作ってはならない
3.隣り合う文字を1箇所だけ入れ替えても、AGCになってはならない

3. が厄介
変えないAGC 
0-1 A*GC
1-2 GAC
2-3 ACG
3-4 AG*C

とりあえず3文字分テーブルに持たせながらdp？
"""

mod = 10**9 + 7
N = int(input())
dp =[[[[0]*5 for i in range(5)] for j in range(5)] for n in range(108)]

nul = 0
A = 1
G = 2
C = 3
T = 4

"""
AGC
0-1 A*GC
1-2 GAC
2-3 ACG
3-4 AG*C
"""
dp[0][0][0][0] = 1
for n in range(N):
    for n3 in range(5):             
        for n2 in range(5):         
            for n1 in range(5):     
                for s in range(1,5):  
                    if n2 == A and n1 == G and s == C: continue
                    if n3 == A and n1 == G and s == C: continue
                    if n2 == G and n1 == A and s == C: continue
                    if n2 == A and n1 == C and s == G: continue
                    if n3 == A and n2 == G and s == C: continue
                    
                    dp[n+1][n2][n1][s] += dp[n][n3][n2][n1]                    
ans = 0
for i in range(5):
    for j in range(5):
        for k in range(5):
            ans += dp[N][i][j][k]
print(ans%mod)

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

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

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], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).find('AGC') >= 0:
            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())
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], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).find('AGC') >= 0:
            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())


def is_valid(last_4):
    cand = [last_4]
    for i in range(3):
        cand.append(last_4[:i] + last_4[i + 1] + last_4[i] + last_4[i + 2:])

    for m in cand:
        if "AGC" in m:
            return False
    return True


memo = [{} for i in range(N + 1)]
mod = 10**9 + 7


def dfs(index, last_3):
    if last_3 in memo[index].keys():
        return memo[index][last_3]
    elif index == N:
        return 1
    else:
        s = 0
        for c in "AGCT":
            if is_valid(last_3 + c):
                s = (s + dfs(index + 1, last_3[1:] + c)) % mod
        memo[index][last_3] = s
        return s


print(dfs(0, "HHH"))

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
dp={b:1 for b in 'ACGT'}
for i in range(N-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
sys.setrecursionlimit(100000)

def intinput(): return map(int,input().split())

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

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

def dfs(last3="TTT",cnt=0):
    if last3 in memo[cnt]:
        return memo[cnt][last3]
    if cnt==n:
        return 1
    ans=0
    for i in "AGCT":
        last4 = last3+i
        if ok(last4):
            ans = ans+dfs(last4[1:],cnt+1)
    memo[cnt][last3]=ans
    return ans

print(dfs()%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
for i in range(N+1):
    if i == 0:
        memo[0]["****"] = 1
    elif i == 1:
        memo[1]["***A"] = 1
        memo[1]["***C"] = 1
        memo[1]["***G"] = 1
        memo[1]["***T"] = 1
    else:
        
        for c in 'ACGT':
            for j in memo[i-1]:
                
                if ok(j[1:] + c):
                    if j[1:] + c not in memo[i]:               
                        memo[i][j[1:] + c] = memo[i-1][j] % MOD
                    else:
                        memo[i][j[1:] + c] += memo[i-1][j] % MOD

s = 0
for i in memo[N].values():
    s += i % MOD
print(s % MOD)

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

dp = [{} for _ in range(N + 1)]
s = ['A', 'C', 'G', 'T']
dp[0]['TTT'] = 1

for l in range(1, N + 1):
	for c1 in s:
		for c2 in s:
			for c3 in s:
				for c4 in s:
					tmp = c1 + c2 + c3 + c4
					tm = c1 + c2 + c3
					mp = c2 + c3 + c4
					if re.search(r'AGC', tmp):
						continue
					if re.search(r'GAC', tmp):
						continue
					if re.search(r'ACG', tmp):
						continue
					if re.search(r'A.GC', tmp):
						continue
					if re.search(r'AG.C', tmp):
						continue
					if tm in dp[l - 1].keys():
						if mp in dp[l].keys():
							dp[l][mp] += dp[l - 1][tm]
						else:
							dp[l][mp] = dp[l - 1][tm]

ans = 0
for i in dp[N].values():
	ans = (ans + i) % mod
	
print(ans)

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:
			tmp = t[i]
			t[i] = t[i - 1]
			t[i - 1] = tmp
		if ''.join(t).count('AGC') >= 1:
			return False
	return True
			
def AGC(n, last3):
	if last3 in memo[n]:
		return memo[n][last3]
	if n == N:
		return 1
	ret = 0
	for c in 'AGCT':
		if ok(last3 + c):
			ret = (ret + AGC(n + 1, last3[1:] + c)) % MOD
		memo[n][last3] = ret
	return ret
	
print(AGC(0, 'TTT'))

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

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

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



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

sums = 0
for j in range(1, 5):
    for k in range(1, 5):
        for l in range(1, 5):
            sums += dp[N][l][k][j]

print(sums % (10**9 + 7))

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

dp = [[[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ 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 t in range(1, 5):
                    
                    if i == 2 and j == 1 and t == 3:
                        continue
                    
                    if i == 3 and j == 1 and t == 2:
                        continue
                    
                    if i == 1 and j == 2 and t == 3:
                        continue
                    
                    if i == 2 and k == 1 and t == 3:
                        continue
                    
                    if j == 2 and k == 1 and t == 3:
                        continue
                        
                    dp[n+1][t][i][j] += dp[n][i][j][k]

sums = 0
for i in range(1, 5):
    for j in range(1, 5):
        for k in range(1, 5):
            sums += dp[N][i][j][k]

print(sums % (10**9 + 7))

Solution (Python):
import re

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N = int(input())
CHAR = ["A", "C", "G", "T"]
invalid_pattern = r'ACG|GAC|A.?GC|AG.?C'
invalid_reg = re.compile(invalid_pattern)


dp = {a+b+c: 1 if not invalid_reg.search(a+b+c)
      else 0 for a in CHAR for b in CHAR for c in CHAR}




for i in range(N-3):
    next_dp = {key: 0 for key, _ in dp.items()}
    for key, val in dp.items():
        for c in CHAR:
            next_val = key+c
            if invalid_reg.search(next_val):
                
                continue
            else:
                
                next_dp[(key+c)[1:]] += dp[key]
    dp = next_dp
    for key in dp.keys():
        dp[key] %= MOD

print(sum(dp.values()) % MOD)

Solution (Python):
import re

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N = int(input())
CHAR = ["A", "C", "G", "T"]
pattern = r'ACG|GAC|A.?GC|AG.?C'
reg = re.compile(pattern)

dp = {a+b+c: 1 if not reg.search(a+b+c)
      else 0 for a in CHAR for b in CHAR for c in CHAR}


for i in range(N-3):
    next_dp = {key: 0 for key, _ in dp.items()}
    for key, val in dp.items():
        for c in CHAR:
            next_val = key+c
            if reg.search(next_val):
                continue
            else:
                next_dp[(key+c)[1:]] += dp[key]
    dp = next_dp
    for key in dp.keys():
        dp[key] %= MOD
print(sum(dp.values()) % MOD)

Solution (Python):


from collections import defaultdict
MOD = 10 ** 9 + 7


def ok(s: str) -> bool:
    if 'AGC' in s:
        return False
    sl = list(s)
    if len(s) < 3:
        return True
    for i in range(len(s)-1):
        st = sl.copy()
        st[i], st[i + 1] = sl[i + 1], sl[i]
        if 'AGC' in ''.join(st):
            return False
    return True


n = int(input())
dp = [defaultdict(int) for _ in range(n + 1)]
dp[0][''] = 1
for i in range(1, n + 1):
    for k in dp[i - 1].keys():
        for c in 'ACGT':
            st = k[1 if i > 4 else 0:] + c
            if ok(st):
                dp[i][st] += dp[i - 1][k]
                dp[i][st] %= MOD
print(sum(dp[n].values()) % MOD)

Solution (Python):
n = int(input())
mod = 10 ** 9 + 7
dp = [{} for i in range(n + 1)]

def check(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 0
    return 1

for c1 in 'ACGT':
    for c2 in 'ACGT':
        for c3 in 'ACGT':
            if not c1 + c2 + c3 in {'AGC', 'GAC', 'ACG'}:
                dp[3][c1 + c2 + c3] = 1
for i in range(n - 3):
    for last3 in dp[3 + i]:
        for c in 'ACGT':
            if check(last3 + c):
                if last3[1:] + c in dp[4 + i]:
                    dp[4 + i][last3[1:] + c] += dp[3 + i][last3]
                else:
                    dp[4 + i][last3[1:] + c] = dp[3 + i][last3]
    for key, value in dp[4 + i].items():
        dp[4 + i][key] = value % mod
print(sum(dp[n].values()) % mod)

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

def check(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 0
    return 1

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 check(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

def check(s):
    for i in range(4):
        l=list(s)
        if i>0:
            l[i-1],l[i]=l[i],l[i-1]
        if "".join(l).count("AGC"):
            return False
    else:
        return True

memo=[dict() for _ in range(N)]
def dfp(i,seq):
    if i==N:
        return 1
    if seq in memo[i]:
        return memo[i][seq]
    ret=0
    for s in ["A","G","C","T"]:
        if check(seq+s):
            ret=(ret+dfp(i+1,seq[1:]+s))%mod
    memo[i][seq] = ret
    return ret

print(dfp(0,"TTT"))

Solution (Python):
from functools import lru_cache
N = int(input())
mod = 10**9+7

def check(s):
    for i in range(4):
        l=list(s)
        if i>0:
            l[i-1],l[i]=l[i],l[i-1]
        if "".join(l).count("AGC"):
            return False
    else:
        return True

@lru_cache(maxsize=None)
def dfp(i,seq):
    ret=0
    if i==N:
        return 1
    for s in ["A","G","C","T"]:
        if check(seq+s):
            ret=(ret+dfp(i+1,seq[1:]+s))%mod
    return ret

print(dfp(0,"TTT"))

Solution (Python):
N=int(input())
mod=10**9+7
a,f=1,1
l=2
b,c,d,e,g,h,i,j,k=0,0,0,0,0,0,0,0,0

for p in range(N-1):
    A=(d+e+i+l)%mod
    B=(a+g)%mod
    C=(b+j)%mod
    D=(b+j)%mod
    E=(a+h)%mod
    F=(c+d+f+k+l)%mod
    G=(b+c+f+j+k)%mod
    H=(a+g+h)%mod
    I=(a+g+h)%mod
    J=(h)%mod
    K=(i)%mod
    L=(c+d+2*e+2*f+2*i+k+2*l)%mod
    a,b,c,d,e,f,g,h,i,j,k,l=A,B,C,D,E,F,G,H,I,J,K,L
print((a+b+c+d+e+f+g+h+i+j+k+l)%mod)

Solution (Python):


def ABC122D_sum():
  return ACT_A[-1]+G_A[-1]+A_G[-1]+GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]+A_C[-1]+GCT_C[-1]+A_T[-1]+A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]

N = int(input())

mod = int(1e9+7)


ACT_A = [4*3*1]
G_A = [4*1*1]
A_G = [4*1*1]
GCT_G_G = [3*1*1]
A_G_G = [1*1*1]
C_G = [3*1*1]
A_T_G = [1*1*1]
GCT_T_G = [3*1*1]
A_C = [3*1*1]
GCT_C = [4*2*1+3*1*1]
A_T = [4*1*1]
A_G_T = [1*1*1]
GCT_G_T = [3*1*1]
CT_T = [4*2*1]


if N == 3:
  print(ABC122D_sum())
  exit()

for i in range(N-3):
  new_ACT_A = ACT_A[-1]+G_A[-1]+A_C[-1]+GCT_C[-1]+A_T[-1]+A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]
  new_G_A = A_G[-1]+GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]
  new_A_G = ACT_A[-1]+G_A[-1]
  new_GCT_G_G = GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]
  new_A_G_G = A_G[-1]
  new_C_G = GCT_C[-1]
  new_A_T_G = A_T[-1]
  new_GCT_T_G = A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]
  new_A_C = ACT_A[-1]
  new_GCT_C = GCT_G_G[-1]+C_G[-1]+GCT_T_G[-1]+A_C[-1]+GCT_C[-1]+A_T[-1]+GCT_G_T[-1]+CT_T[-1]
  new_A_T = ACT_A[-1]+G_A[-1]
  new_A_G_T = A_G[-1]
  new_GCT_G_T = GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]
  new_CT_T = A_C[-1]+GCT_C[-1]+A_T[-1]+A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]
  ACT_A.append(new_ACT_A)
  G_A.append(new_G_A)
  A_G.append(new_A_G)
  GCT_G_G.append(new_GCT_G_G)
  A_G_G.append(new_A_G_G)
  C_G.append(new_C_G)
  A_T_G.append(new_A_T_G)
  GCT_T_G.append(new_GCT_T_G)
  A_C.append(new_A_C)
  GCT_C.append(new_GCT_C)
  A_T.append(new_A_T)
  A_G_T.append(new_A_G_T)
  GCT_G_T.append(new_GCT_G_T)
  CT_T.append(new_CT_T)
  
ans = ABC122D_sum() % mod
print(ans)

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




def check(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 'ATCG':
        if check(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 i in range(N+1)]




def check(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 'ATCG':
        if check(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):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def is_ok(s: str, c: str):
    if (s[1:3] == "AG"\
      or s[1:3] == "GA"\
      or (s[0:1] == "A" and s[2:3] == "G")\
      or s[0:2] == "AG")\
      and c == "C":
        return False

    elif s[1:3] == "AC" and c == "G":
        return False

    else:
        return True

from collections import defaultdict

n = ni()

dic = defaultdict(int)
dic["xxx"] = 1

atcg = "ATCG"
MOD = 10**9 + 7

for i in range(n):
    new_dic = defaultdict(int)
    for key, val in dic.items():
        for ci in atcg:
            if is_ok(key, ci):
                new_dic[key[1:] + ci] += val
                new_dic[key[1:] + ci] %= MOD

    dic = new_dic

ans = 0

for _, val in dic.items():
    ans += val
    ans %= MOD

print(ans)

Solution (Python):




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)]


for c3 in range(4):
    for c2 in range(4):
        for c1 in range(4):
            c321 = (c3, c2, c1)
            if c321 == (0, 1, 2) or c321 == (1, 0, 2) or c321 == (0, 2, 1):
                continue
            dp[3][c3][c2][c1] = 1


for n in range(4, N + 1):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                for a in range(4):
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue

                    dp[n][c2][c1][a] += dp[n - 1][c3][c2][c1]
                    dp[n][c2][c1][a] %= MOD


ans = 0
for c3 in range(4):
    for c2 in range(4):
        for c1 in range(4):
            ans += dp[N][c3][c2][c1]
            ans %= MOD

print(ans)

Solution (Python):


from collections import defaultdict

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

N = int(input())
dp = [defaultdict(int) for i in range(N+1)]
dp[0]['TTT'] = 1

for i in range(1, N+1):
    for last3 in dp[i-1].keys():
        for c in 'ATGC':
            if ok(last3+c):
                dp[i][last3[1:]+c] += dp[i-1][last3] %  (1e9 + 7)
                dp[i][last3[1:]+c] %= (1e9 + 7)
            
ans = 0
for i in dp[N].keys():
    ans += dp[N][i]
    ans %= (1e9 + 7)
    
print(int(ans))

Solution (Python):

















import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")






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(current, last3):
    if last3 in memo[current]:
        return memo[current][last3]
    if current == N:
        return 1
    ret = 0
    for c in "ACGT":
        if ok(last3 + c):
            ret = (ret + dfs(current + 1, last3[1:] + c)) % MOD
    memo[current][last3] = ret
    return ret

print(int(dfs(0, "TTT") % MOD))

Solution (Python):
N = int(input())
mod = 10**9 +7
stack = [[0 for _ in range(64)] for _ in range(N+1)]
LI = ['0','1','2','3']
def judge(x):
    for i in range(4):
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
        if ''.join(x).count('012') >= 1:
            return False
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
    return True
def nu(x,y,z):
    return 16*int(x)+4*int(y)+int(z)
for i in range(64):
    if (i == 6) or (i == 9) or (i == 18):
        stack[3][i] = 0
    else:
        stack[3][i] = 1
for i in range(4,N+1):
    for j in LI:
        for k in LI:
            for l in LI:
                cnt = 0
                for m in LI:
                    if judge([m,j,k,l]):
                        cnt += stack[i-1][nu(m,j,k)] 
                stack[i][nu(j,k,l)] = cnt % mod
ans = 0
for i in range(64):
    ans += stack[N][i]
print(ans % mod)

Solution (Python):





from collections import defaultdict
MOD = 10**9 + 7

N = int(input())

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

def test(s):
  if s.find('ABC') != -1:
    return False
  L = len(s)
  for i in range(L-1):
    li = list(s)
    li[i],li[i+1] = li[i+1],li[i]
    t = ''.join(li)
    if t.find('ABC') != -1:
      return False
  return True
    

for n in range(N):
  for s,cnt in dp[n].items():
    for c in 'ABCD':
      ns = s + c
      if test(ns):
        dp[n+1][ns[-3:]] += cnt
        dp[n+1][ns[-3:]] %= MOD

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

Solution (Python):
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 'AGC' in ''.join(t):
            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


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

print(dfs(0, 'TTT'))

Solution (Python):
Mod = 10**9+7
f3 = ["AGC", "GAC", "ACG"]
f4 = ["AGAC","AGGC","AGCC","AGTC"] + ["AAGC","AGGC","ACGC","ATGC"]
q = ["A", "G", "C", "T"]

d = {}
e = {}
for x in q:
  for y in q:
    for z in q:
      s = x+y+z
      if not s in f3:
        d[s] = 1
        e[s] = 0
      
n = int(input())
for i in range(n-3):
  for s in e.keys():
    for c in q:
      t = s+c
      if t[1:] in f3 or t in f4:
        continue
      e[t[1:]] = (e[t[1:]]+d[s])%Mod
  for s in e.keys():
    d[s] = e[s]
    e[s] = 0
    
print(sum(d.values())%Mod)

Solution (Python):
Mod = 10**9+7
p = ["XAGC", "XGAC", "XACG"] + ["AGCX", "GACX", "ACGX"] + ["AGXC", "AXGC"]
q = ["A", "G", "C", "T"]
f = []
for s in p:
  for c in q:
    f.append(s.replace("X",c))

r = ["AGC", "GAC", "ACG"]

d = {}
e = {}
for x in q:
  for y in q:
    for z in q:
      s = x+y+z
      if not s in r:
        d[s] = 1
        e[s] = 0
      
n = int(input())
for i in range(n-3):
  for s in e.keys():
    for c in q:
      t = s+c
      if t in f:
        continue
      e[t[1:]] = (e[t[1:]]+d[s])%Mod
  for s in e.keys():
    d[s] = e[s]
    e[s] = 0
    
print(sum(d.values())%Mod)

Solution (Python):
from collections import Counter
from itertools import product
N = int(input())
S = ['AAAA','AAAG','AAAC','AAAT','AAGA','AAGG','AAGT','AACA','AACC','AACT','AATA','AATG','AATC','AATT','AGAA','AGAG','AGAT','AGGA','AGGG','AGGT','AGTA','AGTG','AGTT','ACAA','ACAG','ACAC','ACAT','ACCA','ACCG','ACCC','ACCT','ACTA','ACTG','ACTC','ACTT','ATAA','ATAG','ATAC','ATAT','ATGA','ATGG','ATGT','ATCA','ATCG','ATCC','ATCT','ATTA','ATTG','ATTC','ATTT','GAAA','GAAG','GAAC','GAAT','GAGA','GAGG','GAGT','GATA','GATG','GATC','GATT','GGAA','GGAG','GGAT','GGGA','GGGG','GGGC','GGGT','GGCA','GGCG','GGCC','GGCT','GGTA','GGTG','GGTC','GGTT','GCAA','GCAG','GCAC','GCAT','GCGA','GCGG','GCGC','GCGT','GCCA','GCCG','GCCC','GCCT','GCTA','GCTG','GCTC','GCTT','GTAA','GTAG','GTAC','GTAT','GTGA','GTGG','GTGC','GTGT','GTCA','GTCG','GTCC','GTCT','GTTA','GTTG','GTTC','GTTT','CAAA','CAAG','CAAC','CAAT','CAGA','CAGG','CAGT','CACA','CACC','CACT','CATA','CATG','CATC','CATT','CGAA','CGAG','CGAT','CGGA','CGGG','CGGC','CGGT','CGCA','CGCG','CGCC','CGCT','CGTA','CGTG','CGTC','CGTT','CCAA','CCAG','CCAC','CCAT','CCGA','CCGG','CCGC','CCGT','CCCA','CCCG','CCCC','CCCT','CCTA','CCTG','CCTC','CCTT','CTAA','CTAG','CTAC','CTAT','CTGA','CTGG','CTGC','CTGT','CTCA','CTCG','CTCC','CTCT','CTTA','CTTG','CTTC','CTTT','TAAA','TAAG','TAAC','TAAT','TAGA','TAGG','TAGT','TACA','TACC','TACT','TATA','TATG','TATC','TATT','TGAA','TGAG','TGAT','TGGA','TGGG','TGGC','TGGT','TGCA','TGCG','TGCC','TGCT','TGTA','TGTG','TGTC','TGTT','TCAA','TCAG','TCAC','TCAT','TCGA','TCGG','TCGC','TCGT','TCCA','TCCG','TCCC','TCCT','TCTA','TCTG','TCTC','TCTT','TTAA','TTAG','TTAC','TTAT','TTGA','TTGG','TTGC','TTGT','TTCA','TTCG','TTCC','TTCT','TTTA','TTTG','TTTC','TTTT']
S = set(S)
mod = 10**9+7
DP1 = Counter()
for a, b, c in product('AGCT', repeat = 3):
    DP1[a+b+c] = 1
DP1['AGC'] = 0
DP1['ACG'] = 0
DP1['GAC'] = 0
for _ in range(N-3):
    DP2 = Counter()
    for k, v in DP1.items():
        for x in 'AGCT':
            s = k + x
            if s in S:
                DP2[s[1:]] = (DP2[s[1:]] + v) % mod
    DP1 = DP2.copy()
print(sum(v for v in DP1.values()) % mod)

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

def ok(s):
    result = True if 'AGC' not in s else False
    for i in range(len(s)-1):
        s_swap = s[:i] + s[i+1] + s[i] + s[i+2:]
        if 'AGC' in s_swap:
            result = False
    return result

CANDIDATE = 'AGCT'

prev = {}
for i in CANDIDATE:
    for j in CANDIDATE:
        for k in CANDIDATE:
            str_ = i + j + k
            if ok(str_):
                prev[str_] = 1

depth = 3
while depth < N:
    next_ = {}
    for item in prev:
        for i in CANDIDATE:
            str_ = item[-3:] + i
            if ok(str_):
                if str_ in next_:
                    next_[str_] += prev[item]
                else:
                    next_[str_] = prev[item]
    depth += 1
    prev = next_

print(sum(prev.values()) % 1000000007)