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):
mod = 10**9+7
n = int(input())
if n < 3:
    print(4**n)
    exit()

ind = 0
d = {}

from itertools import product
for i, j, k in product(range(4), repeat=3):
    if any(a==0 and b==1 and c==2 for a,b,c in [[i,j,k], [j,i,k], [i,k,j]]):
        continue
    d[(i,j,k)] = ind
    d[ind] = (i,j,k)
    ind += 1


edge = [[] for i in range(ind)]
for i, j, k in product(range(4), repeat=3):
    if any((a,b,c)==(0,1,2) for a,b,c in [(i,j,k), (j,i,k), (i,k,j)]):
        continue
    for l in range(4):
        if (j,k,l) in d and (i,k,l) != (0,1,2) and (i,j,l) != (0,1,2):
            edge[d[i,j,k]].append(d[j,k,l])

dp = [1]*ind
for i in range(n-3):
    dp_next = [0]*ind
    for from_ in range(ind):
        for to in edge[from_]:
            dp_next[to] += dp[from_]
            dp_next[to] %= mod
    dp = dp_next
print(sum(dp)%mod)

Solution (Python):
import re
n = int(input())
memo = [{} for _ in range(n)]
MOD = 10**9 + 7

def check(string):
    if re.match(".*(AGC|GAC|ACG|A.?GC|AG.?C).*", string):
        return False
    return True


def dfs(string="", depth=0): 
    if depth == n:
        return 1

    if string in memo[depth]:
        return memo[depth][string]

    cnt = 0
    for i in "AGCT":
        next_string = string + i
        if check(next_string):
            cnt += dfs(string[-3:] + i, depth + 1)
            cnt %= MOD
    memo[depth][string] = cnt
    return cnt

print(dfs())

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

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



def genLegalChars(last3):

    if len(last3) != 3:
        print('Error! variable "last3" is not a string of length 3. None is returned in this function.')
        return None

    if last3[1:] == 'AG':
        return ['A','T','G']
    elif last3[1:] == 'GA':
        return ['A','T','G']
    elif last3[1:] == 'AC':
        return ['A','T','C']
    elif last3[0] == 'A' and last3[2] =='G':
        return ['A','G','T']
    elif last3[0:2] == 'AG':
        return ['A','G','T']
    else:
        return ['A','T','G','C']


def DFS(length, last3):

    
    if last3 in memo[length]:
        return memo[length][last3]

    
    if length == N:
        return 1

    curNodeVal = 0
    
    
    for char in genLegalChars(last3):
        curNodeVal = (curNodeVal + DFS(length+1, last3[1:]+char)) % MOD

    
    memo[length][last3] = curNodeVal

    return curNodeVal

print(DFS(0,'TTT'))

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 ''.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
    res =0
    for c in "ACGT":
        if ok(last3+c):
            res += dfs(cur+1,last3[1:]+c)
            res = res%mod
    memo[cur][last3]=res
    return res
mod = 10**9+7
N = int(input())
memo=[{} for _ in range(N+1)]

print(dfs(0,"TTT"))

Solution (Python):



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

MODULO = 10**9 + 7

def legal(prev4):
    for i in range(len(prev4)):
        check = list(prev4)
        if i >= 1:
            check[i], check[i-1] = check[i-1], check[i]
        if ''.join(check).count('AGC') >= 1:
            return False
    return True

def dfs(cur, prev3):

    if prev3 in memo[cur]:
        return memo[cur][prev3]
    if cur == N:
        return 1

    cnt = 0
    for c in 'ACGT':
        prev4 = prev3 + c
        if legal(prev4):
            cnt = (cnt + dfs(cur + 1, prev4[1:])) % MODULO

    memo[cur][prev3] = cnt
    return cnt

print '{}'.format(dfs(0, '___'))

Solution (Python):
from collections import defaultdict

n = int(input())
ch = ["A", "C", "G", "T"]
dic = {}
for i in range(4):
    for j in range(4):
        for k in range(4):
            dic[ch[i]+ch[j]+ch[k]] = 1
dic["AGC"] = 0
dic["GAC"] = 0
dic["ACG"] = 0

err = ["AGAC", "AGCC", "AGGC", "AGTC", "AAGC", "ACGC", "AGGC", "ATGC", ]

l = [dic]
for i in range(n-3):
    _dic = defaultdict(lambda: 0)
    for k, v in l[i].items():
        for j in range(4):
            s = k+ch[j]
            if s not in err:
                _dic[k[1:]+ch[j]] = (_dic[k[1:]+ch[j]]+v)%(10**9+7)
    _dic["AGC"] = 0
    _dic["GAC"] = 0
    _dic["ACG"] = 0
    l.append(_dic)

ans = 0
for v in l[n-3].values():
    ans = (ans+v)%(10**9+7)

print(ans)

Solution (Python):
from collections import defaultdict

n = int(input())
ch = ["A", "C", "G", "T"]
dic = {}
for i in range(4):
    for j in range(4):
        for k in range(4):
            dic[ch[i]+ch[j]+ch[k]] = 1
dic["AGC"] = 0
dic["GAC"] = 0
dic["ACG"] = 0

err = ["AGAC", "AGCC", "AGGC", "AGTC", "AAGC", "ACGC", "AGGC", "ATGC", ]

l = [dic]
for i in range(n-3):
    _dic = defaultdict(lambda: 0)
    for k, v in l[i].items():
        for j in range(4):
            s = k+ch[j]
            if s not in err:
                _dic[k[1:]+ch[j]] = (_dic[k[1:]+ch[j]]+v)%(10**9+7)
    _dic["AGC"] = 0
    _dic["GAC"] = 0
    _dic["ACG"] = 0
    l.append(_dic)

ans = 0
for v in l[n-3].values():
    ans = (ans+v)%(10**9+7)

print(ans)

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


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



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


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


print(ans % mod)

Solution (Python):
n=int(input())
m=[{}for i in range(n+1)]
w=10**9+7
def f(s):
    for i in range(4):
        t=list(s)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>0:
            return False
    return True
def a(p,q):
    if q in m[p]:
        return m[p][q]
    if p==n:
        return 1
    r=0
    for i in "AGCT":
        if f(q+i):
            r=(r+a(p+1,q[1:]+i))%w
    m[p][q]=r
    return r
print(a(0,"WHY"))

Solution (Python):
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]

ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]

i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())

ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]


def check(c0, c1, c2, c3):
    if c0 == 1 and c1 == 2 and c2 == 0:
        return False
    if c0 == 1 and c1 == 0 and c2 == 2:
        return False
    if c0 == 2 and c1 == 1 and c2 == 0:
        return False
    if c0 == 1 and c1 == 2 and c3 == 0:
        return False
    if c0 == 1 and c2 == 2 and c3 == 0:
        return False
    return True

def main(N):
    mod = int(1e+9) + 7
    
    dp1 = [0 for _ in range(4)]
    for c0 in range(4):
        if check(c0, -1, -1, -1) == False:
            continue
        dp1[c0] = 1
    if N == 1:
        ans = 0
        for c1 in range(4):
            ans += dp1[c1]
            ans %= mod
        print(ans)
        return
    
    dp2 = [[0 for _ in range(4)] for _ in range(4)]
    for c1 in range(4):
        for c0 in range(4):
            if check(c0, c1, -1, -1) == False:
                continue
            dp2[c0][c1] += dp1[c1]
            dp2[c0][c1] %= mod
    if N == 2:
        ans = 0
        for c1 in range(4):
            for c2 in range(4):
                ans += dp2[c1][c2]
                ans %= mod
        print(ans)
        return
    
    dp3 = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
    for c1 in range(4):
        for c2 in range(4):
            for c0 in range(4):
                if check(c0, c1, c2, -1) == False:
                    continue
                dp3[c0][c1][c2] += dp2[c1][c2]
                dp3[c0][c1][c2] %= mod
    if N == 3:
        ans = 0
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    ans += dp3[c1][c2][c3]
                    ans %= mod
        print(ans)
        return
    
    dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                dp[3][c1][c2][c3] = dp3[c1][c2][c3]
    
    for l in range(3, N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    for c0 in range(4):
                        if check(c0, c1, c2, c3) == False:
                            continue
                        dp[l+1][c0][c1][c2] += dp[l][c1][c2][c3]
                        dp[l+1][c0][c1][c2] %= mod
    ans = 0
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                ans += dp[N][c1][c2][c3]
                ans %= mod
    print(ans)

main(i2n())

Solution (Python):
import itertools
N = int(input())
AGCs = [
    'AGC',
    'GAC',
    'ACG',
    'AGAC',
    'AGGC',
    'AGTC',
    'ACGC',
    'ATGC',
]
seq = ["A", "G", "C", "T"]
from collections import Counter
memo = Counter()

count = 0
new_S = []
def memo_saiki(n, start_memo):
    if n==1:
        print(4)
        exit()
    if n==2:
        print(16)
        exit()
    memo = start_memo
    new_memo = Counter()
    for _ in range(n-3):
        for k, v in memo.items():
            for char in 'AGCT':
                target = k+char
                if any([agc in target for agc in AGCs]):
                    continue
                new_memo.update({target[-3:]: v})
        memo = new_memo
        new_memo = Counter()
    print(sum([v for v in memo.values()]) % (10**9 + 7))

def saiki(n=6):
    S = ['']
    new_S = []
    memo = {}
    for _ in range(n):
        for i, s in enumerate(S):
            for c in 'AGCT':
                memo[s[-3:]] = 1
                hoge = s[-3:] + c
                if any([agc in hoge for agc in AGCs]):
                    continue
                new_S.append(hoge)
        S = new_S
        new_S = []
    
    return S
memo_saiki(n=N, start_memo = Counter(saiki(3)))

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

for i in range(4, n+1):
	for j in range(4):
		for k in range(4):
			for l in range(4):
				dp[i][j][k][l] = 0
				for h in range(4):
					if l == C:
						if h == A and k == G:
							continue
						if h == A and j == G:
							continue
					dp[i][j][k][l] += dp[i-1][h][j][k]

				dp[i][j][k][l] %= MOD

	dp[i][A][G][C] = 0
	dp[i][A][C][G] = 0
	dp[i][G][A][C] = 0

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):
"""
agc
acg
gac
axgc
agxc
"""

n = int(input())
MOD = 10**9 + 7
dpa = [0, 0, 1]
dpc = [0, 0, 1]
dpg = [0, 0, 1]
dpt = [0, 0, 1]

for i in range(2, n+2):
    dpa.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
    dpc.append(dpa[i]-dpg[i-1] + dpc[i] + dpg[i]-dpa[i-1]-2*dpa[i-2] + dpt[i]-dpa[i-2])
    dpg.append(dpa[i] + dpc[i]-dpa[i-1]+dpg[i-2] + dpg[i] + dpt[i])
    dpt.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
    
print((dpa[n+1]+dpg[n+1]+dpc[n+1]+dpt[n+1]) % MOD)

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

all_suffix = []
base = ['A', 'C', 'G', 'T']

for char1 in base:
    for char2 in base:
        for char3 in base:
            all_suffix.append(char1+char2+char3)

len_all_suffix = len(all_suffix)

def judge(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).find('AGC') >= 0:
            return False
    return True

dp = [[0 for i in range(len_all_suffix)] for i in range(N-2)]

for i in range(len_all_suffix):
    if all_suffix[i]!='AGC' and all_suffix[i]!='GAC' and all_suffix[i]!='ACG':
        dp[0][all_suffix.index(all_suffix[i])] += 1

for i in range(1, N-2):
    for j in range(len_all_suffix):
        for char in base:
            if judge(all_suffix[j]+char):
                k = all_suffix.index(all_suffix[j][1:]+char)
                dp[i][k] += dp[i-1][j] % MOD

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

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

MOD = int(1e9+7)

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

suffixes = []
for suffix_1 in tokens:
    for suffix_2 in tokens:
        for suffix_3 in tokens:
            suffixes.append(suffix_1+suffix_2+suffix_3)

dp = [[0 for _ in suffixes] for _ in range(N+1)]

reverse_index = {}
for i,s in enumerate(suffixes):
    reverse_index[s] = i

def pprint(dp):
    N = len(dp)
    M = len(dp[0])

    for i in dp:
        st = ""
        for j in i:
            st += str(j)
            st += " "
        print(st)

for i,s in enumerate(suffixes):
    if not s in ['AGC', 'ACG', 'GAC']:
        dp[3][i]  = 1

valid_str_4 = set()

def swap(s, i ,j):
    s_new = list(s)
    s_new[i], s_new[j] = s[j], s[i]
    return ''.join(s_new)

def valid(str4):
    if 'AGC' in str4:
        return False
    for i in range(3):
        s_new = swap(str4, i, i+1)
        if 'AGC' in s_new:
            return False
    return True

for s in suffixes:
    for c in tokens:
        ss = s+c
        if valid(ss):
            valid_str_4.add(ss)

for n in range(4, N+1):
    for s in suffixes:
        for c in tokens:
            ss = s+c
            if ss in valid_str_4:
                dp[n][reverse_index[ss[1:]]] += dp[n-1][reverse_index[s]]

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

Solution (Python):

N=int(input())
memo = [{} for i in range(N)]

def check(last3,way,add,num):
    if num == 1:
        memo[num][last3+add] = way
    if num == 2:
        new_last3 = last3[-2:]+add
        if (new_last3!="AGC")&(new_last3!="GAC")&(new_last3!="ACG"):
            if new_last3 in memo[num]:
                memo[num][new_last3]+=way
            else:
                memo[num][new_last3]=way
    if num > 2:
        new_last3 = last3[-2:]+add
        new_last4 = last3[-3:]+add
        if (new_last3!="AGC")&(new_last3!="GAC")&(new_last3!="ACG"):
            if (new_last4!="AGAC")&(new_last4!="AGGC")&(new_last4!="AGTC")&(new_last4!="ATGC"):     
                if new_last3 in memo[num]:
                    memo[num][new_last3]+=way
                else:
                    memo[num][new_last3]=way

for c in "ATGC":
    memo[0][c] = 1

for i in range(1,N):
    for cj in memo[i-1]:
        last3 = cj
        way = memo[i-1][cj]
        for new_c in "ATCG":
            check(last3,way,new_c,i)
su = 0
for i in memo[N-1]:
    su += memo[N-1][i]
print(su%(10**9+7))

Solution (Python):
from collections import Counter
mod = 10**9+7
def check(s):
    ban = ["AGC", "ACG", "GAC", "AGGC", "ATGC", "AGTC"]
    for b in ban:
        if b in s:
            return False
    return True

n = int(input())
dp = [Counter() for i in range(n+1)]
dp[0]["RAN"] = 1

for i in range(n):
    for key, value in dp[i].items():
        for c in "ACTG":
            if check(key+c):
                dp[i+1][key[1:]+c]+=value % mod

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

Solution (Python):
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]


n = readInt()
M = 10 ** 9 + 7


dp = np.zeros((n + 1, 256), dtype=np.uint32)
dp[0, 255] = 1


for i in range(n):
    for j4 in [0, 64, 128, 192]:
        for j3 in [0, 16, 32, 48]:
            j43 = j4 + j3
            for j2 in [0, 4, 8, 12]:
                j432 = j43 + j2
                for j1 in range(4):
                    j = j432 + j1
                    l321 = 4 * (j3 + j2 + j1)
                    for l0 in range(4):
                        if (6 == (j3 + 4 * j1 + l0)) or (6 == (j3 + j2 + l0)) or (6 == (4 * j2 + 4 * j1 + l0)) or (6 == (16 * j1 + j2 + l0)) or (6 == (4 * j2 + 4 * l0 + j1)):
                            continue
                        l = l321  + l0
                        dp[i + 1, l] = (dp[i + 1, l] + dp[i, j]) % M

ret = 0
for v in dp[-1]:
    ret = (ret + v) % M
print(ret)

Solution (Python):
from collections import Counter

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

dp = [Counter() for i in range(N+1)]
dp[0]["TTT"] = 1


def ok(last4):
    bad = ["AGC", "ACG", "GAC", "AGGC", "ATGC", "AGTC"]
    for b in bad:
        if b in last4:
            return False
    return True

for i in range(N):
    for key, value in dp[i].items():
        for c in "AGCT":
            if ok(key+c):
                dp[i+1][key[1:]+c] += value % MOD

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

Solution (Python):

n = int(input())



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


dp[0][3][3][3] = 1
mod = 1000000007


for lens in range(n):
    
    for c1 in range(4):
        
        for c2 in range(4):
            
            for c3 in range(4):
                
                if dp[lens][c1][c2][c3] == 0:
                    continue
                
                for a in range(4):
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue

                    
                    dp[lens+1][a][c1][c2] += dp[lens][c1][c2][c3]
                    dp[lens+1][a][c1][c2] %= mod
 
ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[n][c1][c2][c3]
            ans %= mod
 
print(ans)

Solution (Python):
N = int(input())
mod = 1000000007
data = dict([(i+j+k, 1) for i in 'ACGT' for j in 'AGCT' for k in 'ACGT'])
data['AGC'] = 0
data['ACG'] = 0
data['GAC'] = 0
 
def check(text):
    if 'AGC' in text:
        return False
    if 'AGC' in text[1] + text[0] + text[2] + text[3]:
        return False
    if 'AGC' in text[0] + text[2] + text[1] + text[3]:
        return False
    if 'AGC' in text[0] + text[1] + text[3] + text[2]:
        return False
    else:
        return True

for x in range(0,N-3):
    new_data = dict([(i+j+k, 0) for i in 'ACGT' for j in 'AGCT' for k in 'ACGT'])
    for y in data.keys():
        for z in 'ACGT':
            if check(y+z):
                new_data[y[1:]+z] += data[y]%mod
    data = new_data.copy()

print(sum(data.values())%mod)

Solution (Python):
MOD = 10**9 + 7
memo = {}

def ok(last4):
    if "AGC" in last4:
        return False
    for i in range(3):
        s = list(last4)
        s[i], s[i+1] = s[i+1], s[i]
        if "AGC" in "".join(s):
            return False
    return True

def dfs(d, last3):
    if d < 0:
        return 1
    if not (d, last3) in memo:
        res = 0
        for c in "ACGT":
            last4 = last3 + c
            if ok(last4):
                res = (res + dfs(d-1, last4[-3:])) % MOD
        memo[d, last3] = res
    return memo[d, last3]

def solve(n):
    return dfs(n-1, "

n = int(input())
print(solve(n))

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

N = int(input())

countA = 4
countG = 4
countAG = 1
countGA = 1
countAC = 1
countAGX = 0
countAXG = 0
countAT = 1
ans = 16
nextnums = [0 for _ in range(7)]
for i in range(N-2):
    nextans = ans*4 - countAG - countGA - countAC - countAXG - countAGX
    nextA = ans
    nextG = ans - countAC
    nextAG = countA
    nextGA = countG
    nextAC = countA - countGA
    nextAGX = 2 * countAG
    nextAXG = countAT
    nextAT = countA

    ans = nextans % MOD
    countA = nextA % MOD
    countAC = nextAC % MOD
    countAG = nextAG % MOD
    countAGX = nextAGX % MOD
    countAT = nextAT % MOD
    countAXG = nextAXG % MOD
    countG = nextG % MOD
    countGA = nextGA % MOD
print(ans)

Solution (Python):
N = int(input())
mod = 10**9+7
data = dict([(i+j+k, 1) for i in "ACGT" for j in "ACGT" for k in "ACGT"])
data["AGC"] = 0
data["ACG"] = 0
data["GAC"] = 0

def check(text):
    one = text[0]
    two = text[1]
    three = text[2]
    four = text[3]
    if "AGC" in text:
        return False
    if "AGC" in two + one + three + four:
        return False
    if "AGC" in one + three + two + four:
        return False
    if "AGC" in one + two + four + three:
        return False
    return True


for i in range(N-3):
    new_data = dict([(i+j+k, 0) for i in "ACGT" for j in "ACGT" for k in "ACGT"])
    for s in data.keys():
        for c in "ACGT":
            if(not check(s+c)):
                continue
            new_data[s[1:]+c] += data[s]%mod
    data = new_data.copy()
print(sum(data.values())%mod)

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

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

dp[0][3][3][3] = 1
mod = 1000000007

for lens in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                
                if dp[lens][c1][c2][c3] == 0:
                    continue
                for a in range(4):
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[lens+1][a][c1][c2] += dp[lens][c1][c2][c3]
                    dp[lens+1][a][c1][c2] %= mod

ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[n][c1][c2][c3]
            ans %= mod

print(ans)

Solution (Python):
import itertools, math

N = int(input())

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

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

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

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

print(ans)

Solution (Python):
N = int(input())
dp = [[[[0 for i in range(0, 4)] for j in range(0, 4)] for k in range(0, 4)] for l in range(0, 101)]

dp[0][3][3][3] = 1
for n in range(0, 100):
    for i in range(0, 4):
        for j in range(0, 4):
            for k in range(0, 4):
                for l in range(0, 4):
                    if dp[n][i][j][k] == 0:
                        continue

                    if (j == 0 and k == 2 and l == 1
                        or j == 0 and k == 1 and l == 2
                        or j == 2 and k == 0 and l == 1
                        or i == 0 and k == 2 and l == 1
                        or i == 0 and j == 2 and l == 1):
                        continue
                    dp[n+1][j][k][l] += dp[n][i][j][k]

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

Solution (Python):
import itertools

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

ng_patterns3 = ['AGC', 'ACG', 'GAC']
ng_patterns4 = ['AAGC', 'AACG', 'ATGC', 'AGAC', 'AGTC', 'AGGC', 'AGCA', 'AGCT', 'AGCG', 'AGCC', 'ACGA', 'ACGT', 'ACGG',
                'ACGC', 'TAGC', 'TACG', 'TGAC', 'GAGC', 'GACA', 'GACT', 'GACG', 'GACC', 'GGAC', 'CAGC', 'CACG', 'CGAC']




def main():
    
    counts = {}
    for li in itertools.product('ATGC', repeat=3):
        s = ''.join(li)
        if s not in ng_patterns3:
            counts[s] = 1

    
    for _ in range(3, n):
        new_counts = {s: 0 for s in counts.keys()}
        for s3, count in counts.items():
            for c in 'ATGC':
                s4 = s3 + c
                if s4 not in ng_patterns4:
                    new_counts[s4[-3:]] += count % MOD
        counts = new_counts

    print(sum([c for c in counts.values()]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
MOD = 10**9+7
n = int(input())

basis = ['A', 'C', 'G', 'T']
cands = {}
for i in basis:
    for j in basis:
        for k in basis:
            ijk = i+j+k
            if ijk in ['AGC', 'GAC', 'ACG']:
                cands[ijk] = 0
            else:
                cands[ijk] = 1
for i in range(3, n):
    cands_tmp = {ijk:0 for ijk in cands.keys()}
    for k, v in cands.items():
        for l in basis:
            k_new = k+l
            if k_new[1:] in ['AGC', 'GAC', 'ACG']:
                pass
            elif k_new[0] == 'A' and 'G' in k_new[1:3] and k_new[3] == 'C':
                pass
            else:
               cands_tmp[k_new[1:]] += v
               cands_tmp[k_new[1:]] %= MOD
    cands = cands_tmp
    
print(sum(cands.values())%MOD)

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

dp = np.zeros((N+1,4,4,4),dtype="int")

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


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

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

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

print(dfs(0, 'TTT'))

Solution (Python):
import re
import itertools
chars = ["A","G","T","C"]
avoid = ["AGC","GAC","ACG",]
avoid_pattern = r"(.AGC|AGC.|.GAC|GAC.|.ACG|ACG.|A.GC|AG.C)"
MOD = (10**9) + 7
states = [ "".join([c1,c2,c3]) for  c1,c2,c3 in itertools.product(chars,chars,chars)]
states = [state for state in states if state not in avoid ]
def forward(states_num):
    update = dict([ (state,0) for state in  states_num.keys()])
    for current_state,current_num in states_num.items():
        for char in chars:
            if re.search(avoid_pattern,current_state + char) :
                pass
            else:
                new_state = current_state[1:]+char
                update[new_state] += current_num %MOD
    return update

def get_number(N):
    if N ==1 :
        return 4
    elif N ==2:
        return 16
    else:
        states_num = dict([ (state, 1)for state in states])
        for i in range(N-3):
            states_num = forward(states_num)
        return sum([  v for k,v in states_num.items()])%MOD

N = int(input())



print(get_number(N))

Solution (Python):
mod=10**9+7
n=int(input())
a=[{} for i in range(n+1)]
def C(last4):
    if last4[:3]=='AGC' or last4[1:]=='AGC':
        return False
    for i in range(3):
        tmp=list(last4)
        tmp[i], tmp[i+1]=tmp[i+1], tmp[i]
        if ''.join(tmp).count('AGC')>0:
            return False
    return True
a[0]['TTT']=1
for i in range(1, n+1):
    for k, v in a[i-1].items():
        for c in 'ACGT':
            if C(k+c):
                if k[1:]+c in a[i]:
                    a[i][k[1:]+c]+=v
                else:
                    a[i][k[1:]+c]=v
print(sum(a[n].values())%mod)

Solution (Python):


N = int(input())
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)) % (10 ** 9 + 7)
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Solution (Python):
import itertools
from collections import defaultdict

N=input()

if N==3:
	print 61
	quit()

dp=defaultdict(lambda: 0)	
a=0;g=1;c=2;t=3

n=4
for i,j,k,l in itertools.product( range(4), repeat=4 ):
	if l==c and j==g and i==a: continue
	elif l==c and k==g and i==a: continue
	elif l==c and k==g and j==a: continue
	elif k==c and j==g and i==a: continue
	elif l==c and k==a and j==g: continue
	elif k==c and j==a and i==g: continue
	elif l==g and k==c and j==a: continue
	elif k==g and j==c and i==a: continue
	dp[ (n,i,j,k,l) ]=1



for n in range(5,N+1):
	for i,j,k,l in itertools.product( range(4), repeat=4 ):
		if l==c and j==g and i==a: continue
		elif l==c and k==g and i==a: continue
		elif l==c and k==g and j==a: continue
		elif k==c and j==g and i==a: continue
		elif l==c and k==a and j==g: continue
		elif k==c and j==a and i==g: continue
		elif l==g and k==c and j==a: continue
		elif k==g and j==c and i==a: continue
	
		for m in range(4):
			dp[ (n,i,j,k,l) ]+=dp[ (n-1,j,k,l,m) ]


ans=0
for x,val in dp.items():
	n=x[0]
	if n==N:
		ans+=val

print ans%(10**9+7)