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
import itertools

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()

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

    A, C, G, T = 0, 1, 2, 3
    for i in range(n):
        for a, b, c, d in itertools.product(range(4), repeat=4):
            if b == A and c == G and d == C: continue
            if b == A and c == C and d == G: continue
            if b == G and c == A and d == C: continue
            if a == A and b == G and d == C: continue
            if a == A and c == G and d == C: continue
            dp[i + 1][b][c][d] = (dp[i + 1][b][c][d] + dp[i][a][b][c]) % MOD

    ans = 0
    for a, b, c in itertools.product(range(4), repeat=3):
        ans = (ans + dp[n][a][b][c]) % MOD

    return ans


print(main())

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 = int(1e9+7)
A = [[[ [0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(102)]

A[0][3][3][3] = 1






for x in range(N+1):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if A[x][i][j][k] == 0:
          continue
        for a in range(4):
          if (a == 2 and i == 1 and j == 0): continue
          if (a == 1 and i == 2 and j == 0): continue
          if (a == 2 and i == 0 and j == 1): continue
          if (a == 2 and i == 1 and k == 0): continue
          if (a == 2 and j == 1 and k == 0): continue
          A[x+1][a][i][j] = (A[x+1][a][i][j] + A[x][i][j][k]) % MOD
          
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans = (ans + A[N][i][j][k]) % MOD
      
print(ans)

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][3][3][3]=1
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 k==0 and l==2 and m==1: continue
                    elif k==2 and l==0 and m==1: continue
                    elif k==0 and l==1 and m==2: continue
                    elif j==0 and l==2 and m==1: continue
                    elif j==0 and k==2 and m==1: continue
                    else: dp[i+1][k][l][m]+=dp[i][j][k][l]
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):
N = int(input())

mod = 10 ** 9 + 7


dp = []
for _ in range(N):
    n = []
    for _ in range(4):
        l = []
        for _ in range(4):
            c = [0] * 4
            l.append(c)
        n.append(l)
    dp.append(n)

CHAR_A = 0
CHAR_C = 1
CHAR_G = 2
CHAR_T = 3

for c in range(4):
    for r in range(4):
        dp[1][CHAR_T][c][r] = 1

for i in range(2, N):
    for l in range(4):
        for c in range(4):
            for r in range(4):
                for a in range(4):
                    if c == CHAR_A and r == CHAR_G and a == CHAR_C:
                        continue
                    if c == CHAR_A and r == CHAR_C and a == CHAR_G:
                        continue
                    if c == CHAR_G and r == CHAR_A and a == CHAR_C:
                        continue
                    if l == CHAR_A and c == CHAR_G and a == CHAR_C:
                        continue
                    if l == CHAR_A and r == CHAR_G and a == CHAR_C:
                        continue
                    dp[i][c][r][a] += dp[i-1][l][c][r]

ans = 0
for l in range(4):
    for c in range(4):
        for r in range(4):
            ans += dp[N-1][l][c][r]

print(ans%mod)

Solution (Python):
import collections, itertools
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)]
dp[0][3][3][3] = 1
count = 0
for i in range(N):
    for c0, c1, c2, c3 in itertools.product(range(4), repeat=4):
        A1 = [c1, c2, c3]
        A2 = [c0, c2, c3]
        A3 = [c0, c1, c3]
        if A1 in [[0, 1, 2], [1, 0, 2], [0, 2, 1]] or [0, 1, 2] in [A2, A3]:
            continue
        dp[i + 1][c1][c2][c3] += dp[i][c0][c1][c2]
        dp[i + 1][c1][c2][c3] %= mod
        if i == N - 1:
            count += dp[i][c0][c1][c2]
            count %= mod
print(count)

Solution (Python):
import itertools

MOD = 10**9 + 7


def is_ok(p, c):
    if c == "C":
        if p[1:] == "AG" or p[1:] == "GA" or p[:2] == "AG" or (p[0] == "A" and p[2] == "G"):
            return False
    if c == "G" and p[1:] == "AC":
        return False
    return True


def main():
    N = int(input())
    ans = {"".join(x): 1 for x in itertools.product("ACGT", repeat=3)}
    for p in ["AGC", "ACG", "GAC"]:
        ans[p] = 0
    for _ in range(3, N):
        prev = ans
        ans = {"".join(x): 0 for x in itertools.product("ACGT", repeat=3)}
        for c in "ACGT":
            for p in prev:
                if is_ok(p, c):
                    nxt = p[1:] + c
                    ans[nxt] = (ans[nxt] + prev[p]) % MOD
    print(sum(ans.values()) % MOD)


if __name__ == "__main__":
    main()

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):
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 in range(4):
        for j in range(4):
            for k in 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 in range(4):
            for j in range(4):
                for k in 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 in range(4):
        for j in range(4):
            for k in range(4):
                ans += dp[n-3][i][j][k]
    print(ans%mod)
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

for n in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                if dp[n][a][b][c] == 0:
                    continue
                
                for l in range(4):
                    if l == 2 and a == 1 and b == 0:
                        continue
                    if l == 2 and a == 0 and b == 1:
                        continue
                    if l == 1 and a == 2 and b == 0:
                        continue
                    if l == 2 and a == 1 and c == 0:
                        continue
                    if l == 2 and b == 1 and c == 0:
                        continue

                    dp[n+1][l][a][b] += dp[n][a][b][c]
                    dp[n+1][l][a][b] %= MOD

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

Solution (Python):
import collections, itertools
N = int(input())
mod = 10**9 + 7
cd = collections.defaultdict
dp = cd(lambda: cd(lambda: cd(lambda: cd(int))))
dp[0][3][3][3] = 1
count = 0
for i in range(N):
    for c0, c1, c2, c3 in itertools.product(range(4), repeat=4):
        A1 = [c1, c2, c3]
        A2 = [c0, c2, c3]
        A3 = [c0, c1, c3]
        if A1 in [[0, 1, 2], [1, 0, 2], [0, 2, 1]] or [0, 1, 2] in [A2, A3]:
            continue
        dp[i + 1][c1][c2][c3] += dp[i][c0][c1][c2]
        dp[i + 1][c1][c2][c3] %= mod
        if i == N - 1:
            count += dp[i][c0][c1][c2]
            count %= mod
print(count)

Solution (Python):

from collections import defaultdict
from itertools import  product
def main():
    N=input()

    dp = [defaultdict(int) for i in range(101)]
    def ok(s):
        if s[:-1] in ("agc", "acg", "gac"):
            return False        
        if s[1:] in ("agc", "acg", "gac"):
            return False
        if s[0:2] == "ag" and s[3] == "c":
            return False
        if s[0] == "a" and s[2:4] == "gc": 
            return False
        return True

    if N==3:
        print(61)
        return

    for s in product("atgc", repeat=4):
        s="".join(s)
        if ok(s):
            dp[4][s]=1
        else:
            dp[4][s]=0
    
    i=5
    while i<=N:
        for k,v in dp[i-1].iteritems():
            for c in "atgc":
                n=k[1:]+c
                if ok(n):
                    dp[i][n] += dp[i-1][k]
        i+=1
    print(sum(dp[N].values()) % (10**9+7))
main()

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

chars = "ACGT"
cache = dict()

def is_valid(last4):
    if "AGC" in last4:
        return False
    for i in range(3):
        s = last4[:i] + last4[i + 1] + last4[i] + last4[i + 2:]
        if "AGC" in s:
            return False
    return True

def calc2(idx, last3):
    key = str(idx) + last3
    if key in cache:
        return cache[key]
    if idx == N:
        return 1
    ret = 0
    for c in chars:
        ns = last3 + c
        if is_valid(ns):
            ret = (ret + calc2(idx + 1, ns[1:])) % MOD
    ret = ret % MOD
    cache[key] = ret
    return ret
print(calc2(0, "   "))

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

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

Solution (Python):
import re,functools as f;d=f.lru_cache(999)(lambda n,b:n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7));print(d(int(input()),'TTT'))

Solution (Python):
from itertools import product
import re

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

dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG_pattern = r'.*AGC|.*ACG|.*GAC|A.GC|AG.C|'

for i in range(N):
    for last_3 in product('AGCT', repeat=3):
        last_3 = ''.join(last_3)
        for next_s in 'AGCT':
            if re.match(NG_pattern, last_3 + next_s).group():
                continue
            else:
                dp[i + 1][last_3[1:] + next_s] += dp[i][last_3]
                dp[i + 1][last_3[1:] + next_s] %= MOD

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

Solution (Python):
from itertools import product
import re
N = int(input())
MOD = 10 ** 9 + 7


dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG_pattern = r'.*AGC|.*ACG|.*GAC|A.GC|AG.C|'


for i in range(1, N + 1):
    for last_3 in product('AGCT', repeat=3):
        last_3 = ''.join(last_3)
        for pre_s in 'AGCT':
            if re.match(NG_pattern, pre_s + last_3).group():
                continue
            else:
                dp[i][pre_s + last_3[:-1]] += dp[i - 1][last_3]
                dp[i][pre_s + last_3[:-1]] %= MOD

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

Solution (Python):

















import numpy as np

N = int(input())

mod = 10 ** 9 + 7

memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1


for c in range(N):
    
    for i in range(4):
        
        for j in range(4):
            
            for k in range(4):
                
                for a in range(4):
                    
                    
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod


ans = 0

for i in range(4):
    
    for j in range(4):
        
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))

Solution (Python):
import sys
sys.setrecursionlimit(100000)
mod = 7 + 10 ** 9



N = int(input())
memo = {}

def agc(ppp, pp, p, i, memo):
    if i == N: return 1
    try:
        return memo[(ppp, pp, p, i)]
    except KeyError:
        Ans = 0
        if ppp == 1:
            if pp == 3:
                Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            elif pp == 1:
                if p == 2:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 4, i+1, memo)
                elif p == 3:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
                else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            elif p == 3:
                Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
        else:
            if pp == 1:
                if p == 2:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 4, i+1, memo)
                elif p == 3:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
                else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            elif pp == 3:
                if p == 1: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
                else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
        Ans %= mod
        memo[(ppp, pp, p, i)] = Ans
        return Ans

print(agc(0, 0, 0, 0, memo))

Solution (Python):
from itertools import product
import re
N = int(input())
MOD = 10 ** 9 + 7


dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG_pattern = r'AGC.*|ACG.*|GAC.*|A.GC|AG.C|'

for i in range(N):
    for last_3 in product('AGCT', repeat=3):
        last_3 = ''.join(last_3)
        for next_s in 'AGCT':
            if re.match(NG_pattern, last_3 + next_s).group():
                continue
            else:
                dp[i + 1][last_3[1:] + next_s] += dp[i][last_3]
                dp[i + 1][last_3[1:] + next_s] %= MOD


ans = 0
for key, value in dp[-1].items():
    if re.match(NG_pattern, key).group():
        continue
    ans += value
    ans %= MOD
print(ans)

Solution (Python):



get = lambda: int(raw_input().strip())

import collections


def valid(S):
    if "AGC" in S:
        return False
    for i in xrange(len(S)):
        S2 = S[:i] + S[i:i + 2][::-1] + S[i + 2:]
        if "AGC" in S2:
            return False
    return True


N = get()

mod = 10**9 + 7
count = collections.Counter({"": 1})
for _ in xrange(N):
    count2 = collections.Counter({"": 0})
    for pre in count:
        for X in "AGCT":
            cur = pre + X
            if valid(cur):
                count2[cur[-3:]] += count[pre] % mod
    count = count2


print sum(count.values()) % mod

Solution (Python):

dp = []
mod = 10 ** 9 + 7

def check(pre_3, pre_2, pre_1, now_num):
    if pre_2 == 0 and pre_1 == 2 and now_num == 1:
        return 1
    if pre_2 == 2 and pre_1 == 0 and now_num == 1:
        return 1
    if pre_2 == 0 and pre_1 == 1 and now_num == 2:
        return 1
    if pre_3 == 0 and pre_2 == 2 and now_num == 1:
        return 1
    if pre_3 == 0 and pre_1 == 2 and now_num == 1:
        return 1
    return 0

def print_ans(num):
    global dp, mod
    count = 0
    for pre_3 in range(4):
        for pre_2 in range(4):
            for pre_1 in range(4):
                count += dp[num][pre_3][pre_2][pre_1]
    print(count % mod)


def start_process(num):
    global dp, mod
    dp = [[[[0, 0, 0, 0] for k in range(4)] for j in range(4)] for i in range(num + 1)]
    dp[0][3][3][3] = 1
    for char_num in range(num):
        for pre_3 in range(4):
            for pre_2 in range(4):
                for pre_1 in range(4):
                    for now_num in range(4):
                        if check(pre_3, pre_2, pre_1, now_num):
                            continue
                        dp[char_num + 1][pre_2][pre_1][now_num] += dp[char_num][pre_3][pre_2][pre_1]
                        dp[char_num + 1][pre_2][pre_1][now_num] %= mod
    print_ans(num)

def main():
    num = int(input())
    start_process(num)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product
N = int(input())
MOD = 10 ** 9 + 7


dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG = {'AGC', 'ACG', 'GAC', 'AGGC', 'ACGC', 'ATGC', 'AGAC', 'AGTC'}

for i in range(N):
    for last_3 in product('AGCT', repeat=3):
        
        if ''.join(last_3) in NG:
            continue

        for next_s in 'AGCT':
            X = ''.join(last_3) + next_s
            
            if X in NG:
                continue
            else:
                dp[i + 1][X[1:]] += dp[i][X[:-1]]
                dp[i + 1][X[1:]] %= MOD

ans = 0
for key, value in dp[-1].items():
    if key not in NG:
        ans += value
        ans %= MOD
print(ans)

Solution (Python):
mod = 10**9 + 7
s = 'ACGT'
bad = ['AGC', 'ACG', 'GAC', 'ACGC', 'AGGC', 'ATGC', 'AGAC', 'AGGC', 'AGTC']

def valid(a):
    if a[0:3] in bad:
        return False
    if a[1:] in bad:
        return False
    if a in bad:
        return False
    return True

n = int(input())

dp = [[[1 for k in range(4)] for j in range(4)] for i in range(4)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            t = s[k]+s[j]+s[i]
            if t in ['AGC', 'ACG', 'GAC']:
                dp[i][j][k] = 0

for pos in range(3,n):
    nx = [[[0 for k in range(4)] for j in range(4)] for i in range(4)]

    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    t = s[k]+s[j]+s[i]+s[l]

                    if valid(t):
                        nx[l][i][j] += dp[i][j][k]
                        nx[l][i][j] %= mod
    dp = nx

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

Solution (Python):
















import numpy as np

N = int(input())

mod = 10 ** 9 + 7

memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1


for c in range(N):
    
    for i in range(4):
        
        for j in range(4):
            
            for k in range(4):
                
                for a in range(4):
                    
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod


ans = 0

for i in range(4):
    
    for j in range(4):
        
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))

Solution (Python):
import numpy as np
N=int(input())


dp = np.zeros((N+1, 4, 4, 4))
dp[0][3][3][3]=1
mod=1000000007
for c in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for a in range(4):
          if a==1 and i==2 and j==0:continue
          if a==2 and i==1 and j==0:continue
          if a==2 and i==0 and j==1:continue
          if a==2 and j==1 and k==0:continue
          if a==2 and i==1 and k==0:continue
          dp[c+1][a][i][j]+=dp[c][i][j][k]
          dp[c+1][a][i][j]%=mod
ans=0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=dp[N][i][j][k]
      ans%=mod
print(int(ans))

Solution (Python):
import numpy as np
N = int(input())
mod = 10**9+7
 
dp = np.zeros((N+1, 4, 4, 4))
dp[0][3][3][3] = 1
 
for i in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):        
        for new in range(4):
          if new == 2 and c1 == 1 and c2 == 0:
            continue
          if new == 2 and c1 == 0 and c2 == 1:
            continue
          if new == 1 and c1 == 2 and c2 == 0:
            continue
          if new == 2 and c1 == 1 and c3 == 0:
            continue
          if new == 2 and c2 == 1 and c3 == 0:
            continue
          dp[i+1][new][c1][c2] += dp[i][c1][c2][c3]
          dp[i+1][new][c1][c2] %= mod


res = 0

for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):        
      res += dp[N][c1][c2][c3]
 
print(int(res%mod))

Solution (Python):
N = int(input())
mod = 10 ** 9 + 7
D = [[[[0] * 4 for i in range(4)] for i in range(4)] for i in range(101)]

D[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 x in range(4):
                    if k == 0 and l == 1 and x == 2:
                        continue
                    if k == 0 and l == 2 and x == 1:
                        continue
                    if k == 1 and l == 0 and x == 2:
                        continue
                    if j == 0 and l == 1 and x == 2:
                        continue
                    if j == 0 and k == 1 and x == 2:
                        continue
                    D[i + 1][k][l][x] += D[i][j][k][l] % mod
                    D[i + 1][k][l][x] %= mod
                    
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += D[N][j][k][l]
            ans %= mod
                    
print(ans)

Solution (Python):
from functools import lru_cache
MOD = 1000000007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)

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

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

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


for L in range(N):
    for i in range(4):
        
        for j in range(4):
        
            for k in range(4):
                if (dp[L][i][j][k]==0): continue
                for a in range(4):
                    if (a == 2 and i == 1 and j == 0):    continue
                    if (a == 2 and i == 0 and j == 1):    continue
                    if (a == 1 and i == 2 and j == 0):    continue
                    if (a == 2 and i == 1 and k == 0):    continue
                    if (a == 2 and j == 1 and k == 0):    continue
                    
                    dp[L+1][a][i][j] += dp[L][i][j][k]
                    dp[L+1][a][i][j] %= modd
  
ans = 0         
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= modd
print(ans)

Solution (Python):
N = int(input())
def to_bit(num,digit = 3,N = 4):
    bit = [0] * digit
    for i in range(digit):
        bit[i] = num % N
        num = int((num - (num % N)) / N)
    bit[0],bit[2] = bit[2],bit[0] 
    return bit

DP_map = [[0] * 64 for _ in range(100)]
'''
A = 0
C = 1
G = 2
T = 3

NG in 3 char
AGC = 0 * 16 + 2 * 4 + 1 * 1 = 9
ACG = 0 * 16 + 1 * 4 + 2 * 1 = 6
GAC = 2 * 16 + 0 * 4 + 1 * 1 = 33
'''
DP_map[0] = [1] * 64
DP_map[0][6] = 0
DP_map[0][9] = 0
DP_map[0][33] = 0

C_NG = [9,33]
for i in range(N - 2):
    for j in range(64):
        bit = to_bit(j)
        now = DP_map[i][j]
        added_A = bit[1] * 16 + bit[2] * 4 + 0
        added_C = bit[1] * 16 + bit[2] * 4 + 1
        added_G = bit[1] * 16 + bit[2] * 4 + 2
        added_T = bit[1] * 16 + bit[2] * 4 + 3
        DP_map[i + 1][added_A] = (DP_map[i + 1][added_A] + now) % (int(1e9 + 7))
        DP_map[i + 1][added_T] = (DP_map[i + 1][added_T] + now) % (int(1e9 + 7))
        if added_G != 6:
            DP_map[i + 1][added_G] = (DP_map[i + 1][added_G] + now) % (int(1e9 + 7))

        if (added_C not in C_NG) and (bit[0] != 0 or (bit[2] != 2 and bit[1] != 2)):
            DP_map[i + 1][added_C] = (DP_map[i + 1][added_C] + now) % (int(1e9 + 7))



print(sum(DP_map[N-3]) % (int(1e9 + 7)))

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

def check(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 D[cur]:
        return D[cur][last3]
    if cur == N:
        return 1
    res = 0
    for c in 'ACGT':
        if check(last3 + c):
            res = (res + dfs(cur + 1, last3[1:] + c)) % mod
    D[cur][last3] = res
    return res
    
print(dfs(0, '000'))

Solution (Python):
import re,functools as f;d=f.lru_cache(None)(lambda n,b:n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7));print(d(int(input()),'TTT'))

Solution (Python):


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




import numpy as np
dp = np.zeros((N+1, 4, 4, 4), dtype="int64")

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


for l in range(N):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                
                if dp[l, c3, c2, c1] == 0:
                    continue
                
                for a in range(4):
                    
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[l + 1, c2, c1, a] += dp[l, c3, c2, c1] % MOD
                    dp[l + 1, c2, c1, a] %= MOD

print(dp[N, :, :, :].sum() % 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'))