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, 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, 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 ['A', 'C', 'G', 'T']:
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret
print(dfs(0, 'TTT'))

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret
print(dfs(0, 'TTT'))

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

def is_valid(i, j, k, new):
    if (j, k, new) == (0, 1, 2) or (j, k, new) == (0, 2, 1) or (j, k, new) == (2, 0, 1):
        return False
    elif (i, k, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1):
        return False
    elif (i, j, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1):
        return False
    else:
        return True

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
dp[0][3][3][3] = 1
for n in range(1, N + 1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for new in range(4):
                    if is_valid(i, j, k, new):
                        dp[n][j][k][new] += dp[n - 1][i][j][k]
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N][i][j][k]) % mod
print(ans)

Solution (Python):
def dp_table(*counts):  
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def ng(char1, char2, char3, new_char):
    if char2 == 0 and char3 == 1 and new_char == 2:
        return True
    if char2 == 0 and char3 == 2 and new_char == 1:
        return True
    if char2 == 1 and char3 == 0 and new_char == 2:
        return True
    if char1 == 0 and char2 == 1 and new_char == 2:
        return True
    if char1 == 0 and char3 == 1 and new_char == 2:
        return True
    return False


AGCT = ["A", "G", "C", "T"]



def main():
    modulo = 10**9+7
    N = int(input())
    dp = dp_table(N+1, 4, 4, 4)
    dp[0][3][3][3] = 1
    for i in range(N):
        for char_1 in range(4):
            for char_2 in range(4):
                for char_3 in range(4):
                    if dp[i][char_1][char_2][char_3] == 0:
                        continue
                    
                    
                    for new in range(4):
                        if ng(char_1, char_2, char_3, new):
                            continue
                        else:
                            dp[i + 1][char_2][char_3][new] += dp[i][char_1][char_2][char_3]
                    dp[i + 1][char_2][char_3][new] %= modulo
    ans = 0
    for char_1 in range(4):
        for char_2 in range(4):
            for char_3 in range(4):
                ans += dp[N][char_1][char_2][char_3]
    
    print(ans % modulo)


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache
from itertools import product

N = int(input())
T = [''.join(t) for t in product(('A','C','G','T'),repeat = 3)]

def acg(s):
    return any(['ACG' in s[:i] + s[i+1:i+2] + s[i] + s[i+2:] for i in range(len(s))])

@lru_cache(maxsize=None)
def f(N,s):
    if N == 3 and acg(s):
        return 0
    elif N == 3 and not acg(s):
        return 1
    else: 
        return sum(f(N-1, c + s[:2]) for c in ('A','C','G','T') if not acg(c + s))

ans = sum(f(N,s) for s in T)
print(ans % 1000000007)

Solution (Python):
n = int(input())
mod = 10**9+7
A, G, C, T = 0, 1, 2, 3
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i == A and j == G and k == C)\
            or (i == A and j == C and k == G)\
            or (i == G and j == A and k == C):
                continue
            else:
                dp[3][i][j][k] += 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 (k == A and l == G and m == C)\
                    or (k == G and l == A and m == C)\
                    or (k == A and l == C and m == G)\
                    or (j == A and l == G and m == C)\
                    or (j == A and k == G and m == C):
                        continue
                    else:
                        dp[i+1][k][l][m] += dp[i][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)

Solution (Python):
N = int(input())
mod = 10**9+7
from collections import defaultdict
dp = defaultdict(lambda:defaultdict(lambda:0))
def possible(last4):
    if 'AGC' in last4:
        return False
    for i in range(3):
        s = list(last4)
        s[i],s[i+1] = s[i+1],s[i]
        if 'AGC' in ''.join(s):
            return False
    return True
S = []
for s1 in 'AGCT':
    for s2 in 'AGCT':
        for s3 in 'AGCT':
            s = s1+s2+s3
            S.append(s)
for s in S:
    if s not in ['AGC','GAC','ACG']:
        dp[3][s] = 1

for n in range(3,N+3):
    for last in 'AGCT':
        for last3 in S:
            last4 = last3+last
            if possible(last4):
                dp[n+1][last4[1:]] += dp[n][last3]
                dp[n+1][last4[1:]] %= mod
print(dp[N+3]['TTT'])

Solution (Python):
N = int(input())
mod = 10**9+7
from collections import defaultdict
dp = defaultdict(lambda:{})
def possible(last4):
    if 'AGC' in last4:
        return False
    for i in range(3):
        s = list(last4)
        s[i],s[i+1] = s[i+1],s[i]
        if 'AGC' in ''.join(s):
            return False
    return True
    
def rec(n,last3):
    if last3 in dp[n]:
        return dp[n][last3]
    if n == 3:
        if last3 not in ['AGC','GAC','ACG']:
            dp[n][last3] = 1
            return 1
        else:
            dp[n][last3] = 0
            return 0
    res = 0
    for s in 'AGCT':
        last4 = last3+s
        if possible(last4):
            res += rec(n-1,last4[1:])
            res %= mod
    dp[n][last3] = res
    return res

print(rec(N+3,'TTT'))

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

def is_valid(i, j, k, new):
    if (j, k, new) == (0, 1, 2) or (j, k, new) == (0, 2, 1) or (j, k, new) == (2, 0, 1):
        return False
    elif (i, j, k, new) == (0, 2, 2, 1) or (i, j, k, new) == (0, 1, 2, 1) or (i, j, k, new) == (0, 3, 2, 1):
        return False
    elif (i, j, k, new) == (0, 2, 0, 1) or (i, j, k, new) == (0, 2, 2, 1) or (i, j, k, new) == (0, 2, 3, 1):
        return False
    else:
        return True

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
for n in range(3, N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for new in range(4):
                    if n ==3 and (i,j,k)!=(0,1,2) and (i,j,k)!=(1,2,1) and (i,j,k)!=(2,0,1):
                        dp[n][i][j][k]=1
                    elif is_valid(i, j, k, new):
                        dp[n][j][k][new] += dp[n-1][i][j][k]
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N][i][j][k]) % mod
print(ans)

Solution (Python):
def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

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

dna = ["A","C","G","T"]

def chk(last4):
    for i in range(len(last4)):
        l = list(last4)
        if i > 0:
            l[i],l[i-1] = l[i-1],l[i]
        if "AGC" in "".join(l):
            return False
    return True

def rec(idx, last3):
    if idx == N:
        return 1
    elif last3 in memo[idx]:
        return memo[idx][last3]
    else:
        ret =0
        for d in dna:
            if chk(last3 + d):
                ret+= rec(idx+1,last3[1:]+d)
                ret = ret % (10**9+7)
        memo[idx][last3] = ret
        return ret


def ans():
    return rec(0,"TTT")

print(ans())

Solution (Python):
def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

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

dna = ["A","C","G","T"]

def chk(last4):
    for i in range(len(last4)):
        l = list(last4)
        if i > 0:
            l[i],l[i-1] = l[i-1],l[i]
        if "AGC" in "".join(l):
            return False
    return True

def rec(idx, last3):
    if idx == N:
        return 1
    elif last3 in memo[idx]:
        return memo[idx][last3]
    else:
        ret =0
        for d in dna:
            if chk(last3 + d):
                ret+= rec(idx+1,last3[1:]+d)
                ret = ret % (10**9+7)
        memo[idx][last3] = ret
        return ret


def ans():
    return rec(0,"TTT")

print(ans())

Solution (Python):
def dynamic_programming(N):
    mod = 10 ** 9 + 7
    dp = [{} for _ in range(N+1)] 
    dp[0]['TTT'] = 1
    for n in range(N):
        for last3 in dp[n].keys():
            for c in 'ACTG':
                if is_ok(last3 + c):
                    if last3[1:] + c in dp[n+1].keys():
                        dp[n+1][last3[1:] + c] += dp[n][last3] % mod
                    else:
                        dp[n+1][last3[1:] + c] = dp[n][last3] % mod
    ret = sum(dp[N].values()) % mod
    return ret

def is_ok(last4):
        
    for i in range(4):
        t = list(last4)
        if i < 3:
            t[i], t[i+1] = t[i+1], t[i]
        if ''.join(t).count('AGC') > 0:
            return False
    return True

def main():

    n = int(input())
    

    
    print(dynamic_programming(n))


main()

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).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)
    memo[cur][last3] = ret
    return ret

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

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

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).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)
    memo[cur][last3] = ret
    return ret

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

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






def ok(l4):
  l3 = l4[1:4]
  if l3 == 'AGC' or l3 =='GAC' or l3 == 'ACG':
    return False
  if l4[0] == 'A' and l4[2:4] == 'GC':
    return False
  if l4[0:2] == 'AG' and l4[3] == 'C':
    return False
  return True


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

for c1 in ACGT:
  for c2 in ACGT:
    for c3 in ACGT:
      l4 = 'X' + c1 + c2 + c3
      if ok(l4):
        dp[3][l4] = 1
      else:
        dp[3][l4] = 0

for i in range(4, N+1):
  for l4 in dp[i-1].keys():
    for c in ACGT:
      next_l4 = l4[1:4] + c
      if not next_l4 in dp[i]:
        dp[i][next_l4] = 0
      if ok(next_l4):
        dp[i][next_l4] += dp[i-1][l4]

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

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

dp = [[[[0, 0, 0, 0] for k in range(4)] for j in range(4)] for i in range(n+1)]




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

for len in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[len][c1][c2][c3] == 0:
                    continue
                for add in range(4):
                    if c1 == 1 and c2 == 0 and add == 2:
                        continue
                    elif c1 == 0 and c2 == 1 and add == 2:
                        continue
                    elif c1 == 2 and c2 == 0 and add == 1:
                        continue
                    elif c1 == 1 and c3 == 0 and add == 2:
                        continue
                    elif c2 == 1 and c3 == 0 and add == 2:
                        continue
                    dp[len+1][add][c1][c2] += dp[len][c1][c2][c3]
                    dp[len+1][add][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):
def valid(st):
    check_str = st[::-1]
    invalid_types = ["AGC", "A_GC", "GAC", "ACG", "AG_C"]
    for typ in invalid_types:
        typ = typ[::-1]
        i=0
        j=0
        if len(check_str) < len(typ):
            continue
        res = False
        for i in range(len(typ)):
            if typ[i] == '_':
                continue
            if typ[i] != check_str[i]:
                res = True
                break
        if res == False:
            return res
    return True

fsm = {}
index = 0
sigma = ["A", "C", "G", "T"]
for i in sigma:
    for j in sigma:
        for k in sigma:
            st = ''.join([i,j,k])
            if valid(st):
                fsm[st] = index
                index+=1
arr = [[],[]]
arr[0] = [0 for _ in range(len(fsm))]
arr[1] = [1 for _ in range(len(fsm))]
N = int(input())
for n in range(4, N+1):
    old = (n+1)%2
    nw = n%2
    visited = [False for x in range(len(fsm))]
    for state in fsm.keys():
        for y in sigma:
            if valid(state+y):
                if visited[fsm[state[1:]+y]]:
                    arr[nw][fsm[state[1:]+y]] = (arr[nw][fsm[state[1:]+y]]+arr[old][fsm[state]])%(10**9+7)
                else:
                    visited[fsm[state[1:]+y]] = True
                    arr[nw][fsm[state[1:]+y]] = arr[old][fsm[state]]
print(sum(arr[N%2])%(10**9+7))

Solution (Python):
import itertools

def main():
    atgc = ["A", "T", "G", "C"]
    mod = 10 ** 9 + 7
    n = int(input())

    dp = [[[[0 for i3 in range(4)] for i2 in range(4)] for i1 in range(4)] for i0 in range(n)]

    for i, j, k in itertools.product(range(4), range(4), range(4)):
        dp[0][i][j][k] = 1
    dp[0][0][2][3] = 0 
    dp[0][0][3][2] = 0 
    dp[0][2][0][3] = 0 

    for t in range(n-3):
        for i, j, k in itertools.product(range(4), range(4), range(4)):
            dp[t+1][i][j][k] = dp[t][0][i][j] + dp[t][1][i][j] + dp[t][2][i][j] + dp[t][3][i][j]

        for i in range(4):
            dp[t+1][i][2][3] -= dp[t][0][i][2] 
        for i in range(4):
            dp[t+1][2][i][3] -= dp[t][0][2][i] 
        
        dp[t+1][2][2][3] += dp[t][0][2][2]

        dp[t+1][0][2][3] = 0 
        dp[t+1][0][3][2] = 0 
        dp[t+1][2][0][3] = 0 

    ans = 0
    for i, j, k in itertools.product(range(4), range(4), range(4)):
        ans += dp[n-3][i][j][k]
    print(ans%mod)
main()

Solution (Python):

"""
D - We Like AGC
https://atcoder.jp/contests/abc122/tasks/abc122_d

"""
import sys
import re

N = None
memo = None

def ok(last4):
    if re.search(r'AGC|GAC|ACG|A.GC|AG.C', last4):
        return False
    return True


def dfs(cur, last3):
    global memo
    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)) % (10**9 + 7)
    memo[cur][last3] = ret
    return ret


def main(args):
    global N, memo
    N = int(input())
    memo = [dict() for i in range(N+1)]
    ans = dfs(0, 'TTT')
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
def 解():
    N = int(input())
    iD = 10**9+7

    
    
    
    
    
    
    
    
    
    
    

    A = [0]*(N+1)
    G = [0]*(N+1)
    C = [0]*(N+1)
    T = [0]*(N+1)
    AC = [0]*(N+1)
    GA = [0]*(N+1)
    AG = [0]*(N+1)
    AGG = [0]*(N+1)
    AGT = [0]*(N+1)
    ATG = [0]*(N+1)

    A[1]=G[1]=C[1]=T[1]=1 
    for i in range(2,N+1):
        
        A[i] = A[i-1] + G[i-1] + C[i-1] +T[i-1]
        G[i] = A[i] - AC[i-1]
        C[i] = A[i] - GA[i-1] - AG[i-1] - AGG[i-1] - AGT[i-1] - ATG[i-1]
        T[i] = A[i]

        
        AC[i] = A[i-1] - GA[i-1]  
        AG[i] = A[i-1]
        GA[i] = G[i-1]

        AGG[i]= AG[i-1]
        AGT[i]= AG[i-1]
        ATG[i]= A[i-2]

        A[i] %= iD
        G[i] %= iD
        C[i] %= iD
        T[i] %= iD
        AC[i] %= iD
        GA[i] %= iD
        AG[i] %= iD
        AGG[i] %= iD
        ATG[i] %= iD
        AGT[i] %= iD

    print((A[N]+G[N]+C[N]+T[N])%iD)
解()

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

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).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)
    memo[cur][last3] = ret
    return ret
    
print(dfs(0, "TTT") % 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)) 
    memo[cur][last3] = ret
    return ret
    
print(dfs(0, 'TTT') % MOD)

Solution (Python):
n = int(input())
s = ["A","T","G","C"]
ban = ["AGC","ACG","GAC"]
ban4 = ["ATGC","AGTC","AGGC"]
last3 = [{},{}]
zl = {}
for i in s:
    for j in s:
        for k in s:
            if i+j+k not in ban:
                last3[0][i+j+k] = 1
                zl[i+j+k] = 0
last3[1] = zl.copy()

for k in range(3,n):
    for i in last3[0]:
        for j in s:
            l = i+j
            if not (l in ban4 or l[1:] in ban):
                last3[1][l[1:]] += last3[0][i]
    last3[0] = last3[1]
    last3[1] =zl.copy()

print(sum(last3[0].values())%(10**9+7))

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

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if "".join(t).count("AGC"):
            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)
            ret%=MOD
        memo[cur][last3] = ret
    return ret
print(dfs(0,"TTT"))

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

def is_agc(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 True
    return False

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0

    for char in 'ATGC':
        if not is_agc(last3 + char):
            ret = (ret + dfs(cur + 1, last3[1:] + char)) % mod
        memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Solution (Python):
import itertools, math

N = int(input())

ACGTList = ["A", "G", "C", "T"]
AGCList = ["ATGC", "AGTC", "AGGC"]
for ACGT in ACGTList:
    for AGC in ["AGC", "ACG", "GAC"]:
        AGCList.append(ACGT + AGC)
        AGCList.append(AGC + ACGT)

patternObj = itertools.product(ACGTList, repeat=3)
patternDict = {}
for i, pattern in enumerate(patternObj):
    strPattern = "".join(pattern)
    patternDict[strPattern] = 0 if strPattern in ["AGC", "ACG", "GAC"] else 1

for i in range(N - 3):
    nextPatternDict = dict.fromkeys(patternDict, 0)
    for pattern in patternDict:
        for ACGT in ACGTList:
            newPattern = pattern + ACGT
            if newPattern in AGCList:
                continue
            nextPatternDict[newPattern[:3]] += patternDict[newPattern[1:]]
    patternDict = nextPatternDict.copy()

ans = 0
devide = int(math.pow(10, 9)) + 7
for pattern in patternDict:
    ans += patternDict[pattern]
    ans %= devide

print(ans)

Solution (Python):
MOD = 10**9 + 7
aa = ["A","C","G","T"]
dic = {}
invdic = {}
n = int(input())
for i in range(4):
    for j in range(4):
        for k in range(4):
            dic[16*i+4*j+k] = aa[i]+aa[j]+aa[k]
            invdic[aa[i]+aa[j]+aa[k]] = 16*i+4*j+k


dp = [[0 for j in range(64)] for i in range(101)]

for i in range(64):
    dp[3][i] = 1

dp[3][invdic["AGC"]]=0
dp[3][invdic["GAC"]]=0
dp[3][invdic["ACG"]]=0

for i in range(3,100):
    for j in range(64):
        moji = dic[j]
        if(moji[0] == "A" and moji[2] == "G") or(moji[0] == "A" and moji[1] == "G")or(moji[1] == "A" and moji[2] == "G")or(moji[1] == "G" and moji[2] == "A"):
            dp[i+1][invdic[moji[1]+moji[2]+"A"]] = (dp[i+1][invdic[moji[1]+moji[2]+"A"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"G"]] = (dp[i+1][invdic[moji[1]+moji[2]+"G"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"T"]] = (dp[i+1][invdic[moji[1]+moji[2]+"T"]]+dp[i][j]) % MOD
        elif(moji[1] == "A" and moji[2] == "C"):
            dp[i+1][invdic[moji[1]+moji[2]+"A"]] = (dp[i+1][invdic[moji[1]+moji[2]+"A"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"C"]] = (dp[i+1][invdic[moji[1]+moji[2]+"C"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"T"]] = (dp[i+1][invdic[moji[1]+moji[2]+"T"]]+dp[i][j]) % MOD
        else:
            dp[i+1][invdic[moji[1]+moji[2]+"A"]] = (dp[i+1][invdic[moji[1]+moji[2]+"A"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"C"]] = (dp[i+1][invdic[moji[1]+moji[2]+"C"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"T"]] = (dp[i+1][invdic[moji[1]+moji[2]+"T"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"G"]] = (dp[i+1][invdic[moji[1]+moji[2]+"G"]]+dp[i][j]) % MOD        
    
        

ans = 0

for i in range(64):
    ans = (ans+dp[n][i]) % MOD

print(ans)

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

def checkAGC(string):
    str0 = string[0] +string[1] +string[2] +string[3]
    str1 = string[1] +string[0] +string[2] +string[3]
    str2 = string[0] +string[2] +string[1] +string[3]
    str3 = string[0] +string[1] +string[3] +string[2]
    
    if "AGC" in str0 or "AGC" in str1 or "AGC" in str2 or "AGC" in str3:
        return True
    else:
        return False

def checkAGC3(string):
    str0 = string[0] +string[1] +string[2]
    str1 = string[1] +string[0] +string[2] 
    str2 = string[0] +string[2] +string[1] 
    
    if "AGC" in str0 or "AGC" in str1 or "AGC" in str2 :
        return True
    else:
        return False
      

import itertools

words = list(itertools.product("ATGC", "ATGC","ATGC"))


nucleotide_dict =  dict(list( (words[i],i) for i in range(len(words))))

import numpy as np

W = np.zeros((len(words),len(words)))
for word_prev in words:
    for word_next in words:
        if word_prev[1:] == word_next[:-1] and not checkAGC(word_prev[:-1]+word_next[1:]):
            
            W[nucleotide_dict[word_next],nucleotide_dict[word_prev]] = 1
b = np.array([0 if checkAGC3(i) else 1 for i in words])

def mod(num):
    return num % int(pow(10,9)+7)
  
res = b
for i in range(N-3):
    res = np.vectorize(lambda x: mod(x))(np.dot(W,res))
print(int(mod(np.sum(res))))

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 = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]


def ng(a: int, b: int, c: int):
    return (a == 1 and b == 2 and c == 3)



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


ans = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans += dp[N][a][b][c] % mod


print(ans % mod)

Solution (Python):
n = int(input())
mod = 10 ** 9 + 7
dp = [[[[1 if i==0 else 0 for i in range(n-2)] for j in range(4)] for k in range(4)] for l in range(4)]
dp[0][1][2][0] = 0
dp[0][2][1][0] = 0
dp[2][0][1][0] = 0
for i in range(n - 3):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if dp[j][k][l][i] == 0:
                    continue
                for m in range(4):
                    if k == 0 and l == 2 and m == 1:
                        continue
                    if k == 0 and l == 1 and m == 2:
                        continue
                    if k == 2 and l == 0 and m == 1:
                        continue
                    if j == 0 and l == 2 and m == 1:
                        continue
                    if j == 0 and k == 2 and m == 1:
                        continue
                    dp[k][l][m][i + 1] += dp[j][k][l][i]
                    dp[k][l][m][i + 1] %= mod
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[j][k][l][n - 3]

print(ans % 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 "AGCT":
        if ok(last3+c):
            ret = (ret + dfs(cur+1,last3[1:]+c)) % mod
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Solution (Python):
n = int(input())
MOD = 1e9 + 7

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

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

def sol(cur, s):
    if s in memo[cur]:
        return memo[cur][s]
    if cur == n:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(s + c):
            ret = int(ret + sol(cur + 1, s[1:] + c)) % MOD
    memo[cur][s] = int(ret)
    return int(ret)

print(sol(0, 'TTT'))

Solution (Python):

import sys

MOD = 1000000007  

def solve(n: int):
    def is_valid(i, j, k, l):
        if ((j == 0 and k == 1 and l == 2) or
            (j == 0 and k == 2 and l == 1) or
            (j == 2 and k == 0 and l == 1) or
            (i == 0 and k == 2 and l == 1) or
            (i == 0 and j == 2 and l == 1)):
            return False
        return True
    dp = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    dp[0][1][2] = 0
    dp[0][2][1] = 0
    dp[2][0][1] = 0
    for i in range(3, n):
        next_dp = [[[0] * 4 for _ in range(4)] for _ in range(4)]
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        if is_valid(i, j, k, l):
                            next_dp[j][k][l] += dp[i][j][k]
        dp = next_dp
    ret = sum([sum([sum(e) for e in d ]) for d in dp]) % MOD

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()