Problem:
 Score : 400 points    Problem Statement You are given an integer N . Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7 :   The string does not contain characters other than A , C , G and T .  The string does not contain AGC as a substring.  The condition above cannot be violated by swapping two adjacent characters once.       Notes A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T .  For example, the substrings of ATCODER include TCO , AT , CODER , ATCODER and (the empty string), but not AC .      Constraints  3 \leq N \leq 100         Input Input is given from Standard Input in the following format:  N       Output Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7 .        Sample Input 1 3      Sample Output 1 61  There are 4^3 = 64 strings of length 3 that do not contain characters other than A , C , G and T . Among them, only AGC , ACG and GAC violate the condition, so the answer is 64 - 3 = 61 .       Sample Input 2 4      Sample Output 2 230       Sample Input 3 100      Sample Output 3 388130742  Be sure to print the number of strings modulo 10^9+7 .

Solution (Python):
n=int(input())
mod=10**9+7
memo=[{} for i in range(n+1)]
def ok(last4):
  for i in range(4):
    tmp=list(last4)
    if i>=1:
      tmp[i-1],tmp[i]=tmp[i],tmp[i-1]
    if ''.join(tmp).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):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    mod = 10**9 + 7

    N = int(input())

    
    dp = [[0]*4 for _ in range(N+1)]
    dp[1] = [1]*4
    for i in range(1,N+1):
        for j in range(4):
            dp[i][j] += sum(dp[i-1])
            dp[i][j] %= mod
        
        if i >= 2:
            dp[i][1] -= dp[i-2][0]*1 + dp[i-2][2]*1
            dp[i][2] -= dp[i-2][0]*1
        
        if i >= 3:
            
            dp[i][1] -= dp[i-3][0]*3
            
            dp[i][2] += dp[i-3][2]*1

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

if __name__ == '__main__':
    main()

Solution (Python):
def dfs(str):
    global AGC
    if len(str)==3:
        AGC.append(str)
    else:
        dfs(str+'A')
        dfs(str+'G')
        dfs(str+'C')
        dfs(str+'T')


moji=['A','G','C','T']
AGC=[]
dfs('')
ban=[]
for str in moji:
    ban.append(str+'AGC')
    ban.append(str+'ACG')
    ban.append(str+'GAC')
    ban.append('AGC'+str)
    ban.append('ACG'+str)
    ban.append('GAC'+str)
    ban.append('AG'+str+'C')
    ban.append('A'+str+'GC')

ban=list(set(ban))

N=int(input())
mod=10**9+7
dp=[{key:0 for key in AGC} for i in range(0,N+1)]
for key in AGC:
    if key!='AGC' and key!='ACG' and key!='GAC':
        dp[3][key]=1

for i in range(3,N):
    for key in AGC:
        ans=0
        for str in moji:
            if not key+str in ban:
                dp[i+1][key[1:]+str]+=dp[i][key]

print(sum(dp[N][key] for key in AGC)%mod)

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

def main():
    N = int(input())
    states = [s + t + u for s in 'ACGT' for t in 'ACGT' for u in 'ACGT']
    states.remove('AGC')
    states.remove('ACG')
    states.remove('GAC')
    transitions = defaultdict(list)
    ngs = []
    for s in 'ACGT':
        for t in 'ACGT':
            for u in 'ACGT':
                for v in 'ACGT':
                    if 'AGC' in s + t + u + v or 'AGC' in t + s + u + v or 'AGC' in s + u + t + v or 'AGC' in s + t + v + u:
                        ngs.append(s + t + u + v)
    for s in states:
        for t in states:
            if s[1:] == t[:2] and s[0] + t not in ngs:
                transitions[s].append(t)
    count = {s: 1 for s in states}
    for _ in range(N - 3):
        updated = {s: 0 for s in states}
        for fr, tos in transitions.items():
            for to in tos:
                updated[to] += count[fr]
                updated[to] %= 10 ** 9 + 7
        count = updated
    print(sum(count.values()) % (10 ** 9 + 7))

main()

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

def DFS(i, w):
    if w in memo[i]:
        return memo[i][w]
    if i == N:
        return 1
    
    ans = 0
    for c in 'ACGT':
        if w + c not in NG:
            ans = (ans + DFS(i+1, w[1:] + c)) % MOD
    memo[i][w] = ans
    return ans

if N == 3:
    print(61)
else:
    ans, NG = 0, set(['AGGC', 'ATGC', 'AGTC'])
    for w in ['AGC', 'GAC', 'ACG']:
        for c in 'ACGT':
            NG.add(c+w)
            NG.add(w+c)
    for w in [x+y+z for x in 'ACGT' for y in 'ACGT' for z in 'ACGT' if x+y+z not in ['AGC', 'GAC', 'ACG']]:
        ans = (ans + DFS(3, w)) % MOD
    print(ans)

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

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

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

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

if n == 3:
    ans = 0
    for i in dp[-1]:
        for j in i:
            for k in j:
                ans += k
    print(ans)
    sys.exit()

for i in range(4, n + 1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if (j == 0 and k == 1 and l == 2) or (j == 1 and k == 0 and l == 2) or (j == 0 and k == 2 and l == 1):
                    dp[i][j][k][l] = 0
                    continue
                if l != 2:
                    dp[i][j][k][l] = sum([dp[i - 1][x][j][k] for x in range(4)])
                    dp[i][j][k][l] %= mod
                    continue
                dp[i][j][k][l] = sum([dp[i - 1][x][j][k] for x in range(4)])
                dp[i][j][k][l] %= mod

                if l == 2 and k == 1:
                    dp[i][j][k][l] -= dp[i - 1][0][j][1]
                    dp[i][j][k][l] %= mod
                
                if l == 2 and j == 1:
                    dp[i][j][k][l] -= dp[i - 1][0][1][k]
                    dp[i][j][k][l] %= mod
                
                if l == 2 and j == 1 and k == 1:
                    dp[i][j][k][l] += dp[i - 1][0][1][1]
                    dp[i][j][k][l] %= mod


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

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

N = int(input())
MOD = 10**9 + 7
S = ['A', 'G', 'C', 'T']
M = set(['AGC', 'GAC', 'ACG'])

for s in S:
    M.add(s + 'AGC')
    M.add(s + 'GAC')
    M.add(s + 'ACG')
    M.add('A' + s + 'GC')
    M.add('AG' + s + 'C')

@lru_cache(maxsize=None)
def search(prev, length):
    if length >= N:
        return 1

    ret = 0

    for s in S:
        T = prev + s
        if not T in M:
            T = T[:: -1][: 3][:: -1]
            ret += search(T, length + 1)
    return ret

ans = search('', 0) % MOD
print(ans)

Solution (Python):
n=int(input())
mod=10**9+7
dp=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[3][i][j][k]=1
dp[3][0][2][1]=0
dp[3][0][1][2]=0
dp[3][2][0][1]=0
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][j][k][l]=(dp[i][j][k][l]+dp[i-1][m][j][k])%mod
          if m==0 and k==2 and l==1:
            dp[i][j][k][l]=0
          if m==0 and j==2 and l==1:
            dp[i][j][k][l]=0
  dp[i][0][2][1]=0
  dp[i][0][1][2]=0
  dp[i][2][0][1]=0
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 main():
    from functools import lru_cache
    N = int(input())
    MOD = 10**9 + 7

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

    @lru_cache(maxsize=10000)
    def dfs(cur, last3):
        if cur == N:
            return 1
        ret = 0
        for c in "AGCT":
            if is_ok(last3 + c):
                ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
        return ret

    print(dfs(0, "TTT"))


if __name__ == '__main__':
    main()

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

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

    @lru_cache(maxsize=1000)
    def dfs(cur, last3):
        if cur == N:
            return 1
        ret = 0
        for c in "AGCT":
            if is_ok(last3 + c):
                ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
        return ret

    print(dfs(0, "TTT"))


if __name__ == '__main__':
    main()

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

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

    print(dfs(0, "TTT"))


if __name__ == '__main__':
    main()

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

N = int(input())
MOD = 10**9 + 7
S = ['A', 'G', 'C', 'T']
M = set(['AGC', 'GAC', 'ACG'])

for s in S:
    M.add(s + 'AGC')
    M.add(s + 'GAC')
    M.add(s + 'ACG')
    M.add('A' + s + 'GC')
    M.add('AG' + s + 'C')

@lru_cache(maxsize=None)
def search(prev, length):
    if length >= N:
        return 1

    ret = 0

    for s in S:
        T = prev + s
        if not T in M:
            T = T[:: -1][: 3][:: -1]
            ret += search(T, length + 1)
    return ret % MOD

ans = search('', 0)
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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


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


print(dfs(0, "TTT"))

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
dp = [[[[0, 0, 0, 0] for _ in range(4)] for _ in range(4)] for _ in range(n - 2)] 
arr = [[0, 2, 1], [0, 1, 2], [2, 0, 1]]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if not [i, j, k] in arr:
                dp[0][i][j][k] = 1

arr2 = [[0, 2, 2, 1], [0, 3, 2, 1], [0, 2, 3, 1], [0, 2, 2, 1]]
for nn in range(1, n - 2):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if not [i, j, k, l] in arr2 and not [j, k, l] in arr:
                        dp[nn][j][k][l] += dp[nn - 1][i][j][k]
                        dp[nn][j][k][l] %= mod
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[n - 3][i][j][k]
            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 - 2)]


for i in range(4):
    for j in range(4):
        for k in range(4):
            if i == 0 and j == 1 and k == 2: 
                continue
            if i == 0 and j == 2 and k == 1: 
                continue
            if i == 2 and j == 0 and k == 1: 
                continue
            dp[0][i][j][k] = 1


for n in range(N - 3):
    for i in range(4):
        for j in range(4):
            for k in range(4):

                
                for c in range(4):
                    if j == 0 and k == 1 and c == 2: 
                        continue
                    if j == 0 and k == 2 and c == 1: 
                        continue
                    if j == 2 and k == 0 and c == 1: 
                        continue
                    if i == 0 and k == 2 and c == 1: 
                        continue
                    if i == 0 and j == 2 and c == 1: 
                        continue

                    dp[n+1][j][k][c] = (dp[n+1][j][k][c] + dp[n][i][j][k]) % MOD

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

print(ans)

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

dp = [[[0]*4 for _ in range(4)] for _ in range(4)]
A,G,C,T = 0,1,2,3
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i,j,k) in [(A,G,C), (A,C,G), (G,A,C)]: continue
            dp[i][j][k] = 1

for _ in range(N-3):
    dp2 = [[[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):
                if (i,j,k) in [(A,G,C), (A,C,G), (G,A,C)]: continue
                for l in range(4):
                    if (j,k,l) in [(A,G,C), (A,C,G), (G,A,C)]: continue
                    if (i,k,l) == (A,G,C) or (i,j,l) == (A,G,C): continue
                    dp2[j][k][l] += dp[i][j][k]
                    dp2[j][k][l] %= MOD
    dp = dp2

ans = 0
for row in dp:
    for row2 in row:
        ans += sum(row2)
print(ans%MOD)

Solution (Python):
n = int(input())
if n == 3:
    print(61)
    exit()
MOD = 10 ** 9 + 7

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

to = {0:"A", 1:"C", 2:"G", 3:"T"}
for i1 in range(4):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                if "AGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue
                if "ACG" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "GAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AAGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "ACGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "ATGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGCC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGTC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                dp[4][i1][i2][i3][i4] = 1

for i in range(4, n):
    for i1 in range(4):
        for i2 in range(4):
            for i3 in range(4):
                for i4 in range(4):
                    if "AGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue
                    if "ACG" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "GAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AAGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "ACGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "ATGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGCC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGTC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    for j in range(4):
                        dp[i + 1][i1][i2][i3][i4] += dp[i][i2][i3][i4][j]
                        dp[i + 1][i1][i2][i3][i4] %= MOD

ans = 0
for i1 in range(4):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                ans += dp[-1][i1][i2][i3][i4]
                ans %= MOD
print(ans % MOD)

Solution (Python):


N=int(input())

dp=[[[[0]*5 for i in range(5)] for j in range(5)] for k 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):
                dp[n+1][j][k][1]+=dp[n][i][j][k]
                dp[n+1][j][k][2]+=0 if (j==1 and k==3) else dp[n][i][j][k]
                dp[n+1][j][k][3]+=0 if (i==1 and k==2) or (i==1 and j==2) or (j==1 and k==2) or (j==2 and k==1) else dp[n][i][j][k]
                dp[n+1][j][k][4]+=dp[n][i][j][k]
ans=0
for item in dp[N]:
    for jtem in item:
        ans+=sum(jtem)
print(ans%(10**9+7))

Solution (Python):
MOD = 1000000007

N = int(input())

S = ['A', 'C', 'G', 'T']
T = []

for i in range(4):
    for j in range(4):
        for k in range(4):
            s = S[i] + S[j] + S[k]
            T.append(s)

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

for j in range(64):
    sj = T[j]
    if sj == 'GAC' or sj == 'ACG' or sj == 'AGC':
        continue
    dp[2][j] = 1

for i in range(3, N):
    for j in range(64):
        sj = T[j]
        if sj == 'GAC' or sj == 'ACG' or sj == 'AGC':
            continue
        for k in range(64):
            sk = T[k]
            if sj[2] == 'C' and sk[0] == 'A' and sk[2] == 'G':
                continue
            if sj[2] == 'C' and sk[:2] == 'AG':
                continue
            if sj[:2] == sk[1:]:
                dp[i][j] += dp[i - 1][k]
                dp[i][j] %= MOD

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

Solution (Python):
MOD = 1000000007

N = int(input())

S = ['A', 'C', 'G', 'T']
T = []

for i in range(4):
    for j in range(4):
        for k in range(4):
            s = S[i] + S[j] + S[k]
            T.append(s)

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

for j in range(64):
    sj = T[j]
    if sj == 'GAC' or sj == 'ACG' or sj == 'AGC':
        continue
    dp[2][j] = 1

for i in range(3, N):
    for j in range(64):
        sj = T[j]
        if sj == 'GAC' or sj == 'ACG' or sj == 'AGC':
            continue
        for k in range(64):
            sk = T[k]
            if sj[2] == 'C' and sk[0] == 'A' and sk[2] == 'G':
                continue
            if sj[2] == 'C' and sk[:2] == 'AG':
                continue
            if sj[:2] == sk[1:]:
                dp[i][j] += dp[i - 1][k]
                dp[i][j] %= MOD

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

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()


def no_agc_is(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


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



def dfs(cur, last3):
    
    
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in "ACGT":
        if no_agc_is(last3 + c):
            ret = (ret + dfs(cur + 1, (last3 + c)[1:])) % 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(5)] for _ in range(5)] for _ in range(5)] for _ in range(n+1)] 
DP[0][0][0][0] = 1

for i in range(n):
    
    for x in range(5):
        for y in range(5):
            for z in range(5):
                
                for m in range(1,5):
                    if y == 1 and z == 2 and m == 3:
                        continue
                    elif y == 1 and z == 3 and m == 2:
                        continue
                    elif y == 2 and z == 1 and m == 3:
                        continue
                    elif x == 1 and z == 2 and m == 3:
                        continue
                    elif x == 1 and y == 2 and m == 3:
                        continue
                    DP[i+1][y][z][m] = (DP[i+1][y][z][m] + DP[i][x][y][z]) % mod

ans = 0
for x in range(1,5):
    for y in range(1,5):
        for z in range(1,5):
            ans = (ans + DP[n][x][y][z]) % mod

print(ans)

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""

N=int(input())
mod=10**9+7
num=pow(4,N,mod)

S={}
for i in range(1,N+1):
    S[i]={}

S[1]={"A":1,"G":1,"C":1,"T":1}
C=["A","G","C","T"]
for i in range(1,N):
    for s in S[i]:
        for c in C:
            st=s+c
            if len(st)>=5:
                st="".join(list(st)[1:])

            if len(st)==3:
                if st in ["AGC","GAC","ACG"]:
                    continue
            elif len(st)==4:
                if "AGC" in st or "GAC" in st or "ACG" in st:
                    continue
                if st[0]+st[1]+st[3]=="AGC":
                    continue
                if st[0]+st[2]+st[3]=="AGC":
                    continue
            if not st in S[i+1]:
                S[i+1][st]=S[i][s]
            else:
                S[i+1][st]+=S[i][s]
                S[i+1][st]%=mod


print(sum([S[N][i] for i in S[N]])%mod)

Solution (Python):

n=int(input())
import itertools
P=list(itertools.product('ACGT', repeat=3))
mod=10**9+7
use=[] 
for some in P:
    some=list(some)
    K="".join(some)
    use.append(K)
dp=[{some:0 for some in use}for k in range(n+1)]
for some in use:
    if some!="AGC" and some!="ACG" and some!="GAC":
        dp[3][some]=1

D=["A","C","G","T"]
for i in range(4,n+1):
    for some in use:
        
        for j in range(4):
            S=list(some+D[j])
            if (S[0]=="A" and S[2]=="G" and S[3]=="C")  or (S[1]=="G" and S[2]=="A "and S[3]=="C") or (S[0]=="A" and S[1]=="G" and S[3]=="C"):
                pass
            else:
                if some!="AGC" and some!="ACG" and some!="GAC":
                    dp[i]["".join(S[1:])]+=dp[i-1][some]
                    dp[i]["".join(S[1:])]=dp[i]["".join(S[1:])]%mod
ans=0
for some in use:
    if some!="AGC" and some!="ACG" and some!="GAC":
        ans+=dp[n][some]
print(ans%mod)

Solution (Python):

import sys
from itertools import product, permutations

MOD = 1000000007  

def solve(N: int):
    f = lambda : {c:{cc:{ccc:0 for ccc in 'ACGT'} for cc in 'ACGT'} for c in 'ACGT'}
    dp = [f() for _ in range(N+2)]
    ng = set(map(tuple, ('AGC', 'ACG', 'GAC', 
                         'AAGC', 'AGGC', 'ACGC', 'ATGC', 
                         'AGAC', 'AGCC', 'AGGC', 'AGTC', 
                     )))
    for a, b, c in product('ACGT', repeat=3):
        if (a, b, c) in ng:
                continue
        dp[2][a][b][c] = (dp[2][a][b][c] + 1) % MOD
    for i in range(2, N):
        for a, b, c, d in product('ACGT', repeat=4):
            if (a, b, c, d) in ng or (a, b, c) in ng or (b, c, d) in ng:
                continue
            dp[i][b][c][d] = (dp[i][b][c][d] + dp[i-1][a][b][c]) % MOD
    return sum(sum(sum(dd.values()) for dd in d.values()) for d in dp[N-1].values()) % MOD


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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline   
sys.setrecursionlimit(100000000)
from functools import lru_cache
INF = 1000000000
MOD = 10**9+7

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

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

    dp[3]=[[[1]*4 for _ in range(4)] for _ in range(4)]    
    dp[3][0][2][1]=0
    dp[3][0][1][2]=0
    dp[3][2][0][1]=0
    
    cannot={(0,1,2),(0,2,1),(2,0,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 cannot:
                        dp[i][j][k][l]=0
                    else:
                        for m in range(4):
                            if (m,j,l)==(0,2,1) or (m,k,l)==(0,2,1):
                                continue
                            else:
                                dp[i][j][k][l]+=dp[i-1][m][j][k]
                                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[-1][i][j][k]
                ans%=MOD
    print(ans)
if __name__=='__main__':
    main()

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

dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N+1)]
dp[0][3][3][3] = 1
let = {i:l for i,l in enumerate('AGCT')}

for i in range(1,N+1):
    for l3 in range(4):
        for l2 in range(4):
            for l1 in range(4):
                for nextl in range(4):
                    flag = True
                    for j in range(4):
                        lets = list(let[l3]+let[l2]+let[l1]+let[nextl])
                        if j >= 1:
                            lets[j-1],lets[j] = lets[j],lets[j-1]
                        if 'AGC' in ''.join(lets):
                            flag = False
                            break
                    if flag:
                        dp[i][l2][l1][nextl] += dp[i-1][l3][l2][l1]
                        dp[i][l2][l1][nextl] %= mod
ans = 0
for l3 in range(4):
    for l2 in range(4):
        for l1 in range(4):
            ans = (ans + dp[N][l3][l2][l1])%mod
print(ans)

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

dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N+1)]
dp[0][3][3][3] = 1
let = {i:l for i,l in enumerate('AGCT')}

def judge(lets):
    for i in range(4):
        t = lets.copy()
        if i >= 1:
            t[i-1],t[i] = t[i],t[i-1]
        if 'AGC' in ''.join(t):
            return False
    return True

for i in range(1,N+1):
    for l3 in range(4):
        for l2 in range(4):
            for l1 in range(4):
                for nextl in range(4):
                    lets = list(let[l3]+let[l2]+let[l1]+let[nextl])
                    if judge(lets):
                        dp[i][l2][l1][nextl] += dp[i-1][l3][l2][l1]
                        dp[i][l2][l1][nextl] %= mod
ans = 0
for l3 in range(4):
    for l2 in range(4):
        for l1 in range(4):
            ans = (ans + dp[N][l3][l2][l1])%mod
print(ans)

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

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

def judge(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(i,last3):
    if last3 in memo[i]:
        return memo[i][last3]
    if i == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if judge(last3+c):
            ret = (ret + dfs(i+1,last3[1:]+c))%mod
    memo[i][last3] = ret
    return ret

print(dfs(0,'TTT'))

Solution (Python):
from itertools import product
from copy import deepcopy

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

comp = {"A": 0, "C": 1, "G": 2, "T": 3}
keys = comp.keys()

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

bad = [0b001001, 0b000110, 0b100001]
for i in range(4 ** 3):
    if not i in bad:
        dp[3][i] = 1


def is_ok(li):
    for i in range(4):
        tmp = deepcopy(li)
        if i >= 1:
            tmp[i-1], tmp[i] = tmp[i], tmp[i-1]

        if "".join(tmp).count("AGC") >= 1:
            return False

    return True


def comp2int(li):
    ret = 0
    for i, e in enumerate(li):
        ret += comp[e] << 2 * (2 - i)

    return ret


for i in range(3, n):
    for last4 in product(keys, repeat=4):
        last4 = list(last4)
        if is_ok(last4):
            j_prev = comp2int(last4[:-1])
            j_nxt = comp2int(last4[1:])
            dp[i+1][j_nxt] += dp[i][j_prev]
            dp[i+1][j_nxt] %= mod

ans = 0
for i in range(4 ** 3):
    ans += dp[n][i]
    ans %= mod

print(ans)