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):
def resolve():
    N = int(input())
    
    def isOk(i3, i2, i1, i0):
        if i2 == 0 and i1 == 1 and i0 == 2: return False
        if i2 == 1 and i1 == 0 and i0 == 2: return False
        if i2 == 0 and i1 == 2 and i0 == 1: return False
        if i3 == 0 and i1 == 1 and i0 == 2: return False
        if i3 == 0 and i2 == 1 and i0 == 2: return False
        return True
     
    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 isOk(None, i, j, k):
                    dp[3][i][j][k] = 1

    for n in range(3, N):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        if not isOk(i, j, k, l):
                            continue
                        dp[n+1][j][k][l] += dp[n][i][j][k]
                        dp[n+1][j][k][l] %= (10**9)+7

    total = 0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                total += dp[N][i][j][k]
                total %= (10**9)+7
    print(total)


if '__main__' == __name__:
    resolve()

Solution (Python):
def ch2int(ch):
    if ch == 'A':
        return 0
    elif ch == 'C':
        return 1
    elif ch == 'G':
        return 2
    else:
        return 3


def acgt2int(agct):
    ret = 0
    for ch in agct:
        ret = (ret << 2) + ch2int(ch)
    return ret


def int2acgt(val):
    ret = []
    tmp = val
    for i in range(3):
        amari = tmp % 4
        if amari == 0:
            ret.append('A')
        elif amari == 1:
            ret.append('C')
        elif amari == 2:
            ret.append('G')
        else:
            ret.append('T')
        tmp //= 4
    ret.reverse()
    return ret


n = int(input())
dp = [[0] * 64 for _ in range(n)]

dp[0][acgt2int('TTA')] = 1
dp[0][acgt2int('TTC')] = 1
dp[0][acgt2int('TTG')] = 1
dp[0][acgt2int('TTT')] = 1


def is_valid(chs):
    tmp = ''.join(chs)
    ng = ['AGC', 'GAC', 'ACG', 'AAGC', 'ACGC', 'AGGC',
          'ATGC', 'AGAC', 'AGCT', 'AGGC', 'AGTC']
    for item in ng:
        if item in tmp:
            return False
    return True


for i in range(1, n):
    for j in range(64):
        chs = int2acgt(j)
        tmp = 0
        for ch in ['A', 'C', 'G', 'T']:
            my_chs1 = [ch] + chs
            if is_valid(my_chs1):
                tmp += dp[i-1][acgt2int(my_chs1[:-1])] % (10 ** 9 + 7)
        dp[i][j] = tmp

print(sum(dp[-1]) % (10 ** 9 + 7))

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







index=[]
for s1 in "AGCT":
    for s2 in "AGCT":
        for s3 in "AGCT":
            for s4 in "AGCT":
                index.append(s1+s2+s3+s4)



dp=[[0]*256 for _ in range(n)]

if n==3:
    print(61)
    exit()
elif n==4:
    print(230)
    exit()

cnt=0
for i,item in enumerate(index):
    flag=0
    for ng in ["AGC","ACG","GAC","AGGC","ACGC","AGAC","ATGC","AGTC"]:
        if item==ng or item[1:]==ng or item[:-1]==ng:
            flag=1
    if flag==0:
        dp[3][index.index(item)]=1

for i in range(4,n):
    for j,item in enumerate(index):
        for s in "AGCT":
            ss=item[1:]+s
            flag=0
            for ng in ["AGC","ACG","GAC","AGGC","ACGC","AGAC","ATGC","AGTC"]:
                if ss==ng or ss[1:]==ng or ss[:-1]==ng:
                    flag=1
            if flag==0:
                dp[i][index.index(ss)]+=dp[i-1][j]%mod

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

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

mod = 10 ** 9 + 7

if n == 3:
    print(61)
else:

    from collections import defaultdict
    from itertools import product
    keys = []
    for prod in product('AGCT', 'AGCT', 'AGCT', 'AGCT'):
        last = ''.join(prod)
        f = ('AGC' not in last)

        for i in range(len(last) - 1):
            last2 = list(last)
            last2[i], last2[i+1] = last2[i+1], last2[i]
            last2 = ''.join(last2)
            if 'AGC' in last2:
                f = False

        if f:
            keys.append(''.join(last))

    dp = dict()
    for key in keys:
        dp[key] = 1

    for _ in range(4, n):
        dp_new = defaultdict(int)

        for key in keys:
            for char in 'AGCT':
                last = (key + char)[1:]
                f = ('AGC' not in last)

                for i in range(len(last) - 1):
                    last2 = list(last)
                    last2[i], last2[i+1] = last2[i+1], last2[i]
                    last2 = ''.join(last2)
                    if 'AGC' in last2:
                        f = False

                if f:
                    dp_new[''.join(last)] += dp[key]

        dp = dict()
        for key in keys:
            dp[key] = dp_new[key] % mod

    print(sum(list(dp.values())) % 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):

import copy

n = int(input())

mod = 10**9+7

memo = {}

banned = {'ACTG', 'TCAG', 'GCAG', 'TACG', 'AACG', 'ACAG', 'GAGC', 'CACG',
          'AGC', 'ATCG', 'ACCG', 'CAG', 'GACG', 'CCAG', 'AAGC', 'ACG', 'TAGC'}

count = 0


def dp(lettrs, state):

    if state in banned:
        return 0
    if lettrs == 0:
        return 1
    if (lettrs, state) in memo:
        return memo[lettrs, state]

    ans = 0
    for c in "ACGT":
        ans += dp(lettrs-1, (state+c)[-4:])
        ans %= mod
    ans %= mod
    memo[lettrs, state] = ans

    return ans


print(dp(n, ""))

Solution (Python):
import re


def ok(last4):
    pattern = '.?AGC.?|.?GAC.?|.?ACG.?|A.GC|AG.C'
    res = re.match(pattern, last4)
    return res is None


def dfs(cur, last3, n, m, mod):
    if last3 in m[cur]:
        return m[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, n, m, mod)) % mod

    m[cur][last3] = ret
    return ret


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

    m = [{} for _ in range(n + 1)]
    ans = dfs(0, 'TTT', n, m, mod)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    mod=10**9+7
    n=int(readline())

    A=0
    T=1
    G=2
    C=3
    dp=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
    dp[0][T][T][T]=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 j==A and k==G and l==C:
                            pass
                        elif j==A and k==C and l==G:
                            pass
                        elif j==G and k==A and l==C:
                            pass
                        elif m==A and k==G and l==C:
                            pass
                        elif m==A and j==G and l==C:
                            pass
                        else:
                            dp[i][j][k][l]+=dp[i-1][m][j][k]
    ans=0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                ans+=dp[n][j][k][l]
                ans%=mod

    print(ans)

if __name__=="__main__":
    main()

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

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

def judge(i, j, k):
    if i == 0 and j == 2 and k == 1:
        return False
    elif i == 0 and j == 1 and k == 2:
        return False
    elif i == 2 and j == 0 and k == 1:
        return False
    else:
        return True

for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[3][i][j][k] = judge(i, j, k)

def judge(j, k, l, m):
    if k == 0 and l == 2 and m == 1:
        return False
    elif k == 0 and l == 1 and m == 2:
        return False
    elif k == 2 and l == 0 and m == 1:
        return False
    elif j == 0 and l == 2 and m == 1:
        return False
    elif j == 0 and k == 2 and m == 1:
        return False
    else:
        return True

for i in range(4, N + 1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    dp[i][k][l][m] += dp[i - 1][j][k][l] * judge(j, k, l, m)
                    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 % mod)

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

for i in range(n-1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for st in range(4):
                    if i>=1:
                        if k==0 and l==1 and st==2:continue
                        if k==0 and l==2 and st==1:continue
                        if k==1 and l==0 and st==2:continue
                    if i>=2:
                        if j==0 and k==1 and st==2:continue
                        if j==0 and l==1 and st==2:continue
                    dp[i+1][k][l][st] = (dp[i+1][k][l][st]+dp[i][j][k][l])%mod


sum=0
for j in range(4):
    for k in range(4):
        for l in range(4):
            sum = (sum+dp[n-1][j][k][l])%mod


print(sum)

Solution (Python):
import itertools

N = int(input())
MOD = 10**9 + 7
ACGT = ["A","C","G","T"]
dp = [ [ [ [0 for l in range(4) ] for k in range(4)] for j in range(4)] for i in range(N+1)]
dp[0][-1][-1][-1] = 1

for i,p,q,r,s in itertools.product(range(N),range(4),range(4),range(4),range(4)):
  if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
  and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
  and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
    dp[i + 1][q][r][s] += dp[i][p][q][r]
    dp[i + 1][q][r][s] %= MOD   
print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Solution (Python):
import itertools

N = int(input())
MOD = 10**9 + 7
ACGT = ["A","C","G","T"]
dp = [ [ [ [0 for l in range(4) ] for k in range(4)] for j in range(4)] for i in range(N+1)]
dp[0][-1][-1][1] = 1

for i,p,q,r,s in itertools.product(range(N),range(4),range(4),range(4),range(4)):
  if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
  and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
  and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
    dp[i + 1][q][r][s] += dp[i][p][q][r]
    dp[i + 1][q][r][s] %= MOD  
print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

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

MOD = 10**9 + 7

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
A = 1
C = 2
G = 3
T = 4

for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(1, 5):
                    if p == A and q == G and s == C: 
                        continue
                    if p == A and r == G and s == C:
                        continue
                    if q == A and r == G and s == C: 
                        continue
                    if q == G and r == A and s == C:
                        continue
                    if q == A and r == C and s == G: 
                        continue
                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD

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

print(ans)

Solution (Python):
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
MOD = 10 ** 9 + 7
AGCT3 = ["".join(x) for x in itertools.product("AGCT", repeat=3)]
M = 64
blacklist3 = {"AGC", "ACG", "GAC"}


def solve():
    dp = [[0] * M for _ in range(N + 1)]
    for i in range(M):
        if AGCT3[i] not in blacklist3:
            dp[3][i] = 1
    for i in range(4, N + 1):
        for j in range(M):
            p3 = AGCT3[j]
            if p3 in blacklist3:
                dp[i][j] = 0
                continue
            for k in range(M):
                q3 = AGCT3[k]
                q2 = q3[1:]
                if not p3.startswith(q2):
                    continue
                if p3[1] == "G" and p3[2] == "C" and q3[0] == "A":
                    continue
                if p3[0] == "G" and p3[2] == "C" and q3[0] == "A":
                    continue
                dp[i][j] += dp[i - 1][k]
                dp[i][j] %= MOD
    ans = 0
    for x in dp[N]:
        ans = (ans + x) % MOD
    return ans


print(solve())

Solution (Python):
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
MOD = 10 ** 9 + 7
AGCT3 = ["".join(x) for x in itertools.product("AGCT", repeat=3)]
A, G, C, T = 0, 1, 2, 3
M = 64

blacklist3 = {"AGC", "ACG", "GAC"}


def solve():
    dp = [[0] * M for _ in range(N + 1)]
    for i in range(M):
        if AGCT3[i] not in blacklist3:
            dp[3][i] = 1
    for i in range(4, N + 1):
        for j in range(M):
            p3 = AGCT3[j]
            if p3 in blacklist3:
                dp[i][j] = 0
                continue

            if p3[1] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            if p3[0] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            for k in range(M):
                q3 = AGCT3[k]
                q2 = q3[1:]
                if p3.startswith(q2):
                    dp[i][j] += dp[i - 1][k]
                    dp[i][j] %= MOD
    ans = 0
    for x in dp[N]:
        ans = (ans + x) % MOD
    return ans


print(solve())

Solution (Python):
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
MOD = 10 ** 9 + 7
AGCT3 = ["".join(x) for x in itertools.product("AGCT", repeat=3)]
A, G, C, T = 0, 1, 2, 3
M = 64

blacklist3 = {"AGC", "ACG", "GAC"}


def solve():
    dp = [[0] * M for _ in range(N + 1)]
    for i in range(M):
        if AGCT3[i] not in blacklist3:
            dp[3][i] = 1
    for i in range(4, N + 1):
        for j in range(M):
            p3 = AGCT3[j]
            if p3 in blacklist3:
                dp[i][j] = 0
                continue

            if p3[1] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            if p3[0] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            for k in range(M):
                q3 = AGCT3[k]
                q2 = q3[1:]
                if p3.startswith(q2):
                    dp[i][j] += dp[i - 1][k]
                    dp[i][j] %= MOD
    ans = 0
    for x in dp[N]:
        ans = (ans + x) % MOD
    return ans


print(solve())

Solution (Python):
N = int(input())
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]

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

for i in range(N):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        if dp[i][j][k][l] == 0:
          continue

        for m in range(4):
          if k == 1 and l == 0 and m == 2: 
            continue
          if k == 0 and l == 2 and m == 1: 
            continue
          if k == 0 and l == 1 and m == 2: 
            continue
          if j == 0 and l == 1 and m == 2: 
            continue
          if j == 0 and k == 1 and m == 2: 
            continue
          dp[i+1][k][l][m] += dp[i][j][k][l]
          dp[i+1][k][l][m] %= 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):
"""
AtCoder Beginner Contest 122  D - We Like AGC

愚直解
・N文字のうち、各文字についてA,C,G,Tの4通りを取りうるので、4^N
・できた文字について、AGCを含まないか確認：N
・隣接する2文字を一回だけ入れ替えて、AGCができないか確認：N
なので、4^N * N * N ぐらいか？後ろ二つはまとめてもいいが。
また、AAAGCでNGなのがわかっているのに、AAAGCAAを作って調べる〜みたいな重複もいけてない。
このような重複を避けるには、小さい問題からメモ化で解決するDPがよいと思う

入れ替えてAGCができる時、
GAC -> AGC か、 ACG -> AGC、　AXGC -> XAGC、　AGXC -> AGCX
なので、作っている文字列の右端から3文字がわかって入れば行けそう


dp[i+1][j(i-2文字目)][k(i-1文字目)][l(i文字目)]：i文字目をl、一個手前をk、もう一個手前をjとした時の文字列の個数
とすると

遷移
・dp[i+1][A][G][C], dp[i+1][G][A][C], dp[i+1][A][C][G] :こいつらは作ってはいけない
・dp[i][A][＊][G] -> dp[i+1][*][G][C] : Aと* を入れ替えるとAGCができるのでNG
・dp[i][A][G][*] -> dp[i+1][G][*][C] : *とCを入れ替えるとAGCになるのでだめ

上の遷移はなんかややこしいので、ざっくりまとめると、　・・・pqrs　と並んでいて、pqrsについて、
A,G,*,C
A,*,G,C
*,A,G,C,
*,G,A,C
*,A,C,G
がアウトで他はOK
これをDPでやるとよい

最後に末尾3文字について、全パターン見て足し合わせる。


"""

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



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
A = 1
C = 2
G = 3
T = 4

for i in range(N):
    
    for p in range(5):
        for q in range(5):
            for r in range(5):
                
                for s in range(1, 5):
                    
                    """
                    A,G,*,C
                    A,*,G,C
                    *,A,G,C,
                    *,G,A,C
                    *,A,C,G
                    がアウト
                    """
                    if p == A and q == G and s == C : continue
                    if p == A and r == G and s == C : continue
                    if q == A and r == G and s == C : continue
                    if q == G and r == A and s == C : continue
                    if q == A and r == C and s == G : continue

                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD


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


print(ans)

Solution (Python):
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 len in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[len][i][j][k] == 0: continue

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

dp = [[[[0]*5 for _ in range(5)] for _ in range(5)] for _ in range(n + 1)]
ng_3 = [(0, 1, 2), (0, 2, 1), (1, 0, 2)]
dp[0][4][4][4] = 1
for i in range(n):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                for m in range(4):
                    if (m, j, k) in ng_3 or (m == 0 and k == 1 and l == 2) or (m == 0 and j == 1 and l == 2):
                        continue
                    dp[i + 1][m][j][k] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[-1][j][k][l]
print(ans % (10**9 + 7))

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

n = int(input())

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
c = [0, 1, 2, 3]
import itertools
pers = itertools.product(c, repeat=3)
ng_3 = [(0, 1, 2), (0, 2, 1), (1, 0, 2)]
for p in pers:
    if p in ng_3:
        continue
    dp[3][p[0]][p[1]][p[2]] = 1
for i in range(3, n):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if (m, j, k) in ng_3 or (m == 0 and k == 1 and l == 2) or (m == 0 and j == 1 and l == 2):
                        continue
                    dp[i + 1][m][j][k] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[-1][j][k][l]
print(ans % (10**9 + 7))

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

n = int(input())

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
c = [0, 1, 2, 3]
import itertools
pers = itertools.product(c, repeat=3)
for p in pers:
    if p in [(0, 1, 2), (0, 2, 1), (1, 0, 2)]:
        continue
    dp[3][p[0]][p[1]][p[2]] = 1
for i in range(4, n + 1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if (j, k, l) in [(0, 1, 2), (0, 2, 1), (1, 0, 2)]:
                    continue
                elif (j == 0 and l == 1) or (j == 0 and k == 1):
                    dp[i][j][k][l] = sum([dp[i - 1][k][l][x] for x in range(4) if x != 2])
                else:
                    dp[i][j][k][l] = sum([dp[i - 1][k][l][x] for x in range(4)])
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[-1][j][k][l]
print(ans % (10**9 + 7))

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 = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print (dfs(0, 'TTT'))

Solution (Python):
import itertools

ACGT = ['A', 'C', 'G', 'T', '']
MOD = 10 ** 9 + 7

N = int(input())

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

for i, p, q, r, s in itertools.product(range(N), range(5), range(5), range(5), range(4)):
    if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
            and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
            and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
        dp[i + 1][q][r][s] += dp[i][p][q][r]
        dp[i + 1][q][r][s] %= MOD

print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Solution (Python):
ACGT = ['A', 'C', 'G', 'T', '']
MOD = 10 ** 9 + 7

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

dp[0][4][4][4] = 1
for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(4):
                    if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
                            and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
                            and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
                        dp[i + 1][q][r][s] += dp[i][p][q][r]
                        dp[i + 1][q][r][s] %= MOD

print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Solution (Python):
N = int(input())
A = ['A', 'C', 'G', 'T']
dp = [[0]*64 for _ in range(N+1)]
MOD = 10**9+7

for i in range(4):
    for j in range(4):
        for k in range(4):
            if A[i]+A[j]+A[k] in ['AGC', 'ACG', 'GAC']:
                continue

            dp[3][16*k+4*j+i] = 1
    
for i in range(3, N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if A[k]+A[l]+A[m] in ['AGC', 'ACG', 'GAC']:
                        continue
                    
                    if A[j]+A[l]+A[m]=='AGC':
                        continue
                    
                    if A[j]+A[k]+A[m]=='AGC':
                        continue
                    
                    dp[i+1][16*m+4*l+k] += dp[i][16*l+4*k+j]
                    dp[i+1][16*m+4*l+k] %= MOD

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

Solution (Python):


N = int(input())
dp = [[[[0] * 4 for i in range(4)] for j in range(4)] for k in range(N+1)]
dp[0][0][0][0] = 1
mod = 10 ** 9 + 7
for n in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for NEXT in range(4):
          if j == 1 and k == 2 and NEXT == 3:
            continue
          if j == 1 and k == 3 and NEXT == 2:
            continue
          if j == 2 and k == 1 and NEXT == 3:
            continue
          if i == 1 and j == 2 and NEXT == 3:
            continue
          if i == 1 and k == 2 and NEXT == 3:
            continue
          dp[n+1][j][k][NEXT] += dp[n][i][j][k]
          dp[n+1][j][k][NEXT] %= mod
          
ans = 0
for i in dp[N]:
  for j in i:
    for k in j:
      ans += k
ans %= mod
print(ans)

Solution (Python):

from collections import defaultdict


def submit():
    n = int(input())
    modp = 10 ** 9 + 7
    chars = ["A", "C", "G", "T"]
    modp = 10 ** 9 + 7
    
    
    
    
    
    
    

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

    for c1 in chars:
        for c2 in chars:
            for c3 in chars:
                k = c1 + c2 + c3
                if k == "AGC":
                    continue
                if k == "ACG":
                    continue
                if k == "GAC":
                    continue

                dp[3][k] = 1

    for i in range(4, n + 1):
        for k, v in dp[i - 1].items():
            for c in chars:
                
                if k[1] == "A" and k[2] == "G" and c == "C":
                    continue
                
                if k[0] == "A" and k[2] == "G" and c == "C":
                    continue
                
                if k[1] == "G" and k[2] == "A" and c == "C":
                    continue
                
                if k[1] == "A" and k[2] == "C" and c == "G":
                    continue
                
                if k[0] == "A" and k[1] == "G" and c == "C":
                    continue

                new_k = k[1:] + c
                dp[i][new_k] += dp[i - 1][k]
                dp[i][new_k] %= modp

    ans = sum(v % modp for v in dp[n].values())
    print(ans % modp)
    

submit()