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):
N = int(input())
M = 10**9 + 7

dp = [
    [[[1 if i==0 else 0 for i in range(N-2)] for j in range(4)] for k in range(4)] for l in range(4)
]

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

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]

total %= M
print(total)

Solution (Python):
ngs4 = ["ATGC", "AGTC","ACGC", "AGCC","AGGC", "AGGC"]
ngs3 = ["AGC", "ACG", "GAC"]
def is_valid(b):
    s = b[-4:]
    if s in ngs4:
        return False
    s = s[-3:]
    if s in ngs3:
        return False
    return True

N = int(input())
memo = [{} for i in range(N+1)]
acgt = ["A", "C", "G", "T"]
MOD = 10**9 + 7
def dp(i, last3):
    if last3 in memo[i]:
        return memo[i][last3]

    if i == N:
        return 1
    
    ret = 0
    for c in acgt:
        candi = last3 + c
        if is_valid(candi):
            ret = (ret + dp(i+1, last3[1:] +c)) % MOD
    memo[i][last3] = ret
    return ret

def sub():
    print(dp(0, "TTT"))

sub()

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from collections import defaultdict


def find_ans(dp, mod):
    nex = defaultdict(int)
    for key, val in dp.items():
        for c in ["A", "G", "C", "T"]:
            if (key[1:] == "AG" and c == "C")\
                or (key[1:] == "AC" and c == "G")\
                or (key[1:] == "GA" and c == "C")\
                or (key[:1] == "A" and key[2:] == "G" and c == "C")\
                or (key[:1] == "A" and key[1:2] == "G" and c == "C"):
                continue
            else:
                nex[key[1:] + c] += val
                nex[key[1:] + c] %= mod

    return nex

n = ni()
dp = defaultdict(int)
mod = 10**9 + 7

dp["TTT"] = 1

for _ in range(n):
    dp = find_ans(dp, mod)

ans = 0
for key, val in dp.items():
    ans += val
    ans %= mod

print(ans)

Solution (Python):
import numpy as np
N = int(input())
mod = 10**9 + 7

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

for length in range(1, N+1):



    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if logs[length-1, c1, c2, c3] == 0:
                    continue
                for n in range(4):
                    if n == 2 and c1 == 1 and c2 == 0:  continue
                    if n == 1 and c1 == 2 and c2 == 0:  continue
                    if n == 2 and c1 == 0 and c2 == 1:  continue
                    if n == 2 and c2 == 1 and c3 == 0:  continue
                    if n == 2 and c1 == 1 and c3 == 0:  continue
                    
                    logs[length, n, c1, c2] += logs[length - 1, c1, c2, c3]
                    logs[length, n, c1, c2] %= mod

M = int(np.sum(logs[N])) % mod
print(M)

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

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

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

def dfs(cur, S):
    if S in memo[cur]:
        return memo[cur][S]
    if cur == N:
        return 1

    count = 0
    for c in "ACGT":
        if valid(S + c):
            count = (count + dfs(cur + 1, S[1:] + c)) % mod
    memo[cur][S] = count
    return count

print(dfs(0, "TTT"))

Solution (Python):


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

dp = [[[[0,0,0,0] for k in range(4)] for l in range(4)] for m in range(N+1)]


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

for p in range(1,N+1):
    for k in range(4):
        for l in range(4):
            for m in range(4):
                for n in range(4):
                    
                    if (l==0 and m==2 and n==1) or (l==0 and m==1 and n==2) or (l==2 and m==0 and n==1) or (k==0 and m==2 and n==1) or (k==0 and l==2 and n==1):
                        pass
                    else:
                        dp[p][l][m][n] += dp[p-1][k][l][m]
                        dp[p][l][m][n] %= MOD

ans = 0
for k in range(4):
    for l in range(4):
        for m in range(4):
            ans += dp[N][k][l][m]
print(ans%MOD)

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

Solution (Python):
import numpy as np
    
N = int(input())
MOD=7+10**9

def pattern_calc(num,i,j,k,l):
    
    
    
    if calc_result[0,i,j,k,l]==0:
        
        sub_ans = 0
        
    else:
        if calc_flag[num,i,j,k,l] == True:
            sub_ans = calc_result[num,i,j,k,l]
            
        else:
            

            for atot in range(4): 
                calc_result[num,i,j,k,l] = calc_result[num,i,j,k,l] + pattern_calc(num-1,atot,i,j,k)%MOD 
                
                
                
            calc_flag[num,i,j,k,l] = True
            sub_ans = calc_result[num,i,j,k,l]
            
    return sub_ans            

if N==3:
    print("61")
else:   
    calc_result = np.zeros((N-3,4,4,4,4),dtype=np.uint64) 
    
    
    


    
    
    
    

    
    
    

    calc_flag = np.zeros((N-3,4,4,4,4), dtype=np.bool) 
    

    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    calc_result[0,i,j,k,l] = 1
                    calc_flag[0,i,j,k,l] = True

    calc_result[0,0,0,1,2]=0
    calc_result[0,0,0,2,1]=0
    calc_result[0,0,1,1,2]=0
    calc_result[0,0,1,3,2]=0
    calc_result[0,0,1,2,0]=0
    calc_result[0,0,1,2,1]=0
    calc_result[0,0,1,2,2]=0
    calc_result[0,0,1,2,3]=0
    calc_result[0,0,1,0,2]=0
    calc_result[0,0,2,1,0]=0
    calc_result[0,0,2,1,1]=0
    calc_result[0,0,2,1,2]=0
    calc_result[0,0,2,1,3]=0
    calc_result[0,0,3,1,2]=0
    calc_result[0,1,0,1,2]=0
    calc_result[0,1,0,2,0]=0
    calc_result[0,1,0,2,1]=0
    calc_result[0,1,0,2,2]=0
    calc_result[0,1,0,2,3]=0
    calc_result[0,1,1,0,2]=0
    calc_result[0,2,0,2,1]=0
    calc_result[0,2,1,0,2]=0
    calc_result[0,2,0,1,2]=0
    calc_result[0,3,0,2,1]=0
    calc_result[0,3,1,0,2]=0
    calc_result[0,3,0,1,2]=0

    N = N - 4
    ans = 0
    
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    
                    ans = (ans + pattern_calc(N,i,j,k,l))

    print(int(ans%MOD))

Solution (Python):



inf = 10**9+7
def ng(key, c=None):
    if c is None:
        return key == "agc" or key == "gac" or key == "acg"
    if key[0] == 'a' and key[1] == 'g' and c == 'c':
        "ag.c"
        return True
    if key[0] == 'a' and key[2] == 'g' and c == 'c':
        "a.gc"
        return True
    if key[1] == 'a' and key[2] == 'g' and c == 'c':
        "agc"
        return True
    if key[1] == 'g' and key[2] == 'a' and c == 'c':
        "gac"
        return True
    if key[1] == 'a' and key[2] == 'c' and c == 'g':
        "acg"
        return True
    return False


def init():
    ret = {}
    for c1 in list('acgt'):
        for c2 in list('acgt'):
            for c3 in list('acgt'):
                key = c1+c2+c3
                if ng(key):
                    continue
                ret[key] = 1
    return ret


def next(dp):
    ndp = {}
    for key in dp:
        for c in list('atcg'):
            if ng(key, c):
                continue
            nkey = key[1:] + c
            ndp.setdefault(nkey, 0)
            ndp[nkey] += dp[key] % inf
    return ndp


def main():
    N = int(input())
    dp = init()
    for i in range(N-3):
        dp = next(dp)
    print(sum(dp.values()) % inf)


if __name__ == '__main__':
    main()

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


for i in range(4):
    for j in range(4):
        for k in range(4):
            if k == A and j == G and i == C: continue
            if k == A and j == C and i == G: continue
            if k == G and j == A and i == C: continue
            dp[3][k][j][i] = 1

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

Solution (Python):
import itertools

s = 'ACGT'
s = [a+b+c for a,b,c in itertools.product(s,s,s)]
n = {s_:1 for s_ in s}
n['AGC'] = 0
n['GAC'] = 0
n['ACG'] = 0

N = int(input())
if N == 3:
    count = n
else:
    for i in range(N-3):
        count = {s_:0 for s_ in s}
        for _ in s:
            for a in 'ACGT':
                x = _+a
                if 'GAC' in x or 'ACG' in x or ('A' == x[0] and 'GC' == x[2:]) or ('AG' == x[:2] and 'C' == x[3]):
                    pass
                else:
                    count[x[1:]] += n[_]
        count['AGC'] = 0
        count['GAC'] = 0
        count['ACG'] = 0
        n = count
print(sum([value for value in count.values()])%(10**9+7))

Solution (Python):
N=int(input())
dp = [{} for _ in range(101)]

str = "ACGT"
mod = 10**9+7
for i in range(4):
  for j in range(4):
    for k in range(4):
      last3 = str[i] + str[j] + str[k]
      if last3 == "AGC" or last3 == "ACG" or last3 == "GAC":
        dp[3][last3] = 0
      else:
        dp[3][last3] = 1

for n in range(4,101):
  for last3 in dp[n-1]:
    for c in str:
      new_last3 = last3[1:]+c
      if new_last3 == "AGC" or new_last3 == "ACG" or new_last3 == "GAC":
        dp[n][new_last3] = 0
      else:
        if last3 == "AGC" or last3 == "ACG" or last3 == "GAC":
          if new_last3 not in dp[n]:
            dp[n][new_last3] = 0
        elif last3 == "AAG" or last3 == "AGA" or last3 == "AGG" or last3 == "AGT" or last3 == "ATG" or last3 == "CAG" or last3 == "CGA" or last3 == "GAG" or last3 == "GGA" or last3 == "TAG" or last3 == "TGA":
          if new_last3[2] != "C":
            if new_last3 not in dp[n]:
              dp[n][new_last3] = dp[n-1][last3]
            else:
              dp[n][new_last3] += dp[n-1][last3]
        elif last3 == "AAC" or last3 == "CAC" or last3 == "TAC":
          if new_last3[2] != "G":
            if new_last3 not in dp[n]:
              dp[n][new_last3] = dp[n-1][last3]
            else:
              dp[n][new_last3] += dp[n-1][last3]
        else:
          if new_last3 not in dp[n]:
            dp[n][new_last3] = dp[n-1][last3]
          else:
            dp[n][new_last3] += dp[n-1][last3]

sum = 0
for s in dp[N]:
  sum += dp[N][s]
  sum %= mod

print(sum)

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

def ok(last4):
  for i in range(4):
    t = list(last4)
    if i >= 1:
      t[i-1], t[i] = t[i], t[i-1]
    if ''.join(t).count('AGC') >= 1:
      return False
  return True
def dfs(cur, last3):
  if last3 in memo[cur]:
    return memo[cur][last3]
  if cur == N:
    return 1
  ret = 0
  for c in 'ACGT':
    if ok(last3 + c):
      ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
  return ret
print(dfs(0, 'TTT'))

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

import numpy as np

a = np.zeros([4,4,4],np.int64)
a+=1

a[0,2,3]=0
a[2,0,3]=0
a[0,3,2]=0

for i in range(N-3):
  b = np.zeros([4,4,4],np.int64)
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if ( j==0 and k==2 ) or ( j==2 and k==0 ) or ( i==0 and k==2 ) or (i==0 and j==2 ):
          b[j,k,0] += a[i,j,k]
          b[j,k,1] += a[i,j,k]
          b[j,k,2] += a[i,j,k]
        elif ( j==0 and k==3 ):
          b[j,k,0] += a[i,j,k]
          b[j,k,1] += a[i,j,k]
          b[j,k,3] += a[i,j,k]
        else:
          b[j,k,0] += a[i,j,k]
          b[j,k,1] += a[i,j,k]
          b[j,k,2] += a[i,j,k]
          b[j,k,3] += a[i,j,k]
  a=b%(1000000007)
  
        

print ( np.sum(a)%1000000007 )

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

dp=[[[[0for i in range(4)]for i in range(4)]for i in range(4)]for i in range(n)]
s=[0 for i in range(n)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[0][i][j][k]=1
s[0]=4
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[1][i][j][k]=1
s[1]=16
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[2][i][j][k]=1
dp[2][0][2][1]=0
dp[2][0][1][2]=0
dp[2][2][0][1]=0
s[2]=61
for a in range(3,n):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        dp[a][i][j][k]=sum(dp[a-1][j][k])
  
  
  
  dp[a][0][1][2]-=dp[a-1][1][2][0]+dp[a-1][1][2][1]+dp[a-1][1][2][2]+dp[a-1][1][2][3]
  
  dp[a][0][2][1]-=dp[a-1][2][1][0]+dp[a-1][2][1][1]+dp[a-1][2][1][2]+dp[a-1][2][1][3]
  
  dp[a][0][2][2]-=dp[a-1][2][2][1]
  
  dp[a][0][2][3]-=dp[a-1][2][3][1]
  
  dp[a][0][3][2]-=dp[a-1][3][2][1]
  
  dp[a][2][0][1]-=dp[a-1][0][1][0]+dp[a-1][0][1][1]+dp[a-1][0][1][3]
  for i in range(4):
    for j in range(4):
      for k in range(4):
        dp[a][i][j][k]%=mod
        s[a]+=dp[a][i][j][k]
        s[a]%=mod
print(s[n-1])

Solution (Python):
from collections import defaultdict

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

nglist = [
    "?AGC", "AGC?",
    "A?GC", "AG?C",
    "GAC?", "?GAC",
    "ACG?", "?ACG"
]
ng = {}
for t in "AGCT":
    for n in nglist:
        ng[n.replace('?', t)] = 1

dp = {"TTT": 1}

for i in range(N):
    ans = 0
    _dp = defaultdict(int)
    for k, v in dp.items():
        for t in "AGCT":
            s = k+t
            if s not in ng:
                _dp[s[1:]] += v
                ans = (ans+v) % MOD
    dp = _dp
    if i == (N-1):
        print(ans)

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

dp = [
    [[[1 if i==0 else 0 for i in range(N-2)] for j in range(4)] for k in range(4)] for l in range(4)
]


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

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    
                    
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]
            total %= M
print(total)

Solution (Python):





import sys

n = int(input())

if n <= 2:
  print(4**n)
  sys.exit()

end = {}
for i in ['A','G','C','T']:
  for j in ['A','G','C','T']:
    for k in ['A','G','C','T']:
      if i+j+k in ['AGC','GAC','ACG']:
        end[i+j+k] = 0
      else:
        end[i+j+k] = 1
        
num = 61
if n == 3:
  print(num)
  sys.exit()


notend = ['AAG','GAG','CAG','TAG']
notpattarn = ['AAGC','GAGC','CAGC','TAGC']

notend += ['AGA','GGA','CGA','TGA']
notpattarn += ['AGAC','GGAC','CGAC','TGAC']

notend += ['AAC','CAC','TAC']
notpattarn += ['AACG','CACG','TACG']

notend += ['AGG','AGT']
notpattarn += ['AGGC','AGTC']

notend += ['ATG']
notpattarn += ['ATGC']

for i in range(4,n+1):
  
  num *= 4
  for j in end.keys():
    if j in notend:
      num -= end[j]
      
  end_tmp = {}
  for j in end.keys():
    end_tmp[j] = 0
  
  for j in end.keys():
    for k in ['A','G','C','T']:
      if k+j in notpattarn:
        pass
      else:
        end_tmp[j] += end[k+j[0:2]]
        
  end = end_tmp
  

print(num%(10**9+7))

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

E = "ACGT"

from collections import defaultdict

ngp = [
    "AGC?", "GAC?", "ACG?",
    "?AGC", "?GAC", "?ACG",
    "A?GC", "AG?C"
]

ng = set(["AGC", "GAC", "ACG"])

for x in ngp:
    for c in E:
        ng.add(x.replace("?", c))

rs = {"": 1}

for i in range(N):
    nrs = defaultdict(int)
    for k, v in rs.items():
        for e in E:
            nk = (k + e)[-4:]
            if not nk in ng:
                nrs[nk[-3:]] += v
    rs = nrs

result = sum(nrs.values()) % M

print(result)

Solution (Python):


from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * sy) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x





counts_3 = {
  "CAA": 1,
  "CTT": 1,
  "TTT": 1,
  "GGC": 1,
  "CGT": 1,
  "GTG": 1,
  "ACC": 1,
  "GCA": 1,
  "TTC": 1,
  "TCA": 1,
  "GGT": 1,
  "GTT": 1,
  "CAG": 1,
  "AAT": 1,
  "TAA": 1,
  "TAG": 1,
  "CCA": 1,
  "GCT": 1,
  "CTA": 1,
  "TCT": 1,
  "TTG": 1,
  "ATT": 1,
  "CAT": 1,
  "GAA": 1,
  "ATA": 1,
  "CCC": 1,
  "GCG": 1,
  "TTA": 1,
  "ACA": 1,
  "AGT": 1,
  "AGG": 1,
  "AGA": 1,
  "CCG": 1,
  "ATG": 1,
  "GAG": 1,
  "AAA": 1,
  "TCC": 1,
  "AAG": 1,
  "GCC": 1,
  "ACT": 1,
  "TGG": 1,
  "CTC": 1,
  "TCG": 1,
  "TGT": 1,
  "CGC": 1,
  "TAC": 1,
  "TAT": 1,
  "CGG": 1,
  "GGG": 1,
  "TGA": 1,
  "CCT": 1,
  "AAC": 1,
  "CGA": 1,
  "GTC": 1,
  "ATC": 1,
  "GGA": 1,
  "CAC": 1,
  "CTG": 1,
  "GAT": 1,
  "TGC": 1,
  "GTA": 1
}


mod = 10**9 + 7


def main():
    n = intin()

    all_ok = []
    not_c = []
    not_g = []
    for suffix in counts_3:
        if suffix == 'ATG' or suffix == 'AGG' or suffix == 'AAG':
            not_c.append(suffix)
        elif suffix == 'AGT':
            not_c.append(suffix)
        elif 'T' in suffix[1:]:
            all_ok.append(suffix)
        elif suffix[1:] == 'AA' or suffix[1:] == 'GG' or suffix[1:] == 'CC':
            all_ok.append(suffix)
        elif suffix[1:] == 'AG' or suffix[1:] == 'GA':
            not_c.append(suffix)
        elif suffix[1:] == 'AC':
            not_g.append(suffix)
        else:
            all_ok.append(suffix)

    suffix_counts = {3: counts_3}

    for i in range(4, 101):
        prev_count = suffix_counts[i-1]
        suffix_count = {}
        for suffix, count in prev_count.items():
            if suffix in all_ok:
                charlist = ['A', 'C', 'G', 'T']
            if suffix in not_c:
                charlist = ['A', 'G', 'T']
            if suffix in not_g:
                charlist = ['A', 'C', 'T']
            for c in charlist:
                new_suffix = suffix[1:] + c
                suffix_count.setdefault(new_suffix, 0)
                suffix_count[new_suffix] = modadd(suffix_count[new_suffix], count)
        suffix_counts[i] = suffix_count

    suffix_count = suffix_counts[n]

    ans = 0
    for i, count in suffix_count.items():
        ans = modadd(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return map(int, input_tuple)


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x




counts_3 = {
  "CAA": 1,
  "CTT": 1,
  "TTT": 1,
  "GGC": 1,
  "CGT": 1,
  "GTG": 1,
  "ACC": 1,
  "GCA": 1,
  "TTC": 1,
  "TCA": 1,
  "GGT": 1,
  "GTT": 1,
  "CAG": 1,
  "AAT": 1,
  "TAA": 1,
  "TAG": 1,
  "CCA": 1,
  "GCT": 1,
  "CTA": 1,
  "TCT": 1,
  "TTG": 1,
  "ATT": 1,
  "CAT": 1,
  "GAA": 1,
  "ATA": 1,
  "CCC": 1,
  "GCG": 1,
  "TTA": 1,
  "ACA": 1,
  "AGT": 1,
  "AGG": 1,
  "AGA": 1,
  "CCG": 1,
  "ATG": 1,
  "GAG": 1,
  "AAA": 1,
  "TCC": 1,
  "AAG": 1,
  "GCC": 1,
  "ACT": 1,
  "TGG": 1,
  "CTC": 1,
  "TCG": 1,
  "TGT": 1,
  "CGC": 1,
  "TAC": 1,
  "TAT": 1,
  "CGG": 1,
  "GGG": 1,
  "TGA": 1,
  "CCT": 1,
  "AAC": 1,
  "CGA": 1,
  "GTC": 1,
  "ATC": 1,
  "GGA": 1,
  "CAC": 1,
  "CTG": 1,
  "GAT": 1,
  "TGC": 1,
  "GTA": 1
}


def main():
    n = intin()
    mod = 10**9 + 7

    all_ok = []
    not_c = []
    not_g = []
    for suffix in counts_3:
        if suffix == 'ATG' or suffix == 'AGG' or suffix == 'AAG':
            not_c.append(suffix)
        elif suffix == 'AGT':
            not_c.append(suffix)
        elif 'T' in suffix[1:]:
            
            all_ok.append(suffix)
        elif suffix[1:] == 'AA' or suffix[1:] == 'GG' or suffix[1:] == 'CC':
            
            all_ok.append(suffix)
        elif suffix[1:] == 'AG' or suffix[1:] == 'GA':
            not_c.append(suffix)
        elif suffix[1:] == 'AC':
            not_g.append(suffix)
        else:
            
            all_ok.append(suffix)

    suffix_counts = {3: counts_3}

    for i in range(4, 101):
        prev_count = suffix_counts[i-1]
        suffix_count = {}
        for suffix, count in prev_count.items():
            if suffix in all_ok:
                charlist = ['A', 'C', 'G', 'T']
            if suffix in not_c:
                charlist = ['A', 'G', 'T']
            if suffix in not_g:
                charlist = ['A', 'C', 'T']
            for c in charlist:
                new_suffix = suffix[1:] + c
                suffix_count.setdefault(new_suffix, 0)
                suffix_count[new_suffix] += count
                suffix_count[new_suffix] %= mod
        suffix_counts[i] = suffix_count

    suffix_count = suffix_counts[n]

    

    ans = 0
    for i, count in suffix_count.items():
        ans += count
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import itertools

MOD = 1000000007  


def ok(s: str):
    ng = 'AGC'
    c = s.count(ng)
    for i in range(1, 4):
        s2 = s[:i-1] + s[i] + s[i-1] + s[i+1:]
        c += s2.count(ng)
    return c == 0
    

def solve(N: int):
    K = [''.join(t) for t in itertools.product('ACGT', repeat=3)]
    C = [{k: 0 for k in K} for i in range(N+2)] 
    C[0]['TTT'] = 1
    
    for i in range(1, N+1):
        for last3 in C[i-1].keys():
            for c in 'ACGT':
                if ok(last3 + c):
                    C[i][last3[1:] + c] = (C[i][last3[1:] + c] + C[i-1][last3]) % MOD
    print(sum([C[N][k] for k in K]) % MOD)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import chain
from functools import reduce

N = int(input())
atgc = "ATGC"
labels = []
for c1 in atgc:
    for c2 in atgc:
        for c3 in atgc:
            labels.append(c1+c2+c3)

labels[0], labels[11] = labels[11], labels[0]
labels[1], labels[14] = labels[14], labels[1]
labels[2], labels[35] = labels[35], labels[2]

lb2i = {lb:i for i, lb in enumerate(labels)}
mat = [[0]*64 for i in range(64)]

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

for i, lb1 in enumerate(labels):
    tmp = [(lb1+c) for c in atgc]
    tmp = [s for s in tmp if not any(["AGC" in swap(s, i, i+1) for i in range(3)])]
    for lb2 in tmp:
        mat[i][lb2i[lb2[1:]]] += 1

prev = [1]*64
curr = [0]*64

mod = 1000000007

for _ in range(N-3):
    prev[0:3] = [0,0,0]
    for j in range(64):
        curr[j] = 0
    for lbi1 in range(64):
        for lbi2 in range(64):
            curr[lbi2] += mat[lbi1][lbi2]*prev[lbi1]
            curr[lbi2] %= mod
    curr, prev = prev, curr

prev[0:3] = [0,0,0]
print(reduce(lambda acc, x: (acc+x)%mod, prev, 0))

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

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

mod = 10**9+7

for length in range(N):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                if dp[length][c3][c2][c1] == 0:
                    continue

                for a in range(4):
                    if c2 == 0 and c1 == 1 and a == 2:
                        continue
                    if c2 == 1 and c1 == 0 and a == 2:
                        continue
                    if c2 == 0 and c1 == 2 and a == 1:
                        continue
                    if c3 == 0 and c1 == 1 and a == 2:
                        continue
                    if c3 == 0 and c2 == 1 and a == 2:
                        continue

                    dp[length+1][c2][c1][a] += dp[length][c3][c2][c1]
                    dp[length+1][c2][c1][a] %= mod

ans = 0
for c3 in range(4):
    for c2 in range(4):
        for c1 in range(4):
            ans += dp[N][c3][c2][c1]
            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):
        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):
N, mod = int(input()), 10**9+7
memo = [{} for i in range(N+1)]


def ok(last4):
  for i in range(4):
    l = list(last4)
    if l[1]=='A' and l[2]=='G' and l[3]=='C':
      return False
    if l[1]=='A' and l[2]=='C' and l[3]=='G':
      return False
    if l[1]=='G' and l[2]=='A' and l[3]=='C':
      return False
    if l[0]=='A' and l[2]=='G' and l[3]=='C':
      return False
    if l[0]=='A' and l[1]=='G' and l[3]=='C':
      return False
    else:return True
    
def func(num, last3):
  if last3 in memo[num]:
    return memo[num][last3]
  if num == N:
    return 1
  ans = 0
  for i in 'ACGT':
    if ok(last3 + i):
      ans = (ans + func(num+1, last3[1:] + i)) % mod
  memo[num][last3] = ans
  return ans
    
      
print(func(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 i in range(1,n+1):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for a in range(4):
                    if c2 == 0 and c1 == 1 and a == 2:
                        continue
                    if c2 == 0 and c1 == 2 and a == 1:
                        continue
                    if c2 == 1 and c1 == 0 and a == 2:
                        continue
                    if c3 == 0 and c1 == 1 and a == 2:
                        continue
                    if c3 == 0 and c2 == 1 and a == 2:
                        continue
                    dp[i][c2][c1][a] += dp[i-1][c3][c2][c1]
                    dp[i][c2][c1][a] %= MOD
ans = 0
for c1 in range(4):
    for c2 in range(4):
        ans += sum(dp[i][c1][c2])
        ans %= MOD
print(ans)

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(1,N+1):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for a in range(4):
                    if c2 == 0 and c1 == 1 and a == 2:
                        continue
                    if c2 == 0 and c1 == 2 and a == 1:
                        continue
                    if c2 == 1 and c1 == 0 and a == 2:
                        continue
                    if c3 == 0 and c1 == 1 and a == 2:
                        continue
                    if c3 == 0 and c2 == 1 and a == 2:
                        continue
                    dp[i][c2][c1][a] += dp[i-1][c3][c2][c1]
                    dp[i][c2][c1][a] %= mod
ans = 0
for c1 in range(4):
    for c2 in range(4):
        ans += sum(dp[i][c1][c2])
        ans %= mod
print(ans)