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 numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"


def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res


def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]


def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True


A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1
A = np.array(A, dtype = "object")



def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = "object")
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res


x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod)

Solution (Python):
import numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"

def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res

def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]

def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True

A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1

A = np.array(A, dtype = "object")

def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = "object")
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res

x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod)

Solution (Python):
from itertools import product
N = int(input())
MOD = 10**9+7
D = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+3)]
D[0][3][3][3] = 1
for n in range(1,N+1):
    for i, j, k, l in product(range(4), repeat=4):
        if (i,j,l)==(2,1,0) or (i,k,l) == (2,1,0) or (i,j,k) == (1,2,0) or (i,j,k) == (2,0,1) or (i,j,k) == (2,1,0): continue
        D[n][i][j][k] += D[n-1][j][k][l]%MOD
res = 0
for i, j, k in product(range(4),repeat=3):
    res += D[N][i][j][k]
    res %= MOD
print(res)

Solution (Python):
def summ(M):
    S = 0
    for i in range(4):
        for j in range(4):
            S += M[i][j]
            S %= MOD
    return S

N = int(input())
MOD = 10**9 + 7
D = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+3)]
for i in range(4):
    for j in range(4):
        D[1][i][j][3] = 1
for n in range(2,N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                D[n][i][j][k] = sum(D[n-1][j][k])%MOD
    for l in range(4):
        D[n][2][1][l] -= D[n-1][1][l][0]
        D[n][2][l][1] -= D[n-1][l][1][0]
    D[n][2][1][1] += D[n-1][1][1][0]
    D[n][1][2][0] = 0
    D[n][2][0][1] = 0
    D[n][2][1][0] = 0
print(sum(summ(D[N-1][i]) for i in range(4))%MOD)

Solution (Python):
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

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

    for i in range(1, N):
        for s, v in dp[i - 1].items():
            t = s[:2]
            for c in 'AT':
                dp[i][c + t] = (dp[i][c + t] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + t] = (dp[i]['G' + t] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + t] = (dp[i]['C' + t] + v) % MOD

    ans = sum(dp[N - 1].values()) % MOD
    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

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

    for i in range(1, N):
        for s, v in dp[i - 1].items():
            for c in 'AT':
                dp[i][c + s[:2]] = (dp[i][c + s[:2]] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + s[:2]] = (dp[i]['G' + s[:2]] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + s[:2]] = (dp[i]['C' + s[:2]] + v) % MOD

    ans = sum(dp[N - 1].values()) % MOD
    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict as dd
n = int(input())
ng = set(["AGC", "GAC", "ACG", "AGGC", "ACGC", "ATGC", "AGAC", "AGGC", "AGTC"])

moji_count = dd()
moji_count[""] = 1
cand = ["A", "G", "C", "T"]
mod = 10**9 + 7

for i in range(n):
    temp = dd(int)
    for base_moji, num_moji in moji_count.items():
        if len(base_moji) >= 4:
            base_moji = base_moji[1:]
        for add_moji in cand:
            new_moji = base_moji + add_moji
            for ng_word in ng:
                if ng_word in new_moji:
                    break
            else:
                temp[new_moji] += num_moji % mod
        moji_count = temp

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

Solution (Python):
import sys
from collections import defaultdict
from itertools import product

input = sys.stdin.readline

P = 10 ** 9 + 7


def is_ok(a, b, c, d):
    s = "".join((a, b, c, d))
    if ("AGC" in s) or ("ACG" in s) or ("GAC" in s):
        return False
    if (s[0] == "A" and s[2:4] == "GC") or (s[0:2] == "AG" and s[3] == "C"):
        return False
    return True


def main():
    N = int(input())

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

    for i in range(N):
        for a, b, c, d in product("ACGT", repeat=4):
            if is_ok(a, b, c, d):
                dp[i + 1][(b, c, d)] = (dp[i + 1][(b, c, d)] + dp[i][(a, b, c)]) % P

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


if __name__ == "__main__":
    main()

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


ban_list=[]
for i in range(256):
	p=[i//64%4,i//16%4,i//4%4,i%4]
	if p[1:]==[1,2,3] or p[1:]==[1,3,2] or p[1:]==[2,1,3]\
	or (p[:2]==[1,2] and p[3]==3) or (p[0]==1 and p[2:]==[2,3]):
		ban_list.append(i)
for i in range(n):
	for j in range(4):
		for k in range(64):
			three=k*4%64+j
			four=k*4+j
			if four not in ban_list:
				dp[i+1][three]+=dp[i][k]
				dp[i+1][three]%=mod
ans=0
for x in dp[-1]:
	ans+=x
	ans%=mod
print(ans)

Solution (Python):
from itertools import product
import sys
sys.setrecursionlimit(10**9)

N, MOD = int(input()), 10 ** 9 + 7
dp = [[0] * 64 for _ in range(N+1)]
strs = [""] * 64
strs_d = {}
for i, s in enumerate(product("AGCT", repeat=3)):
    strs[i] = "".join(s)
    strs_d["".join(s)] = i

def check(s):
    assert len(s) == 4
    if "".join(s).count("AGC") >= 1:
        return False
    for i in range(3):
        s[i], s[i + 1] = s[i + 1], s[i]
        if "".join(s).count("AGC") >= 1:
            return False
        s[i], s[i + 1] = s[i + 1], s[i]
    return True



dp[0] = [1] * 64
for i in range(1,1+N):
    for j, s in enumerate(strs):
        for ns in "AGCT":
            if check(list(s+ns)):
                dp[i][strs_d[s[1:]+ns]] += dp[i-1][j]
                dp[i][strs_d[s[1:]+ns]] %= MOD

if N == 3:
    print("61")
else:
    print(sum(dp[N-3])%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
"""
違反文字列
AGC -> AGときたらCはNG
GAC -> GAときたらCはNG
ACG -> ACときたらGはNG
AQGC-> A*GときたらCはNG
AGQC-> AG*ときたらCはNG
"""
n=int(input())
p=10**9+7
ok = ['A','G','C','T']
ng = ['AGC','GAC','ACG']
memo =[{} for i in range(n+1)]

def check(text):
  if text[1:] in ng:
    return 0
  if (text[:2] == 'AG' and text[3]=='C') or (text[0]=='A' and text[2:]=='GC'):
    return 0
  return 1

def dfs(cnt, last):
  if last in memo[cnt]:
    return memo[cnt][last]
  if cnt == n:
    return 1
  ans=0
  for o in ok:
    if check(last+o):
      ans += dfs(cnt+1, last[1:]+o) % p
  memo[cnt][last] = ans
  return ans % p
  

print(dfs(0,'TTT')%p)

Solution (Python):
import numpy as np
from itertools import product

n = int(input())

mod = 10**9 + 7
A, G, C, T = range(1, 5)
dp = np.zeros((n+1, 5, 5, 5), dtype=np.int64)
dp[0, 0, 0, 0] = 1
for m in range(n):
    for i, j, k, l in product(range(5), range(5), range(5), range(1, 5)):
        if i == A and j == G and l == C:
            continue
        if i == A and k == G and l == C:
            continue
        if j == A and k == G and l == C:
            continue
        if j == G and k == A and l == C:
            continue
        if j == A and k == C and l == G:
            continue
        dp[m+1, j, k, l] += dp[m, i, j, k]
        dp[m, i, j, k] %= mod

res = 0
for i, j, k in product(range(1, 5), repeat=3):
    res += dp[n, i, j, k]
    res %= mod
print(res)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = int(input())

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


if __name__ == '__main__':
    resolve()

Solution (Python):
import collections, itertools
N = int(input())
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s]
    dp = dp2
print(sum(dp.values()) % mod)

Solution (Python):
import collections, itertools
N = int(input())
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s] % mod
    dp = dp2
print(sum(dp.values()) % mod)

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))




def main():
    n = ni()
    a, c, g, t = 0, 1, 2, 3
    dic = {0: "A", 1: "C", 2: "G", 3: "T"}

    dp = [[[[0 for _ in range(4)] for __ in range(4)] for ___ in range(4)] for ____ in range(n + 1)]
    dp[0][t][t][t] = 1

    for x in range(n):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        if [j, k, l] not in [[a, g, c], [g, a, c], [a, c, g]]:
                            if [i, j, l] != [a, g, c]:
                                if [i, k, l] != [a, g, c]:
                                    dp[x + 1][j][k][l] += dp[x][i][j][k]
                                    dp[x + 1][j][k][l] %= 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)


if __name__ == '__main__':
    main()

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

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

def judge(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).count("AGC") >= 1:
      return False
  return True

def dfs(cur, last3):
  if cur == n:
    return 1
  if last3 in memo[cur]:
    return memo[cur][last3]
  ans = 0
  for c in "AGCT":
    if judge(last3+c):
      ans = (ans+dfs(cur+1, last3[1:]+c))%mod
  memo[cur][last3] = ans
  return ans

print(dfs(0, "TTT"))

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

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

AGC = 16*A+4*G+C
ACG = 16*A+4*C+G
GAC = 16*G+4*A+C

for j in range(64):
  if j==AGC or j==ACG or j==GAC:
    dp[2][j] = 0
  else:
    dp[2][j] = 1

for i in range(3, n):
  tot = [sum(dp[i-1][k::16]) for k in range(16)]
  for j in range(64):
    c1 = j//16
    c2 = j//4%4
    c3 = j%4
    d = tot[j//4]

    if j==AGC or j==ACG or j==GAC:
      d = 0
    elif c2==G and c3==C:
      d -= dp[i-1][c1*4+G]
    elif c1==G and c3==C:
      d -= dp[i-1][G*4+c2]
    dp[i][j] = d % mod

print(sum(dp[-1]) % 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())
mod=10**9+7
dp=[{}for i in range(N)]
list=['AGC','ACG','GAC']
def dfs(x,y):
  if x in list:
    return 0
  if y==N:
    return 1
  if x in dp[y]:
    return dp[y][x]
  ans=0
  for i in 'ACGT':
    if x[0]=='A' and i=='C' and (x[1]=='G' or x[2]=='G'):
      continue
    ans+=dfs(x[1:]+i,y+1)
  dp[y][x]=ans%mod
  return ans%mod
print(dfs('TTT',0))

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

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][3][3][3] = 1
for i in range(1, n+1):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for w in range(4):
                    if x == 0 and z == 2 and w == 1:
                        continue
                    elif y == 0 and z == 2 and w == 1:
                        continue
                    elif y == 2 and z == 0 and w == 1:
                        continue
                    elif y == 0 and z == 1 and w == 2:
                        continue
                    elif x == 0 and y == 2 and w == 1:
                        continue

                    dp[i][y][z][w] += dp[i-1][x][y][z]
                    dp[i][y][z][w] %= MOD

ans = 0
for x in range(4):
    for y in range(4):
        for z in range(4):
            ans += dp[n][x][y][z]
            ans %= MOD

print(ans)

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

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][3][3][3] = 1
for i in range(n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for w in range(4):
                    if x == 0 and z == 2 and w == 1:
                        continue
                    elif y == 0 and z == 2 and w == 1:
                        continue
                    elif y == 2 and z == 0 and w == 1:
                        continue
                    elif y == 0 and z == 1 and w == 2:
                        continue
                    elif x == 0 and y == 2 and w == 1:
                        continue

                    dp[i+1][y][z][w] += dp[i][x][y][z]
                    dp[i+1][y][z][w] %= MOD

ans = 0
for x in range(4):
    for y in range(4):
        for z in range(4):
            ans += dp[n][x][y][z]
            ans %= MOD

print(ans)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9+7

N = int(input())

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

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

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

print(dfs(0,'TTT'))

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

al=pow(4,n,mod)

import itertools
itr=itertools.product([0,1,2,3],repeat=4)
itr=list(itr)
dic1={} 
dic2={} 
for i in enumerate(itr):
    dic1[i[0]]=[i[1]]
    dic2[i[1]]=[i[0]]

    

dp=[[0 for i in range(4**3)] for q in range(n+1)]

for i in range(4**3):
    if i!=9 and i!=33 and i!=6:
        dp[3][i]=1


for i in range(3,n):
    for q in range(4**3):
        for r in range(4):
            p1=q//16%4
            p2=q//4%4
            p3=q%4
            
            if p2==0 and p3==2 and r==1:
                continue
            if p1==0 and p3==2 and r==1:
                continue
            if p1==0 and p2==2 and r==1:
                continue
            if p2==0 and p3==1 and r==2:
                continue
            if p2==2 and p3==0 and r==1:
                continue
        
            ck=q%16*4
            dp[i+1][ck+r]+=dp[i][q]
            dp[i+1][ck+r]%=mod

print(sum(dp[n])%mod)

Solution (Python):
import copy

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

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 cn in range(1, n+1):
    for c3 in range(5):
        if cn <= 3 and c3 > 0:
            continue
        for c2 in range(5):
            if cn <= 2 and c2 > 0:
                continue
            for c1 in range(5):
                if cn == 1 and c1 > 0:
                    continue
                
                if c2 == 1 and c1 == 3: 
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c2 == 1 and c1 == 2: 
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = (dp[cn][c2][c1][2] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][3] = 0
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c2 == 3 and c1 == 1: 
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c3 == 1 and c1 == 3: 
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c3 == 1 and c2 == 3: 
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                else:
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = (dp[cn][c2][c1][2] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    
total = 0
for c3 in range(1, 5):
    for c2 in range(1, 5):
        for c1 in range(1, 5):
            total = (total + dp[n][c3][c2][c1]) % MOD
print(total)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



N = int(input())
out = [ "AGC", "ACG", "GAC"]
from functools import *

def check(s):
    for i in range(4):
        t = list(s)
        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(n, s):
    if n == N:
        return 1
    res = 0
    for c in "ACGT":
        if not check(s + c):
            continue
        res += dfs(n + 1, s[1:] + c) % MOD
    return res

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

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

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, 'XXX'))

Solution (Python):
import sys
N = int(sys.stdin.readline().rstrip())
mod = 10**9+7

from collections import defaultdict
from itertools import product

A = [('A','G','C'),('G','A','C'),('A','C','G')]

for i in range(3,N+1):
    if i == 3:
        d = defaultdict(int)  
        for a in list(product(['A','C','G','T'],repeat=3)):
            d[(a[0],a[1],a[2])] = 1
        for a in A:
            d[a] = 0
    else:
        new_d = defaultdict(int)
        for a in ['A','C','G','T']:
            for b in list(product(['A','C','G','T'],repeat=3)):
                if not ((b[1],b[2],a) in A or (b[0],b[1],a) == ('A','G','C') or (b[0],b[2],a) == ('A','G','C')):
                    new_d[(b[1],b[2],a)] += d[b]
                    new_d[(b[1], b[2], a)] %= mod
        d = new_d

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

Solution (Python):
from collections import defaultdict
MOD = 10**9 + 7

N = int(input())

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

def sol(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 sol(ns):
                dp[n+1][ns[-3:]] += cnt
                dp[n+1][ns[-3:]] %= MOD

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

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

def ok(x, y, z, nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def f(num,A):
  if num==N:
    return 1
  else:
    x,y,z=A[0],A[1],A[2]
    if (x,y,z) in memo[num]:
      return  memo[num][(x,y,z)]
    else:
      s=0
      for i in ['A','C','G','T']:
        if ok(x,y,z,i):
          s+=f(num+1,(y,z,i))
      memo[num][(x,y,z)]=s%mod
      return s%mod
print(f(0,'ZZZ'))

Solution (Python):
n=int(input())
if n==3:
  print(61)
  exit()
mod=pow(10,9)+7

d={0:'A',1:'G',2:'C',3:'T'}
dd={}
dinitial={}
for i in range(4**4):
  key=[]
  for _ in range(4):
    key.append(d[i%4])
    i//=4
  key=''.join(key)
  if 'AGC' in key:continue
  if 'ACG' in key:continue
  if 'GAC' in key:continue
  if key[0]=='A' and key[2:4]=='GC':continue
  if key[0:2]=='AG' and key[3]=='C':continue
  dd[key]=1
  dinitial[key]=0

for _ in range(n-4):
  ddd=dinitial.copy()
  for k in dd:
    if k[1:]+'A' in ddd:
      ddd[k[1:]+'A']+=dd[k]
      ddd[k[1:]+'A']%=mod
    if k[1:]+'G' in ddd:
      ddd[k[1:]+'G']+=dd[k]
      ddd[k[1:]+'G']%=mod
    if k[1:]+'C' in ddd:
      ddd[k[1:]+'C']+=dd[k]
      ddd[k[1:]+'C']%=mod
    if k[1:]+'T' in ddd:
      ddd[k[1:]+'T']+=dd[k]
      ddd[k[1:]+'T']%=mod
  dd=ddd

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

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

def ok(x,y,z,nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def dfs(idx,lis):
    if idx==N:
      return 1
    x,y,z=lis[0],lis[1],lis[2]
    if (x,y,z) in memo[idx]:
        return memo[idx][(x,y,z)]
    ret=0
    for nx in ['A','G','C','T']:
        if ok(x,y,z,nx):
            ret+=dfs(idx+1,(y,z,nx))
    memo[idx][(x,y,z)]=ret%mod
    return ret%mod

print(dfs(0,'DDD'))

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

ch=['A','G','C','T']
ban3=['AGC','GAC','ACG']
ban4=['ATGC','AGGC','AGTC']
dp=[{},{}]

mod=10**9+7

for i in range(4**3):
    s=''
    for j in range(3):
        s+=ch[(i>>(j*2))%4]
    
    if s in ban3:
        dp[0][s]=0
    else:
        dp[0][s]=1
    
    dp[1][s]=0

cnt=0

while N>3:
    for k in dp[(cnt+1)%2]:
        dp[(cnt+1)%2][k]=0
    
    for k,v in dp[cnt].items():
        for c in ch:
            nk=k+c

            if nk in ban4:
                continue

            if nk[1:] in ban3:
                continue

            dp[(cnt+1)%2][nk[1:]]+=dp[cnt][nk[:3]]
            dp[(cnt+1)%2][nk[1:]]%=mod
            
    N-=1
    cnt=(cnt+1)%2

print(sum(dp[cnt].values())%mod)

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

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

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(101)]



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


for length in range(n):
    
    for c1 in range(4):
        
        for c2 in range(4):
            
            for c3 in range(4):
                
                if dp[length][c1][c2][c3] == 0: continue
                
                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[length+1][a][c1][c2] += dp[length][c1][c2][c3]
                    dp[length+1][a][c1][c2] %= MOD
                    
ans = 0

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

Solution (Python):

from itertools import product
from collections import defaultdict
import sys
MOD = 10**9 + 7
def main(N):
    dp = [defaultdict(int) for _ in range(N + 1)]
    dp[0]['TTT'] = 1
    for i in range(N):
        for j in product('AGCT', repeat=3):
            jj = ''.join(j)
            if jj not in dp[i]: continue
            for k in 'AGCT':
                last4 = jj + k
                last3 = last4[1:]
                if last3 == 'AGC': continue
                if last3 == 'GAC': continue
                if last3 == 'ACG': continue
                if last4[0] == 'A' and last4[3] == 'C' and (last4[1] == 'G' or last4[2] == 'G'): continue
                dp[i + 1][last3] += dp[i][jj]
                dp[i + 1][last3] %= MOD
    ans = 0
    for j in product('AGCT', repeat=3):
        jj = ''.join(j)
        ans += dp[N][jj]
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    main(N)