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 math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd

INF = float("inf")
MOD = int(1e9 + 7)

class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2

def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)

class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)

class graph:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    def append(self, v1, v2, cost=1):
        self.graph[v1].append((v2, cost))
    
    def dks(self, v):
        costs = [INF] * self.n
        costs[v] = 0
        done = [False] * self.n
        heap = heapque((0, v))
        while heap.que:
            c_cost, c_index = heap.pop()
            if done[c_index]:
                continue
            done[c_index] = True
            for n_index, n_cost in self.graph[c_index]:
                if c_cost + n_cost < costs[n_index]:
                    costs[n_index] = c_cost + n_cost
                    heap.push((costs[n_index], n_index))
        return costs

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

main()

Solution (Python):

import sys, math, fractions, itertools

MOD = 1000000007  
memo = []

def ok(last4: str):
    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(N: int, cur: int, last3: str):
    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(N, cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

def solve(N: int):
    print(dfs(N, 0, 'TTT'))
    return



def main():
    global memo
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    memo = [{} for i in range(N+1)]
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

dp = {}
chars = ['A', 'G', 'C', 'T']

for cs in itertools.product(chars, repeat = 3):
    word = ''.join(cs)
    if word == 'AGC' or word == 'ACG' or word == 'GAC':
      dp[(3, word)] = 0
    else:
      dp[(3, word)] = 1
      
def includeagc(word):
  return 'AGC' in word

for i in range(4, N + 1):
  for cs in itertools.product(chars, repeat = 4):
    cs = list(cs)
    word = ''.join(cs)
    words = [word]
    for j in range(3):
      cs[j], cs[j + 1] = cs[j + 1], cs[j]
      words.append(''.join(cs))
      cs[j], cs[j + 1] = cs[j + 1], cs[j]
    if not any(includeagc(word) for word in words):
      dp[(i, word[1:4])] = (dp.get((i, word[1:4]), 0) + dp.get((i - 1, word[0:3]), 0)) % MOD
      
ans = sum([k[1] for k in dp.items() if k[0][0] == N]) % MOD
print(ans)

Solution (Python):
n = int(input())
mod = 10**9+7
dp = [[[[0]*4 for _ in [0]*4] for _ in [0]*4] for _ in [0]*(n+1)]
dp[0][3][3][3] = 1
for i in range(1, n+1):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for k in range(4):
          if (c2, c3, k) == (0, 1, 2) : continue
          if (c2, c3, k) == (1, 0, 2) : continue
          if (c2, c3, k) == (0, 2, 1) : continue
          if (c1, c3, k) == (0, 1, 2) : continue
          if (c1, c2, k) == (0, 1, 2) : continue
          dp[i][c2][c3][k] += dp[i-1][c1][c2][c3]
ans = 0
for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      ans += dp[-1][c1][c2][c3]
      ans %= mod
print(ans)

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

for i in range(n):
    for b1 in range(4):
        for b2 in range(4):
            for b3 in range(4):
                for now in range(4):
                    if counter[i][b1][b2][b3] == 0:
                        continue
                    elif b1 == 0 and b3 == 1 and now == 2:
                        continue
                    elif b2 == 1 and b3 == 0 and now == 2:
                        continue
                    elif b2 == 0 and b3 == 2 and now == 1:
                        continue
                    elif b1 == 0 and b2 == 1 and now == 2:
                        continue
                    elif b2 == 0 and b3 == 1 and now == 2:
                        continue
                    else:
                        counter[i+1][b2][b3][now] += counter[i][b1][b2][b3]
                        counter[i+1][b2][b3][now] = counter[i+1][b2][b3][now] % mod

answer = 0
for b1 in range(4):
    for b2 in range(4):
        for b3 in range(4):
            answer += counter[n][b1][b2][b3]

print(answer % mod)

Solution (Python):
import sys
n=int(input())
if n==3:
  print(61)
  sys.exit()
mod=10**9+7
l=['A','C','G','T']
NG=['AGC','GAC','ACG']
NG2=['AAGC','ACGC','AGGC','ATGC','AGAC','AGCC','AGTC']
L=[]
for i1 in range(4):
  for i2 in range(4):
    for i3 in range(4):
      for i4 in range(4):
        L.append(l[i1]+l[i2]+l[i3]+l[i4])
dp=[[0 for i in range(256)] for j in range(n+1)]
for i in range(256):
  if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
    dp[4][i]=0
  else:
    dp[4][i]=1
for j in range(5,n+1):
  for i in range(256):
    if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
      dp[j][i]=0
    else:
      for i2 in range(256):
        if L[i2][1:4]==L[i][0:3]:
          dp[j][i]+=dp[j-1][i2]
    dp[j][i]%=mod
print(sum(dp[n])%mod)

Solution (Python):
from collections import defaultdict
N = int(input())
dp = [defaultdict(int) for _ in range(N+1)]
MOD = 10**9 + 7
dp[0]['TTT'] = 1


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


for n in range(N):
    for s, cnt in dp[n].items():
        for c in 'AGCT':
            ns = s+c
            if ok(ns):
                dp[n+1][ns[-3:]] = (dp[n+1][ns[-3:]]+cnt) % MOD

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

Solution (Python):
N = int(input())
ans = 0
M = (10**9)+7
dic = {}
pdic = {}
pdic['AAA'] = 1
pdic['AAC'] = 1
pdic['AAG'] = 1
pdic['AAT'] = 1
pdic['ACA'] = 1
pdic['ACC'] = 1
pdic['ACG'] = 0
pdic['ACT'] = 1
pdic['AGA'] = 1
pdic['AGC'] = 0
pdic['AGG'] = 1
pdic['AGT'] = 1
pdic['ATA'] = 1
pdic['ATC'] = 1
pdic['ATG'] = 1
pdic['ATT'] = 1
pdic['CAA'] = 1
pdic['CAC'] = 1
pdic['CAG'] = 1
pdic['CAT'] = 1
pdic['CCA'] = 1
pdic['CCC'] = 1
pdic['CCG'] = 1
pdic['CCT'] = 1
pdic['CGA'] = 1
pdic['CGC'] = 1
pdic['CGG'] = 1
pdic['CGT'] = 1
pdic['CTA'] = 1
pdic['CTC'] = 1
pdic['CTG'] = 1
pdic['CTT'] = 1
pdic['GAA'] = 1
pdic['GAC'] = 0
pdic['GAG'] = 1
pdic['GAT'] = 1
pdic['GCA'] = 1
pdic['GCC'] = 1
pdic['GCG'] = 1
pdic['GCT'] = 1
pdic['GGA'] = 1
pdic['GGC'] = 1
pdic['GGG'] = 1
pdic['GGT'] = 1
pdic['GTA'] = 1
pdic['GTC'] = 1
pdic['GTG'] = 1
pdic['GTT'] = 1
pdic['TAA'] = 1
pdic['TAC'] = 1
pdic['TAG'] = 1
pdic['TAT'] = 1
pdic['TCA'] = 1
pdic['TCC'] = 1
pdic['TCG'] = 1
pdic['TCT'] = 1
pdic['TGA'] = 1
pdic['TGC'] = 1
pdic['TGG'] = 1
pdic['TGT'] = 1
pdic['TTA'] = 1
pdic['TTC'] = 1
pdic['TTG'] = 1
pdic['TTT'] = 1
for i in range(N-3):
  for k in pdic.keys():
    k = str(k)
    if k=='ACG' or k=='AGC' or k=='GAC':
      dic[k] = 0
    elif k[1:]=='GC':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    elif k[0]=='G' and k[2]=='C':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    else:
      dic[k] = pdic['A'+k[:-1]]+pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
  for k in pdic.keys():
    pdic[k] = dic[k]
if N==3:
  print(61)
else:
  for v in dic.values():
    ans += v
    ans = ans % M
  print(ans)

Solution (Python):
N = int(input())
mod = int(1E9+7)

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[2][i][j][k] = 1
dp[2][2][1][0] = 0
dp[2][1][2][0] = 0
dp[2][2][0][1] = 0

for i in range(3, N):
    for x in range(4):
        for y in range(4):
            dp[i][0][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][1][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][2][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][3][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
    
    dp[i][2][3][1] -= dp[i-1][3][1][0]
    dp[i][2][1][3] -= dp[i-1][1][3][0]
    dp[i][2][0][1] -= dp[i-1][0][1][0]
    dp[i][2][1][0] -= dp[i-1][1][0][0]
    dp[i][2][1][1] -= dp[i-1][1][1][0]
    
    dp[i][1][2][0] = 0
    dp[i][2][0][1] = 0
    dp[i][2][1][0] = 0
    
    


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

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



dp = [[[[0 for p in range(4)] for q in range(4)] for r in range(4)] for s in range(n)]
dp[0] = [[[1 for p in range(4)] for q in range(4)] for r in range(4)]  
dp[0][0][1][2] = 0  
dp[0][0][2][1] = 0  
dp[0][1][0][2] = 0  

for i in range(n-3):
    for j in range(4):  
        for k in range(4):  
            for l in range(4):  
                for m in range(4):  
                    if j==0 and k==1 and m==2:  
                        continue
                    if j==0 and l==1 and m==2:  
                        continue
                    dp[i+1][k][l][m] += dp[i][j][k][l]  
                    dp[i+1][k][l][m] %= MOD
                dp[i+1][0][1][2] = 0  
                dp[i+1][0][2][1] = 0  
                dp[i+1][1][0][2] = 0  

ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[n-3][j][k][l]
            ans %= MOD

print(ans)

Solution (Python):
import itertools






mod = 10 ** 9 + 7
N = int(input())
keys = [i + j + k for i, j, k in itertools.product('ACGT', repeat=3)]
dp = [dict() for _ in range(N)]
for i in range(N):
    for key in keys:
        dp[i][key] = 0

for key in keys:
    if key in ['AGC', 'ACG', 'GAC']:
        val = 0
    else:
        val = 1
    dp[2][key] = val

for i in range(2, N - 1):
    for key, val in dp[i].items():
        nexts = {'A', 'C', 'G', 'T'}
        if key[1:] == 'AG':
            nexts.discard('C')
        elif key[1:] == 'AC':
            nexts.discard('G')
        elif key[1:] == 'GA':
            nexts.discard('C')
        if key[0] == 'A' and (key[1] == 'G' or key[2] == 'G'):
            nexts.discard('C')
        for ne in nexts:
            next_key = key[1:] + ne
            dp[i + 1].setdefault(next_key, 0)
            dp[i + 1][next_key] += val
print(sum(dp[N - 1].values()) % 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('ACG') >= 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 = [[0 for i in range(4)] for j in range(N)]
mod = 10**9 + 7

for i in range(N):
    if(i == 0):
        for j in range(4):
            dp[0][j] = 1
    elif(i == 1):
        for j in range(4):
            dp[1][j] = 4
    elif(i == 2):
        base = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]
        dp[i][0] += base
        dp[i][1] += base - dp[i-2][2] - dp[i-2][0]
        dp[i][2] += base - dp[i-2][0]
        dp[i][3] += base
        for j in range(4):
            dp[i][j] %= mod
    else:
        base = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]
        dp[i][0] += base
        dp[i][1] += base - dp[i-3][0]*3 - dp[i-2][2] - dp[i-2][0]
        dp[i][2] += base - (dp[i-2][0] - dp[i-3][2])
        dp[i][3] += base
        for j in range(4):
            dp[i][j] %= mod
    
print((dp[N-1][0] + dp[N-1][1] + dp[N-1][2] + dp[N-1][3])%mod)

Solution (Python):
import copy

MOD = 10 ** 9 + 7

def make_list(*args):
	r = [0] * args[-1]
	for n in args[len(args) - 2::-1]:
		r = [copy.deepcopy(r) for _ in range(n)]
	return r

N = int(input())

dp = make_list(N + 1, 5, 5, 5)
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 == 3 and l == 2:
						continue
					
					if j == 3 and k == 1 and l == 2:
						continue
					
					if j == 1 and k == 2 and l == 3:
						continue
					
					if i == 1 and k == 3 and l == 2:
						continue
					
					if i == 1 and j == 3 and l == 2:
						continue
					dp[n + 1][j][k][l] += dp[n][i][j][k]
					dp[n + 1][j][k][l] %= MOD

r = 0
for i in range(1, 5):
	for j in range(1, 5):
		for k in range(1, 5):
			r += dp[N][i][j][k]
			r %= MOD

print(r)

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

MOD = 10**9+7
dp = [[[[0]*4 for i in range(4)] for j in range(4)] for k in range(N+1)]
dp[0][3][3][3] = 1
'''
for i in range(4):
    for j in range(4):
        for k in range(4):
            if k == 2 and j == 1 and i == 0:
                continue
            if k == 1 and j == 2 and i == 0:
                continue
            if k == 2 and j == 0 and i == 1:
                continue
            dp[3][i][j][k] = 1
'''
for n in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[n][i][j][k] == 0:
                    continue
                for new in range(4):
                    if new == 2 and i == 1 and j == 0:
                        continue
                    if new == 1 and i == 2 and j == 0:
                        continue
                    if new == 2 and i == 0 and j == 1:
                        continue
                    if new == 2 and i == 1 and k == 0:
                        continue
                    if new == 2 and j == 1 and k == 0:
                        continue
                    dp[n+1][new][i][j] += dp[n][i][j][k]
                    dp[n+1][new][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(ans)

Solution (Python):
def main():
    N = int(input())
    dp = [[[[0 for _ in range(4)] for _ in range(4)]
           for _ in range(4)] for _ in range(101)]
    dp[0][3][3][3] = 1
    mod = 10 ** 9 + 7
    for n in range(100):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    if dp[n][i][j][k] == 0:
                        continue
                    for a in range(4):
                        if (j == 0 and i == 1 and a == 2) or \
                            (j == 0 and i == 2 and a == 1) or \
                            (j == 1 and i == 0 and a == 2) or \
                            (k == 0 and j == 1 and a == 2) or \
                                (k == 0 and i == 1 and a == 2):
                            continue
                        dp[n + 1][a][i][j] += dp[n][i][j][k]
                        dp[n + 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(ans)


main()

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

s = "ATGC"
t = ["AGC", "ACG", "GAC"]
d = [defaultdict(int), {x+y+z: 1 for x in s for y in s for z in s if x+y+z not in t}]



for i in range(4, n+1):
    a = i%2
    b = (i-1)%2

    d[a] = defaultdict(int)
    for k in d[b]:
        for c in s:
            if "AGC" not in [k[1:]+c, k[0]+k[2]+c, k[2]+k[1]+c, k[1]+c+k[2], k[0]+k[1]+c]:
                d[a][k[1:]+c] += d[b][k]
                d[a][k[1:]+c] %= MOD

print(sum(d[n%2].values()) % MOD)

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

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

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i - 1], t[i] = t[i], t[i - 1]
        if ''.join(t).count('AGC') >= 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=[[[[0,0,0,0] for _ in range(4)] for _ in range(4)] for _ in range(101)]
mod=10**9+7
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[3][i][j][k]=1
dp[3][1][2][0]=0
dp[3][2][1][0]=0
dp[3][1][0][2]=0

for m in range(4,n+1):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if i==0:
          for l in range(4):
            dp[m][i][j][k]+=dp[m-1][j][k][l]
          dp[m][i][j][k]%=mod
        elif i==1:
          if j==2 and k==0:
            dp[m][i][j][k]=0
          elif j==0 and k==2:
            dp[m][i][j][k]=0
          elif j==2 and k!=0:
            for l in range(4):
              if l==0:
                continue
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
          elif j!=0 and k==2:
            for l in range(4):
              if l==0:
                continue
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
          else:
            for l in range(4):
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
        elif i==2:
          if j==1 and k==0:
            dp[m][i][j][k]=0
          else:
            for l in range(4):
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
        elif i==3:
          for l in range(4):
            dp[m][i][j][k]+=dp[m-1][j][k][l]
          dp[m][i][j][k]%=mod
ans=0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=dp[n][i][j][k]
      ans%=mod
print(ans%mod)

Solution (Python):
N = int(input())
mod = 10**9+7
dp = [[[[0]*4 for _ in [0]*4] for _ in [0]*4] for _ in [0]*(N+1)]
dp[0][3][3][3] = 1
for i in range(1,N+1):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for k in range(4):
                    if (c2,c3,k) == (0,1,2) : continue
                    if (c2,c3,k) == (1,0,2) : continue
                    if (c2,c3,k) == (0,2,1) : continue
                    if (c1,c3,k) == (0,1,2) : continue
                    if (c1,c2,k) == (0,1,2) : continue
                    dp[i][c2][c3][k] += dp[i-1][c1][c2][c3]
ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[-1][c1][c2][c3]
            ans %= mod
print(ans)

Solution (Python):
INF = 10**9+7
N = int(input())
dp = [[[[0]*4 for k in range(4)] for j in range(4)] for i in range(110)]

res = 0
dp[0][0][0][0]=1
for n in range(1,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (i,j,k)==(1,2,3):continue
                    if (i,j,k)==(2,1,3):continue
                    if (i,j,k)==(1,3,2):continue
                    if (j,k,l)==(1,2,3):continue
                    if (j,k,l)==(2,1,3):continue
                    if (j,k,l)==(1,3,2):continue
                    if (i,k,l)==(1,2,3):continue
                    if (i,j,l)==(1,2,3):continue
                    dp[n][j][k][l]+=dp[n-1][i][j][k]
                    dp[n][j][k][l]%=INF
for i in range(4):
    for j in range(4):
        for k in range(4):
            res = (res+dp[N][i][j][k])%INF
print(res)

Solution (Python):
N = int(input())
chars = 'AGCT'

dp = {}
for c1 in chars:
    for c2 in chars:
        for c3 in chars:
            dp[c1+c2+c3] = 1
dp['AGC'] = dp['ACG'] = dp['GAC'] = 0

def isValid(s):
    return not (s[1:] == 'AGC' or
                s[1:] == 'ACG' or
                s[1:] == 'GAC' or
                (s[0] == 'A' and s[3] == 'C' and 'G' in s[1:3]) )
	
for i in range(N-3):
    dp_new = {k:0 for k in dp}
    for k in dp:
      	for c in chars:
            if isValid(k+c):
                dp_new[k[1:]+c] += dp[k]
    dp = dp_new

print(sum([v for k,v in dp.items()]) % 1000000007)

Solution (Python):


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

dp = [[[[0]*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):
            
            if dp[i][j][k] == 0:
                continue
            
            for l in range(4):
                
                for a in range(4):
                    

                    
                    if a == 2 and j == 1 and k == 0:continue
                    
                    if a == 2 and j == 0 and k == 1:continue
                    
                    if a == 1 and j == 2 and k == 0:continue
                    
                    if a == 2 and j == 1 and l == 0:continue
                    
                    if a == 2 and k == 1 and l == 0:continue

                    
                    dp[i+1][a][j][k] += dp[i][j][k][l]
                    dp[i+1][a][j][k] %= 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):





n = int(input())

memo = [{} for i in range(n+1)]
mod = 10**9 + 7

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

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    
    for c in 'AGCT':
        
        if ok(last3 + c):
            
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    
    memo[cur][last3] = ret
    return ret
print(dfs(0,'TTT'))

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

import sys
sys.setrecursionlimit(100000)

memo = {}
def ok(last4):
    if 'AGC' in last4:
        return False
    if last4[:3] == 'ACG' or last4[:3] == 'GAC':
        return False
    if last4[1:] == 'ACG' or last4[1:] == 'GAC':
        return False
    if last4[0] == 'A' and last4[2:] == 'GC':
        return False
    if last4[:2] == 'AG' and last4[3] == 'C':
        return False
    return True

def dfs(h, last3):
    if (h, last3) in memo:
        return memo[h, last3]
    
    if h == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3+c):
            ret = (ret + dfs(h+1, last3[1:]+c)) % mod
    memo[h, last3] = ret
    return ret

print(dfs(0, 'TTT'))

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

def concat(li):
  return ''.join([str(l) for l in li])

import itertools
def init_dp(n):
  dp = {}
  for s in itertools.product(['A', 'G', 'C', 'T'],['A', 'G', 'C', 'T'],['A', 'G', 'C', 'T']):
    st = concat(s)
    if check3(st) == 0:
        dp[st] = n
  return dp

def check3(s):
  s1 = s
  s2 = s[0] + s[2] + s[1]
  s3 = s[1] + s[0] + s[2]
  if 'AGC' in '_'.join([s1, s2, s3]):
  	return 1
  return 0

def check4(s):
  s1 = s
  s2 = s[1] + s[0] + s[2] + s[3]
  s3 = s[0] + s[2] + s[1] + s[3]
  s4 = s[0] + s[1] + s[3] + s[2]
  if 'AGC' in '_'.join([s1, s2, s3, s4]):
  	return 1
  return 0
  
def update_dp(dp, next_dp, k, s):
  next4 = k + s  
  if check4(next4) == 0:
	  next_dp[next4[1:]] += dp[k]
  return next_dp

dp = init_dp(1)
for i in range(3, N):
  next_dp = init_dp(0)
  for k in dp.keys():
    for s in ['A', 'G', 'C', 'T']:
      next_dp = update_dp(dp, next_dp, k, s)
  dp = next_dp.copy()

mx = 10**9 + 7
ans = 0
for k in dp.keys():
  ans += dp[k] 
  ans %= mx
print(ans)

Solution (Python):
lo = int(input())
ngl = ["AGC", "ACG", "GAC", "AAGC", "AGGC", "ATGC", "ACGC", "AGAC", "AGGC", "AGTC", "AGCC"]
memo = {}


def ac(s, dep):
    if s == "":
        rv = 0
        for sv in "AGCT":
            rv += ac(s + sv, dep+1)
        return rv % (10 ** 9 + 7)
    else:
        if len(s) == lo:
            if chs(s):
                return 1
            else:
                return 0
        else:
            if len(s) >= 4:
                if chs(s):
                    if (s[-3:] + ":" + str(dep)) in memo:
                        return memo.get(s[-3:] + ":" + str(dep))
                    else:
                        rv = 0
                        for sv in "AGCT":
                            rv += ac(s + sv, dep+1)
                        memo[s[-3:] + ":" + str(dep)] = rv
                        return rv % (10 ** 9 + 7)
                else:
                    return 0
            else:
                rv = 0
                for sv in "AGCT":
                    rv += ac(s + sv, dep+1)
                return rv % (10 ** 9 + 7)


def chs(s):
    for ng in ngl:
        if ng in s:
            return False
    return True


print(ac("", 0))

Solution (Python):
import numpy as np

n = int(input())

"""
directly out
*ag c
indirectly

*ga c
*ac g
a*g c
ag* c

a =0
c =1
g = 2
t = 3
"""

l = ["a","g","c","t"]
bef = {"a":1,"g":1,"c":1,"t":1}
d = {}
m = {}

for i in range(4):
    for j in range(4):
        for k in range(4):
            temp = l[i]+l[j]+l[k]
            d[temp] = 1
d["agc"] = 0
d["acg"] = 0
d["gac"] = 0





for key in d.keys():
    if key[1:] == "ag":
        m[key] = {key[1:]+"a":1,key[1:]+"g":1,key[1:]+"c":0,key[1:]+"t":1}
    elif key[1:] == "ga":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    elif key[1:] == "ac":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 0, key[1:] + "c": 1, key[1:] + "t": 1}
    elif key[0] == "a" and key[2] == "g":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    elif key[0] == "a" and key[1] == "g":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    else:
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 1, key[1:] + "t": 1}

mod = 10**9 +7
for i in range(n-3):
    buf = {}
    for i in range(4):
        for j in range(4):
            for k in range(4):
                temp = l[i] + l[j] + l[k]
                buf[temp] = 0
    for key in d.keys():
        for to in m[key].keys():
            buf[to] += d[key]*m[key][to]
            buf[to] = buf[to]%mod
    d = buf

ans = 0
for key in d.keys():
    ans += d[key]
print(ans%mod)

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

dp[0][T][T][T] = 1
for m in range(n):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for c in range(4):
                    
                    
                    
                    
                    
                    
                    if            j == A and k == G and c == C: continue
                    if i == A            and k == G and c == C: continue
                    if            j == G and k == A and c == C: continue
                    if            j == A and k == C and c == G: continue
                    if i == A and j == G            and c == C: continue
                    dp[m + 1][j][k][c] += dp[m][i][j][k]
                    dp[m + 1][j][k][c] %= MOD

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

print(ans)