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

Solution (Python):


import sys






















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def alpha_to_num(s):
        """
        >>> alpha_to_num('AAA')
        0
        >>> alpha_to_num('AGC')
        11
        >>> alpha_to_num('CCC')
        63
        """
        assert(len(s) == 3)
        d = {'A':0, 'T':1, 'G':2, 'C':3}
        num = 0
        for i in range(3):
            num += pow(4, 2 - i) * d[s[i]]
        return num
    
    def num_to_alpha(num):
        """
        >>> num_to_alpha(0)
        'AAA'
        >>> num_to_alpha(11)
        'AGC'
        >>> num_to_alpha(63)
        'CCC'
        """
        assert(0 <= num < 4 ** 3)
        d = {0:'A', 1:'T', 2:'G', 3:'C'}
        L = []
        for i in range(2, -1, -1):
            q = num // pow(4, i)
            L.append(d[q])
            num -= pow(4, i) * q
        return ''.join(L)
    

    def distribute(num, s, num_of_pattern, seq):
        """
        最後の 3 文字が s (数字に直すと num) であるようなものに対し、末尾に A T G C を追加することを考える
        valid pattern を数え上げ、seq の適切な位置にパターンを加算する
        """
        for char in ['A', 'T', 'G', 'C']:
            new_s = s[1:] + char
            new_num = alpha_to_num(new_s)
            if char == 'G':
                if new_s == 'ACG':
                    continue
            elif char == 'C':
                if s in ['AGT', 'AGG', 'ATG']:
                    continue
                if new_s in ['AGC', 'GAC']:
                    continue
            seq[new_num] = (seq[new_num] + num_of_pattern) % mod

    
    n = ii()
    
    
    dp = [[0] * (4 ** 3) for _ in range(n + 1)]
    
    for num in range(4 ** 3):
        dp[3][num] = 1 if num_to_alpha(num) not in ['AGC', 'ACG', 'GAC'] else 0
    
    for i in range(3, n):
        
        for num in range(4 ** 3):
            distribute(num, num_to_alpha(num), dp[i][num], dp[i+1])


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


if __name__ == "__main__":
    
    

    main()

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

MOD = 10 ** 9 + 7

total = 4 ** N

if N == 3:
    sub = 3
    ans = total - sub
    
elif N >= 4:
    last_three = [{} for _ in range(N - 3 + 1)]
    for n in range(N - 3 + 1):
        for i in ['A', 'G', 'C', 'T']:
            for j in ['A', 'G', 'C', 'T']:
                for k in ['A', 'G', 'C', 'T']:
                    if [i, j, k] != ['A', 'G', 'C'] and [i, j, k] != ['A', 'C', 'G'] and [i, j, k] != ['G', 'A', 'C']:
                        last_three[n]["".join([i, j, k])] = 0
    for k in last_three[0].keys():
        last_three[0][k] = 1
    for i in range(4, N + 1):
        for k in last_three[i - 4].keys():
            if k[1] == 'A' and k[2] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[1] == 'A' and k[2] == 'C':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[1] == 'G' and k[2] == 'A':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[0] == 'A' and k[2] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[0] == 'A' and k[1] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            else:
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD

    ans = sum(last_three[N - 3].values()) % MOD

print(ans)

Solution (Python):
from collections import defaultdict

MOD = 10 ** 9 + 7

N = int(input())


"""dp = dict()
for c1 in "ACGT":
    for c2 in "ACGT":
        for c3 in "ACGT":
            for c4 in "ACGT":
                s = c1 + c2 + c3 + c4
                if s[0:3] in ("AGC", "ACG", "GAC"):
                    continue
                if s[1:4] in ("AGC", "ACG", "GAC"):
                    continue
                if s in ("AGGC", "AGTC", "ATGC"):
                    continue

                dp[s] = 1"""

dp = {"TTT": 1}
for _ in range(N):
    new_dp = defaultdict(int)
    for s, count in dp.items():
        new_dp[s[1:] + 'A'] += count
        new_dp[s[1:] + 'T'] += count
        if s[1:] != "AC":
            new_dp[s[1:] + 'G'] += count
        if s not in ("AGG", "AGT", "ATG") and s[1:] not in ("AG", "GA"):
            new_dp[s[1:] + 'C'] += count

    dp = dict()
    for k, v in new_dp.items():
        dp[k] = v % MOD

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    MOD = 10**9+7
    N = int(input())
    I, J, K, L = N, 4, 4, 4
    
    dp = [[[[0]*(L+1) for _ in range(K+1)] for _ in range(J+1)]
          for _ in range(I+1)]
    
    dp[0][0][0][0] = 1
    
    for i in range(1, I+1):
        for j in range(J+1):
            for k in range(K+1):
                for l in range(L+1):
                    for a in range(1, 5):

                        if [k, l, a] == [1, 3, 2]:
                            continue
                        if [k, l, a] == [1, 2, 3]:
                            continue
                        if [k, l, a] == [2, 1, 3]:
                            continue
                        if [j, l, a] == [1, 2, 3]:
                            continue
                        if [j, k, a] == [1, 2, 3]:
                            continue

                        dp[i][k][l][a] += dp[i-1][j][k][l]

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

    print(ans % MOD)


resolve()

Solution (Python):
N = int(input())
mod = 10 ** 9 + 7
dp = [{} for i in range(N)]
forbid = set(['AGC', 'GAC', 'ACG'])


def search(i, prefix):
    if prefix in forbid:
        return 0
    elif i == N:
        return 1
    elif prefix in dp[i]:
        return dp[i][prefix]

    ret = 0
    for c in 'ACGT':
        if prefix[0] == 'A' and (prefix[1] == 'G' or prefix[2] == 'G') and c == 'C':
            continue
        ret += search(i + 1, prefix[1:] + c)
    dp[i][prefix] = ret % mod
    return ret % mod


print(search(0, 'BBB'))

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    chars = "ACGT"

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

    from collections import deque, Counter
    que = deque()

    for ch1 in chars:
        for ch2 in chars:
            que.append((ch1 + ch2, 2))

    ans = 0
    str_set = set()
    counter = Counter()

    while que:
        cur, length = que.popleft()
        length_next = length + 1
        for ch in chars:
            ok = True
            nx = cur + ch
            if length_next == 3:
                if "AGC" in nx:
                    continue
                for j in range(2):
                    sl = list(nx)
                    sl[j], sl[j + 1] = sl[j + 1], sl[j]
                    swap = "".join(sl)
                    if "AGC" in swap:
                        ok = False
                if ok:
                    que.append((nx, length_next))
            if length_next == 4:
                if "AGC" in nx:
                    ok = False
                for j in range(3):
                    sl = list(nx)
                    sl[j], sl[j + 1] = sl[j + 1], sl[j]
                    swap = "".join(sl)
                    if "AGC" in swap:
                        ok = False
                if ok:
                    counter[nx] += 1
                    str_set.add(nx)

    for _ in range(n - 4):
        counter_next = Counter()
        for st in str_set:
            for ch in chars:
                nx = st[1:] + ch
                if nx in str_set:
                    counter_next[nx] += counter[st]
                    counter_next[nx] %= MOD
        counter = counter_next

    ans = sum(counter.values())
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

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




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(3, n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for w in range(4):
                    if (y, z, w) == (2, 0, 1):
                        continue
                    if (y, z, w) == (0, 1, 2):
                        continue
                    if (y, z, w) == (0, 2, 1):
                        continue
                    if (x, y, w) == (0, 2, 1):
                        continue
                    if (x, z, w) == (0, 2, 1):
                        continue
                    dp[i+1][y][z][w] += dp[i][x][y][z]
                    dp[i+1][y][z][w] %= 10**9+7
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[n][i][j][k]
print(ans%(10**9+7))

Solution (Python):
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    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 j in range(4):  
        for k in range(4):  
            for l in range(4):  
                if j == A and k == G and l == C:  continue
                if j == A and k == C and l == G:  continue
                if j == G and k == A and l == C:  continue
                dp[3][j][k][l] = 1
    
    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):
                        if j == A and k == G and l == C:  continue
                        if j == A and k == C and l == G:  continue
                        if j == G and k == A and l == C:  continue
                        if m == A and k == G and l == C:  continue
                        if m == A and j == G and l == C:  continue
                        dp[i][j][k][l] += dp[i-1][m][j][k]
                        dp[i][j][k][l] %= MOD
    
    res = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                res += dp[N][j][k][l]
                res %= MOD
    
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 6)
import math
from collections import Counter
from collections import deque
from operator import itemgetter
import time, random
MOD = 10 ** 9 + 7
from itertools import permutations

def dfs(s):
    if len(s) == N:
        return 1
    if (s[-2] == 'A' and s[-1] == 'G') or (s[-2] == 'G' and s[-1] == 'A'):
        return dfs(s+'A') % MOD + dfs(s+'G') % MOD + dfs(s+'T') % MOD
    elif s[-2] == 'A' and s[-1] == 'C':
        return dfs(s+'A') % MOD + dfs(s+'C') % MOD + dfs(s+'T') % MOD
    else:
        return dfs(s+'A') % MOD + dfs(s+'C') % MOD + dfs(s+'G') % MOD + dfs(s+'T') % MOD

def main():
    N = int(readline())
    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 j in range(4):  
        for k in range(4):  
            for l in range(4):  
                if j == A and k == G and l == C:  continue
                if j == A and k == C and l == G:  continue
                if j == G and k == A and l == C:  continue
                dp[3][j][k][l] = 1
    
    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):
                        if j == A and k == G and l == C:  continue
                        if j == A and k == C and l == G:  continue
                        if j == G and k == A and l == C:  continue
                        if m == A and k == G and l == C:  continue
                        if m == A and j == G and l == C:  continue
                        dp[i][j][k][l] += dp[i-1][m][j][k]
                        dp[i][j][k][l] %= MOD
    
    res = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                res += dp[N][j][k][l]
                res %= MOD
    
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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

    
    dp[0][0][0][0] = 1
    for i in range(1, N + 1):
        for j in range(5):
            for k in range(5):
                for l in range(5):
                    for m in range(1, 5):
                        if k == A and l == G and m == C:
                            continue
                        if k == A and l == C and m == G:
                            continue
                        if k == G and l == A and m == C:
                            continue
                        if j == A and l == G and m == C:
                            continue
                        if j == A and k == G and m == C:
                            continue

                        dp[i][k][l][m] += dp[i - 1][j][k][l]
                        dp[i][k][l][m] %= MOD

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


if __name__ == "__main__":
    main()

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

moji = ['A','C','G','T']
for c1 in moji:
    for c2 in moji:
        for c3 in moji:
            mojis = c1+c2+c3
            if mojis in ['AGC','GAC','ACG']:continue
            if mojis in dp[3]:
                dp[3][mojis] += 1
            else:
                dp[3][mojis] = 1

for i in range(4,n+1):
    for c in moji:
        for c1 in moji:
            for c2 in moji:
                for c3 in moji:
                    mojis = c1+c2+c3
                    if mojis in ['AGC','GAC','ACG']:continue
                    nowmoji = c2+c3+c
                    if nowmoji in ['AGC','GAC','ACG']:continue
                    if c1 =='A' and c3 == 'G' and c == 'C':continue
                    if c1 =='A' and c2 == 'G' and c == 'C':continue
                    if nowmoji in dp[i]:
                        dp[i][nowmoji] += dp[i-1][mojis]%mod
                        dp[i][nowmoji] %=mod
                    else:
                        dp[i][nowmoji] =  dp[i-1][mojis]%mod
                        dp[i][nowmoji] %=mod

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

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N = int(input())
	
	DP = [[0] * 64 for i in range(N)]
	for i in range(64):
		DP[2][i] = 1
	DP[2][6] = 0
	DP[2][9] = 0
	DP[2][18] = 0

	for p in range(2, N - 1):
		for i in range(4):
			for j in range(4):
				for k in range(4):
					for s in range(4):
						if not ((i == 0 and k == 1 and s == 2) or (i == 0 and j == 1 and s == 2)):
							DP[p + 1][16 * j + 4 * k + s] += DP[p][16 * i + 4 * j + k]
							DP[p + 1][16 * j + 4 * k + s] %= con

		DP[p + 1][6] = 0
		DP[p + 1][9] = 0
		DP[p + 1][18] = 0

	ans = sum(DP[N - 1])
	print(ans % con)


if __name__ == '__main__':
	main()

Solution (Python):
n = int(input())
mod = 10**9+7
  
dp = [[0]*4 for i in range(n)]
for i in range(4):
  dp[0][i] = 1
  dp[1][i] = 4
  dp[2][i] = 16
  
dp[2][1] -= 2
dp[2][2] -= 1
  
for i in range(3,n):
  for j in range(4):
    dp[i][j] = sum(dp[i-1])%mod
  dp[i][1] -= dp[i-2][0] 
  dp[i][1] -= dp[i-2][2] 
  dp[i][1] -= dp[i-3][0]*3 
  dp[i][2] -= dp[i-2][0] 
  dp[i][2] += dp[i-3][2] 
  
print(sum(dp[n-1])%mod)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

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

    """
    ダメワードは
        ACG, AGC, GAC, AxGC, AGxC (xはワイルドカード)
    なので、後ろ３文字を見ながらdpすればよさげ
    """

    char = ['A', 'C', 'G', 'T']
    NG1 = {"ACG", "AGC", "GAC"}
    NG2 = {"AAGC", "ACGC", "AGGC", "ATGC", "AGAC", "AGCG", "AGGC", "AGTC"}
    key = []
    for x in char:
        for y in char:
            for z in char:
                word = x + y + z
                if word not in NG1:
                    key.append(word)
    
    zeros = [0] * len(key)
    ones = [1] * len(key)
    d = dict(zip(key, ones))
    
    for _ in range(N - 3):
        d2 = dict(zip(key, zeros))
        for word in d:
            x, y, z = list(word)
            for w in char:
                if (y + z + w not in NG1) and (x + y + z + w not in NG2):
                    d2[y + z + w] += d[x + y + z]
                    d2[y + z + w] %= mod
        d = d2
    
    ans = 0
    for word in d:
        ans += d[word]
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
MOD=10**9+7
R=range(5)
dp=[[[[0,0,0,0,0] for i in R] for j in R] for k in range(N+1)]
dp[0][0][0][0]=1


for x in range(N):
    for d in R:
        for c in R:
            for b in R:
                for a in range(1,5):
                    
                    if (c==1 and b==2 and a==3):
                        continue
                    if (c==2 and b==1 and a==3):
                        continue
                    if (c==1 and b==3 and a==2):
                        continue
                    if (d==1 and b==2 and a==3):
                        continue
                    if (d==1 and c==2 and a==3):
                        continue
                    dp[x+1][c][b][a]+=dp[x][d][c][b]
                    dp[x+1][c][b][a]%=MOD

ans=0
for c in range(1,5):
    for b in range(1,5):
        for a in range(1,5):
            ans+=dp[N][c][b][a]
            
            ans%=MOD

print(ans)

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

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

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

for i in range(N):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                for m in range(1,5):
                    if (k==1 and l==2 and m==3) or (k==2 and l==1 and m==3) or (k==1 and l==3 and m==2):
                        continue
                    if (j==1 and k==2 and m==3) or (j==1 and l==2 and m==3):
                        continue
                    dp[i+1][k][l][m]=(dp[i+1][k][l][m]+dp[i][j][k][l])%MOD
ans=0
for k in range(5):
    for l in range(5):
        for m in range(5):
            ans=(ans+dp[N][k][l][m])%MOD
print(ans)

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


def main():
    MOD = 10**9 + 7
    N = int(input())
    memo = [{} for _ 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 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):
N=int(input())
MOD=10**9+7
dp=[[[[0]*5 for _ in range(5)] for _ in range(5)]for _ in range(N+1)]
ans=0
dp[0][0][0][0]=1
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                for l in range(1,5):
                    if j==1 and k==2 and l==3:continue
                    if j==1 and k==3 and l==2:continue
                    if j==3 and k==1 and l==2:continue
                    if i==1 and j==3 and l==2:continue
                    if i==1 and k==3 and l==2:continue
                    dp[n+1][j][k][l]+=dp[n][i][j][k]
for j in range(1,5):
    for k in range(1,5):
        for l in range(1,5):
            ans+=dp[N][j][k][l]
print(ans%MOD)

Solution (Python):
N = int(input())
mod = 10 ** 9 + 7
memo = [{} for _ 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())
dp = [[[[1] * 4 for i in range(4)] for j in range(4)] for k in range(n+1)]
dp[3][1][2][0] = 0
dp[3][1][0][2] = 0
dp[3][2][1][0] = 0
if n > 3:
    for i in range(4,n + 1):
        for j in range(4):
            for k in range(4):
                dp[i][3][j][k] = sum(dp[i-1][j][k])
                dp[i][0][j][k] = sum(dp[i-1][j][k])
                if j == 1 and k == 0:
                    dp[i][2][j][k] = 0
                else:
                    dp[i][2][j][k] = sum(dp[i - 1][j][k])
                if j == 0 and k == 2:
                    dp[i][1][j][k] = 0
                elif j == 2 and k == 0:
                    dp[i][1][j][k] = 0
                elif k == 2:
                    dp[i][1][j][2] = sum(dp[i - 1][j][k]) - dp[i - 1][j][2][0]
                elif j == 2:
                    dp[i][1][2][k] = sum(dp[i - 1][j][k]) - dp[i-1][2][k][0]
                else:
                    dp[i][1][j][k] = sum(dp[i - 1][j][k])
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[n][i][j][k] % (10**9 + 7)
print(ans % (10**9 + 7))

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

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

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

print(ans)

Solution (Python):
n = int(input())
mod = 10**9 + 7
acgt = ["A", "C", "G", "T"]
dp = {acgt[i]+acgt[j]+acgt[k]: 1 for i in range(4) for j in range(4) for k in range(4)}
dp["AGC"] = 0
dp["ACG"] = 0
dp["GAC"] = 0

for i in range(n-3):
    next_dp = {key: 0 for key in dp.keys()}
    for key, val in dp.items():
        for item in acgt:
            next_key = key + item
            if next_key[1:] == "AGC" or next_key[1:] == "ACG" or next_key[1:] == "GAC":
                continue
            elif next_key[0] + next_key[2:] == "AGC" or next_key[:2] + next_key[3] == "AGC":
                continue
            else:
                next_dp[next_key[1:]] = (next_dp[next_key[1:]] + val) % mod
    dp = next_dp
print(sum(dp.values()) % mod)

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









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 b==1 and c==3 and d==2: 
                        continue
                    if b==3 and c==1 and d==2: 
                        continue
                    if b==1 and c==2 and d==3:  
                        continue
                    if a==1 and c==3 and d==2:  
                        continue
                    if a==1 and b==3 and d==2:  
                        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[-1][a][b][c]
print(ans%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

N = int(input())
mod = 10 ** 9 + 7
L = [{} for i in range(101)]

def check(txt):
    if 'AGC' in txt:
        return False
    List = list(txt)
    for i in range(3):
        List[i], List[i+1] = List[i+1], List[i]
        if 'AGC' in ''.join(List):
            return False
        List[i], List[i+1] = List[i+1], List[i]
    return True
    
def dfs(i, txt):
    if i == N:
        return 1
    if txt in L[i]:
        return L[i][txt]
    ans = 0
    for char in 'AGCT':
        if check(txt[1:] + char):
            ans += dfs(i+1, txt[1:] + char)
    L[i][txt] = ans % mod
    return ans % mod

print(dfs(0, 'TTTT'))

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

print(ans % mod)

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

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