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):
from itertools import product
from copy import deepcopy

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

comp = {"A": 0, "C": 1, "G": 2, "T": 3}

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

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


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

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

    return True


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

    return ret


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

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

print(ans)

Solution (Python):

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

def judge(last4):
    for i in range(4):
        t=list(last4)
        if i<3:
            t[i],t[i+1]=t[i+1],t[i]
        s=''.join(t)
        if 'AGC' in s:
            return False
    return True

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

print(dfs(0,'TTT'))

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)]
for k in range(4):
    for l in range(4):
        for m in range(4):
            flg=(k==0 and l==1 and m==2) or (k==0 and l==2 and m==1) or (k==2 and l==0 and m==1)
            if not flg:
                dp[3][k][l][m]=1
        

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

g_cnt = 0
def main():
    N = I()
    dp = [[[[0 for _ in range(4)] for ____ in range(4)] for __ in range(4)] for ___ in range(N+1)]
    s2i = {
        'A': 0,
        'G': 1,
        'C': 2,
        'T': 3,
    }
    dp[0][3][3][3] = 1

    for i in range(0, N):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for char in ['A', 'G', 'C', 'T']:
                        if char == 'G':
                            if k == s2i['A'] and l == s2i['C']:
                                continue
                        elif char == 'C':
                            if j == s2i['A'] and l == s2i['G']:
                                continue
                            if k == s2i['G'] and l == s2i['A']:
                                continue
                            if k == s2i['A'] and l == s2i['G']:
                                continue
                            if j == s2i['A'] and k == s2i['G']:
                                continue
                        else:
                            pass
                        dp[i+1][k][l][s2i[char]] += dp[i][j][k][l]
                        dp[i+1][k][l][s2i[char]] %= mod

    cnt = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                cnt += (dp[N][j][k][l] % mod)
                cnt %= mod
    print(cnt)
main()

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

dp = [0]*64





def test(w,x,y,z):
    s = ((0,1,2),(1,0,2),(0,2,1))
    if (x,y,z) not in s and (w,y,z)!=(0,1,2) and (w,x,z)!=(0,1,2):
        return True
    else:
        return False

for i in range(64):
    x,y,z = i>>4,(i>>2)&3,i&3
    if test(3,x,y,z):
        dp[i]=1

for i in range(3,n):
    dp2 = [0]*64
    for j in range(64):
        w,x,y = j>>4,(j>>2)&3,j&3
        """
        if w not in (0,1,2,3) or x not in (0,1,2,3) or y not in ( 0,1,2,3):
            print(j,w,x,y)
            exit()
        """
        for z in range(4):
            if test(w,x,y,z):
                dp2[(x<<4)+(y<<2)+z]+=dp[j]
    dp = dp2



ans = sum(dp)
ans%=10**9+7
print(ans)

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

dp = [[0]*64 for i in range(n)]





def test(w,x,y,z):
    s = ((0,1,2),(1,0,2),(0,2,1))
    if (x,y,z) not in s and (w,y,z)!=(0,1,2) and (w,x,z)!=(0,1,2):
        return True
    else:
        return False

for i in range(64):
    x,y,z = i>>4,(i>>2)&3,i&3
    if test(3,x,y,z):
        dp[2][i]=1

for i in range(3,n):
    for j in range(64):
        w,x,y = j>>4,(j>>2)&3,j&3
        """
        if w not in (0,1,2,3) or x not in (0,1,2,3) or y not in ( 0,1,2,3):
            print(j,w,x,y)
            exit()
        """
        for z in range(4):
            if test(w,x,y,z):
                dp[i][(x<<4)+(y<<2)+z]+=dp[i-1][j]



ans = sum(dp[n-1])
ans%=10**9+7
print(ans)

Solution (Python):
def main():
    N = int(input())
    mod = 10**9 + 7
    v = {'TTTT': 1}
    for _ in range(N):
        u = {}
        for c, k in v.items():
            c = c[1:]
            for i in 'ACGT':
                t = c + i
                if 'AGC' in t or 'GAC' in t or 'ACG' in t or (t[0] == 'A' and t[2:] == 'GC') or (t[:2] == 'AG' and t[3] == 'C'):
                    continue
                u[t] = (u.get(t, 0) + k) % mod
        v = u
    print(sum(v.values()) % mod)

main()

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

MOD = 10**9 + 7


dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]


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


for i in range(N-3):
    
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue 
                    if pp==0 and p==2 and n==1: continue 
                    if pp==1 and p==0 and n==2: continue 
                    if ppp==0 and p==1 and n==2: continue 
                    if ppp==0 and pp==1 and n==2: continue 
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD

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

Solution (Python):
import numpy as np
N = int(input())
p = 10 ** 9 + 7
dp = np.zeros((N + 1, 4, 4, 4), dtype = "int64")


dp[0][3][3][3] = 1
for len in range(0, N):
    for c3 in range(0, 4):
        for c2 in range(0, 4):
            for c1 in range(0, 4):
                for newchar in range(0, 4):
                    
                    if c2 == 0 and c1 == 1 and newchar == 2: continue
                    if c2 == 1 and c1 == 0 and newchar == 2: continue
                    if c2 == 0 and c1 == 2 and newchar == 1: continue
                    if c3 == 0 and c1 == 1 and newchar == 2: continue
                    if c3 == 0 and c2 == 1 and newchar == 2: continue
                    dp[len + 1][c2][c1][newchar] += dp[len][c3][c2][c1]
                    dp[len + 1][c2][c1][newchar] %= p

ans = dp[N].sum() % p
print(ans)

Solution (Python):
def main():
    N = int(input())
    dp = [[[[0
            for c3 in range(4)]
            for c2 in range(4)]
            for c1 in range(4)]
            for L  in range(N+1)]
    dp[0][3][3][3] = 1
    for L in range(1, N+1):
        for c3 in range(4):
            for c2 in range(4):
                for c1 in range(4):
                    for c0 in range(4):
                        if ((c2 == 0 and c1 == 2 and c0 == 1) or
                            (c2 == 2 and c1 == 0 and c0 == 1) or
                            (c2 == 0 and c1 == 1 and c0 == 2) or
                            (c3 == 0 and c2 == 2 and c0 == 1) or
                            (c3 == 0 and c1 == 2 and c0 == 1)):
                            continue
                        dp[L][c0][c1][c2] += dp[L-1][c1][c2][c3]
                        dp[L][c0][c1][c2] %= 10**9 + 7
    ans = 0
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                ans += dp[N][c1][c2][c3]
                ans %= 10**9 + 7
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
N = int(input())
MOD = 10**9+7
dp = np.zeros(64,np.int64)
pdp = np.ones(64,np.int64)
a = 16
b = 4
pdp[0*a+2*b+1] = 0
pdp[0*a+1*b+2] = 0
pdp[2*a+0*b+1] = 0
dic = {}
dic[0] = 'A'
dic[1] = 'C'
dic[2] = 'G'
dic[3] = 'T'
for i in range(N-3):
  for j in range(64):
    x = j//16
    y = (j-x*16)//4
    z = j%4
    m = 16*y+4*z
    if y==2 and z==0:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif y==0 and z==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif y==0 and z==1:
      for h in range(4):
        if h==2:
          continue
        dp[m+h] += pdp[j]
    elif x==0 and y==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif x==0 and z==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    else:
      for h in range(4):
        dp[m+h] += pdp[j]
  dp %= MOD
  pdp = np.copy(dp)
  dp = np.zeros(64,np.int64)
print(pdp.sum()%MOD)

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























for i in range(1, N+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):

                    if j==3 and k==2 and l==1:continue
                    elif j==2 and k==3 and l==1:continue
                    elif j==3 and k==1 and l==2:continue
                    elif j==3 and k==2 and m==1:continue
                    elif j==3 and l==2 and m==1:continue

                    d[i][j][k][l] += d[i-1][k][l][m]
                    d[i][j][k][l] %= mod

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

print(ans)

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

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

def ok(last4):
  for i in range(4):
    temp = list(last4)
    if i >= 1:
      temp[i-1], temp[i] = temp[i], temp[i-1]
    if ''.join(temp).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 = 10**9+7

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

def ok(last4):
  for i in range(4):
    temp = list(last4)
    if i >= 1:
      temp[i-1], temp[i] = temp[i], temp[i-1]
    if ''.join(temp).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 = 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 Length in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):

                if dp[Length][i][j][k] == 0:
                    continue

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

                    dp[Length + 1][j][k][d] += dp[Length][i][j][k]
                    dp[Length + 1][j][k][d] %= mod

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

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    D={
        "A":0, "G":1, "C":2, "T":3
    }

    DP=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N)] 
    DP[1][3] = [[1]*4 for _ in range(4)] 
    for i in range(2,N):
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    for s in range(4):
                        if s==0: 
                            pass
                        elif s==1: 
                            if (b,c)==(D["A"],D["C"]):
                                continue
                        elif s==2: 
                            if (b,c) in ((D["A"],D["G"]), (D["G"],D["A"])) or (a,c) == (D["A"], D["G"]) or (a,b) == (D["A"], D["G"]) :
                                continue
                        else: 
                            pass
                        DP[i][b][c][s] += DP[i-1][a][b][c]
                        DP[i][b][c][s] %= mod

    ans = 0
    for a in DP[-1]:
        ans += sum([sum(i) for i in a])
    print(ans%mod)
    """
    AGC
    ACG
    GAC
    A?GC
    AG?C

    """
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product

N = int(input())

MOD = 10**9 + 7


dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]


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


for i in range(N-3):
    
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue 
                    if pp==0 and p==2 and n==1: continue 
                    if pp==1 and p==0 and n==2: continue 
                    if ppp==0 and p==1 and n==2: continue 
                    if ppp==0 and pp==1 and n==2: continue 
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD

ans = sum(sum(sum(a) for a in b) for b in dp[-1])
print(ans % MOD)

Solution (Python):
N = int(input())
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==0 and j==1 and k==2: continue 
            if i==0 and j==2 and k==1: continue 
            if i==1 and j==0 and k==2: continue 
            dp[0][i][j][k] = 1
MOD = 10**9+7
for i in range(N-3):
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue 
                    if pp==0 and p==2 and n==1: continue 
                    if pp==1 and p==0 and n==2: continue 
                    if ppp==0 and p==1 and n==2: continue 
                    if ppp==0 and pp==1 and n==2: continue 
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD
ans = sum(sum(sum(a) for a in b) for b in dp[-1])
print(ans%MOD)

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], t[i-1] = t[i-1], t[i]
        if "".join(t).count('AGC') >= 1:
            return False
    return True
def dfs(now, last3):
    if last3 in memo[now]:
        return memo[now][last3]
    if now == n:
        return 1
    ret = 0
    for i in 'AGCT':
        
        if ok(last3 + i):
            
            ret = (ret + dfs(now+1, last3[1:] + i)) % mod
    memo[now][last3] = ret
    return ret
print(dfs(0,'TTT'))

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

def main():
    N = int(input())
    MOD = 10**9+7
    A,T,G,C = 0,1,2,3
    dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if i==A and j==G and k==C:
                    continue
                if i==A and j==C and k==G:
                    continue
                if i==G and j==A and k==C:
                    continue
                dp[3][i][j][k] = 1

    if N == 3:
        print("61")
    else:
        for n in range(4,N+1):
            for i in range(4):
                for j in range(4):
                    for k in range(4):
                        for l in range(4):
                            if i==A and j==G and k==C:
                                continue
                            if i==A and j==C and k==G:
                                continue
                            if i==G and j==A and k==C:
                                continue
                            if l==A and i==G and k==C:
                                continue
                            if l==A and j==G and k==C:
                                continue
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= MOD
        ans = 0                    
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    ans += dp[-1][i][j][k]
        print(ans%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
import itertools

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

base = ['A', 'C', 'G', 'T']
base3 = list(itertools.product(base, repeat=3))
index_dict = dict(zip(base3, range(64)))


def is_NG(b, s):
  for i in range(4):
    lb = list(b) + [s]
    if i >= 1:
      lb[i-1], lb[i] = lb[i], lb[i-1]
    if ''.join(lb).count('AGC') == 1:
      return True
  return False



dp = [[0]*64 for i in range(N)]
dp[2] = [1] * 64
for b in [('A', 'G', 'C'), ('A', 'C', 'G'), ('G', 'A', 'C')]:
  dp[2][index_dict[b]] = 0


for i in range(3, N):
  for j in range(64):
    b = base3[j]
    if is_NG(b, 'C'):
      for s in 'AGT':
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][j]
        dp[i][idx] %= MOD
    elif is_NG(b, 'G'):
      for s in 'ACT':
        idx = index_dict[('A', 'C', s)]
        dp[i][idx] += dp[i-1][j]
    else:
      for s in 'ACGT':
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][j]
        dp[i][idx] %= MOD
        

ans = sum(dp[-1]) % MOD
print(ans)

Solution (Python):
import itertools

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

base = ['A', 'C', 'G', 'T']
base3 = list(itertools.product(base, repeat=3))
index_dict = dict(zip(base3, range(64)))

s0 = set((('A', 'G', 'C'), ('A', 'C', 'G'), ('G', 'A', 'C')))
s1 = set((('A', 'A', 'G'), ('C', 'A', 'G'), ('G', 'A', 'G'), ('T', 'A', 'G')))
s2 = set((('A', 'A', 'G'), ('A', 'C', 'G'), ('A', 'G', 'G'), ('A', 'T', 'G')))
s3 = set((('A', 'G', 'A'), ('C', 'G', 'A'), ('G', 'G', 'A'), ('T', 'G', 'A')))
s4 = set((('A', 'G', 'A'), ('A', 'G', 'C'), ('A', 'G', 'G'), ('A', 'G', 'T')))
s5 = set((('A', 'A', 'C'), ('C', 'A', 'C'), ('G', 'A', 'C'), ('T', 'A', 'C')))


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

for j in range(64):
  if base3[j] in s0:
    continue
  
  dp[2][j] = 1


for i in range(3, N):
  for j in range(64):
    b = base3[j]
    idx_b = index_dict[b]
    if b in s1 or b in s2 or b in s3 or b in s4:
      for s in ['A', 'G', 'T']:
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][idx_b]
        dp[i][idx] %= MOD
    elif b in s5:
      for s in ['A', 'C', 'T']:
        idx = index_dict[('A', 'C', s)]
        dp[i][idx] += dp[i-1][idx_b]
    else:
      for s in ['A', 'C', 'G', 'T']:
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][index_dict[b]]
        dp[i][idx] %= MOD
        

ans = sum(dp[-1]) % MOD
print(ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
h = {
 'AG':1,
 'CG':1,
 'AGG':0,
 'aGG':1,
 'ATG':0,
 'aTG':1,
 'GA':1,
 'gA':3,
 'AC':1,
 'aC':3,
 'AT':1,
 'AGT':0,
 'aGT':1,
 'agT':2
}
for i in range(2,n):
    g = {}
    g['AG'] = h['GA']+h['gA']
    g['CG'] = h['aC']
    g['AGG'] = h['AG']
    g['aGG'] = h['CG']+h['AGG']+h['aTG']+h['aGG']+h['ATG']
    g['ATG'] = h['AT']
    g['aTG'] = h['AGT']+h['aGT']+h['agT']
    g['GA'] = h['AG']+h['CG']+h['AGG']+h['aTG']+h['aGG']+h['ATG']
    g['gA'] = h['GA']+h['gA']+h['AC']+h['aC']+h['AT']+h['AGT']+ \
             h['aGT']+h['agT']
    g['AC'] = h['gA']
    g['aC'] = h['AC']+h['aC']+h['AT']+ \
             h['aGT']+h['agT'] + \
             h['CG']+h['aTG']+h['aGG']
    g['AT'] = h['GA']+h['gA']
    g['AGT'] = h['AG']
    g['aGT'] = h['CG']+h['AGG']+h['aTG']+h['aGG']+h['ATG']
    g['agT'] = h['AC']+h['aC']+h['AT']+h['AGT']+ \
             h['aGT']+h['agT']
    h = g
sm = 0
for k in h:
    sm = (sm+h[k])%R
print(sm)

Solution (Python):

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

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

dp = [ [[[0 for c3 in range(4)]  for c2 in range(4)]  for c1 in range(4)] for n in range(N+1)]

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

for n in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for new in range(4):
          if c2 == A and c1 == G and new == C: continue
          if c2 == A and c1 == C and new == G: continue
          if c2 == G and c1 == A and new == C: continue
          if c3 == A and c1 == G and new == C: continue
          if c3 == A and c2 == G and new == C: continue

          dp[n+1][c2][c1][new] += dp[n][c3][c2][c1]      

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

print(ans % mod)

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


n = int(input())

def satisfy(s):
    for i in range(4):
        S = list(s)
        if i >= 1:
            S[i - 1], S[i] = S[i], S[i - 1]
        if "AGC" in "".join(S):
            return False
    return True

def dfs(depth, last4):
    if depth == n:
        if satisfy(last4):
            return 1
        else:
            return 0
    if last4 in MEMO[depth]:
        return MEMO[depth][last4]
    if satisfy(last4):
        ret = 0
        for c in "ACGT":
            ret += dfs(depth + 1, last4[1:] + c)
            ret %= mod
        MEMO[depth][last4] = ret
        return ret
    else:
        return 0

MEMO = [{} for _ in range(n + 1)]
print(dfs(0, "TTTT"))

Solution (Python):



























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


def f(i, s):
    if (i, s) in memo:
        return memo[(i, s)]
    if i == n:
        return 1
    ret = 0
    for c in "AGCT":
        flag = False
        for j in range(4):
            t = list(s + c)
            if j >= 1:
                t[j], t[j - 1] = t[j - 1], t[j]
            if "AGC" in "".join(t):
                flag = True
        if not flag:
            ret += f(i + 1, s[1:] + c)
            ret %= 10 ** 9 + 7
    memo[(i, s)] = ret
    return ret


print(f(0, "TTT"))

Solution (Python):
n=int(input())
alph=["A","C","G","T"]
a=[alph[i]+alph[j]+alph[k] for i in range(4) for j in range(4) for k in range(4)]

d1={l:0 for l in a}
for i in d1:
    if i!="AGC" and i!="ACG" and i!="GAC":
        d1[i]=1
d2={l:0 for l in a}
for i in range(n-3):
    for j in d1:
        next=[j+alph[k] for k in range(4)]
        for k in range(4):
            l=next[k]
            if l[1:]=="GAC" or l[1:]=="ACG" or l[1:]=="AGC":
                
                pass
            elif l[0]=="A" and l[3]=="C" and (l[1]=="G" or l[2]=="G"):
                
                pass
            else:
                d2[l[1:]]+=d1[j]
    for j in d1:
        d1[j]=d2[j]
        d2[j]=0
print(sum(d1.values())%(1000000007))

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











from collections import deque
stack=deque([""])
buf=[]
while stack:
  s=stack.popleft()
  if len(s)==3:
    buf.append(s)
    continue
  for c in ("ACGT"):
    stack.append(s+c)


dp={}
for b in buf:
  dp[b]=[0 for i in range(N+1)]
  if b not in ("AGC","ACG","GAC"):
    dp[b][3]=1


NG={
  "ACG":"C",
  "AGG":"C",
  "ATG":"C",
  "AGA":"C",
  "AGT":"C"
}
DIV=10**9+7

for i in range(3,N):
  for item in dp.items():
    key=item[0]
    value=item[1]
    ngnex=""
    if key in NG:
      ngnex=NG[key]
    las2=key[1:]
    for c in ("ACGT"):
      if las2+c in ("AGC","ACG","GAC"):
        continue
      if c!=ngnex:
        dp[las2+c][i+1]+=dp[key][i]
        dp[las2+c][i+1]%=DIV

ans=0
for v in dp.values():
  ans+=v[-1]
print(ans%DIV)

Solution (Python):



from collections import defaultdict

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

dp = [defaultdict(int) for i in range(n+1)]
dp[0]['']=1

def check(s):
    if 'AGC' in s:
        return False
    for i in range(len(s)-1):
        l = list(s)
        l[i],l[i+1]=l[i+1],l[i]
        t = ''.join(l)
        if 'AGC' in t:
            return False
    return True

for i in range(n):
    for k,v in dp[i].items():
        for x in 'AGCT':
            y = k[-3:]+x
            if check(y):
                dp[i+1][y]+=v

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

Solution (Python):


def base_10to(n,m):
    if (n//m):
        return base_10to(n//m, m) + str(n%m)
    return str(n%m)


def base_10from(n,m):
    a = 0
    for i in range(len(n)):
        a*=m
        a+=int(n[i])
    return a


n = int(input())

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


for i in range(64):
    a = base_10to(i,4)
    a= a.zfill(3)
    if a=='012' or a=='102' or a=='021':
        dp[2][i]=0
    else:
        dp[2][i]=1

for i in range(2,n-1):
    for j in range(64):
        a = base_10to(j, 4)
        a = a.zfill(3)
        if a[1:]=='02':
            for k in [0,2,3]:
                dp[i+1][base_10from(a[1:]+str(k),4)] += dp[i][j]
        elif a[1:]=='10' or a[1:]=='01' or a[:2]=='01' or (a[0]=='0' and a[2]=='1'):
            for k in [0,1,3]:
                dp[i+1][base_10from(a[1:]+str(k),4)] += dp[i][j]
        else:
            for k in [0,1,2,3]:
                dp[i+1][base_10from(a[1:]+str(k),4)] += dp[i][j]

print(sum(dp[-1])%(10**9+7))

Solution (Python):
from functools import lru_cache


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


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


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


print(dfs(0, 'TTT'))

Solution (Python):
MOD=10**9+7
N=int(input())
if N==3:
  print(61)
  exit()
  
dp=[[[[1]*4 for c in range(4)] for b in range(4)] for a in range(4)]
        
for x in range(4):
  dp[0][x][2][1]=0
  dp[0][2][x][1]=0
  dp[0][1][2][x]=0
  dp[2][0][1][x]=0
  dp[0][2][1][x]=0
  dp[x][0][1][2]=0
  dp[x][2][0][1]=0
  dp[x][0][2][1]=0
  
def f():
  tmp=[[[[0]*4 for c in range(4)] for b in range(4)] for a in range(4)]
  for a in range(4):
    for b in range(4):
      for c in range(4):
        t=sum([dp[x][a][b][c] for x in range(4)])
        t%=MOD
        for d in range(4):
          tmp[a][b][c][d]=t
          
  for x in range(4):
    tmp[0][x][2][1]=0
    tmp[0][2][x][1]=0
    tmp[x][0][1][2]=0
    tmp[x][2][0][1]=0
    tmp[x][0][2][1]=0
    
  return tmp
  
for k in range(4, N):
  dp=f()
  
print(sum([sum([dp[a][b][c][d] for a in range(4) for b in range(4) for c in range(4)])%MOD for d in range(4)])%MOD)