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 pprint
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"
M = 10 ** 9 + 7

for j in range(n + 1):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        dp[j][c1 + c2 + c3] = 0

dp[0]["TTT"] = 1

for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[l + 1][c2 + c3 + p] = (dp[l + 1][c2 + c3 + p] + dp[l][c1 + c2 + c3]) % M
          

ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
      ans = ans % M
print(ans)

Solution (Python):
import pprint
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"
M = 10 ** 9 + 7

for j in range(n + 1):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        dp[j][c1 + c2 + c3] = 0

dp[0]["TTT"] = 1

for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[l + 1][c2 + c3 + p] += dp[l][c1 + c2 + c3]
          dp[l + 1][c2 + c3 + p] = dp[l + 1][c2 + c3 + p] % M

ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
      ans = ans % M
print(ans)

Solution (Python):
n=int(input())
dp={}
def f(i,last4):
    if i==n:
        return 1
    else:
        if (i,last4) in dp:
            return dp[(i,last4)]
        else:
            addA=f(i+1,last4[1:4]+'A')
            addT=f(i+1,last4[1:4]+'T')
            if not last4[2:4]=='AC':
                addG=f(i+1,last4[1:4]+'G')
            else:
                addG=0
            if not (last4[2:4]=='AG' or last4[2:4]=='GA' or last4[1:4]=='ATG' or last4[1:4]=='AGG' or last4[1:4]=='AGT'):
                addC=f(i+1,last4[1:4]+'C')
            else:
                addC=0
            answer=addA+addT+addG+addC
            dp[(i,last4)]=answer
            return answer
print(f(0,'SSSS')%(10**9+7))

Solution (Python):
n = int(input())
ans = [61, 230, 865, 3247, 12185, 45719, 171531, 643550, 2414454, 9058467, 33985227, 127504505, 478366600, 794717734, 733354121, 261943303, 776803305, 580025381, 51688048, 44657419, 737209731, 604119499, 159693437, 858533109, 639056669, 549054109, 996291083, 531294469, 23314687, 783022045, 855462856, 649970414, 68697295, 409213624, 604356692, 88638656, 978442997, 534833116, 763737161, 785892908, 123883652, 639213333, 181836645, 998121103, 124885216, 501575626, 39816123, 113468411, 799008836, 775465589, 256852905, 664630886, 971550783, 751629411, 51018086, 702530485, 725438992, 696683714, 792638194, 221791721, 149602322, 414054379, 986519078, 981760191, 305799096, 515140586, 406959393, 975058685, 245601370, 324759692, 673385295, 191483611, 570246669, 427196161, 781042769, 569725155, 842176273, 25328739, 847501730, 206282374, 353770801, 323137024, 371653459, 940737264, 123820509, 915711339, 847205021, 252858375, 718889563, 866398347, 738390145, 133009077, 333099663, 170591295, 329869205, 616680192, 597534442, 388130742]
print(ans[n - 3])

Solution (Python):


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

    """
    AGCTをそれぞれ、
    0123と置き換えて考える
    
    条件は
    ・文字0~3のみで構成される
    ・012を含まない
    ・隣同士をswapしても012を含まない

    出ちゃダメなパターンを考えると、
    ・012
    ・102
    ・021
    ・0?12
    ・01?2

    条件を満たしている部分文字列Sに対して、
    ・S+0 をしたときは大丈夫
    ・S+1 をしたとき、最後が021になるとダメ
    ・S+2 をしたとき、最後が012, 102, 0?12, 01?2になるとダメ
    ・S+3 をしたときは大丈夫
    
    と考えると、部分文字列の最後の3文字を見ると条件を満たしているかを判定できる

    dp[i][c1][c2][c3] := 部分文字列の長さiのときで、部分文字列の最後の文字列がc1c2c3のときの、条件を満たす個数
    """

    dp = [[[[0 for _ in range(4)] for __ in range(4)] for ___ in range(4)] for ____ in range(N+1)]

    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                dp[0][c1][c2][c3] = 0
                dp[1][c1][c2][c3] = 0
                dp[2][c1][c2][c3] = 0
                dp[3][c1][c2][c3] = 1
    dp[3][0][2][1] = 0
    dp[3][0][1][2] = 0
    dp[3][1][0][2] = 0

    for i in range(3, N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    if dp[i][c1][c2][c3] == 0:
                        
                        dp[i+1][c1][c2][c3] = 0
                        continue

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

                        
                        dp[i+1][c2][c3][a] += dp[i][c1][c2][c3]
                        dp[i+1][c2][c3][a] %= MOD
    
    ans = 0
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                ans += dp[N][c1][c2][c3]
                ans %= MOD
    print(ans)


if __name__ == "__main__":
    solve()

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

b = {i+j+k:1 for i in "AGCT" for j in "AGCT" for k in "AGCT" if i+j+k not in ("AGC", "ACG", "GAC")}
t = {}

def isOk(last4):
    if last4[1:] in ("AGC", "ACG", "GAC"):
        return False
    if last4[0] == 'A' and "G" in (last4[1], last4[2]) and last4[3] == "C":
        return False
    return True

for _ in range(N-3):
    t = {}
    for w, j in b.items():
        for a in "AGCT":
            x = w + a
            if isOk(x):
                if x[1:] not in t:
                    t[x[1:]] = j
                else:
                    t[x[1:]] += j
    b = t

a = 0
for i, j in b.items():
    a += j
print(a % 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 'ATCG':
        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):
import numpy as np

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

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

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

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

Solution (Python):
N, 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):

"""
Created on Sat Feb 16 20:52:46 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect


def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')


ABT = zip(A, B, totAB)
result = 0

sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)


(x >> i) & 1


dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""

N = int(input())
dp = np.zeros((N+1, 4,4,4))
dp[0][3][3][3] = 1

mod = 10**9+7
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 now in range(4):
                    if now == 0 and i == 1 and j == 2:
                        continue
                    if now == 0 and i == 2 and j == 1:
                        continue
                    if now == 1 and i == 0 and j == 2:
                        continue
                    if now == 0 and j == 1 and k==2:
                        continue
                    if now == 0 and i == 1 and k==2:
                        continue
                    dp[n+1][now][i][j] += dp[n][i][j][k]
                    dp[n+1][now][i][j] %= mod

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

print(int(res))

Solution (Python):
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"
M = 10 ** 9 + 7
 
for j in range(n + 1):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        dp[j][c1 + c2 + c3] = 0
 
dp[0]["TTT"] = 1
 
for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[l + 1][c2 + c3 + p] += dp[l][c1 + c2 + c3]
          dp[l + 1][c2 + c3 + p] = dp[l + 1][c2 + c3 + p] % M
 
ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
      ans = ans % M
print(ans)

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


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


dp = [[] for i in range(n + 1)]
for i in range(n + 1):
    for j in range(4):
        dp[i].append([])
for i in range(n + 1):
    for j in range(4):
        for k in range(4):
            dp[i][j].append([])
for i in range(n + 1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k].append(0)
dp[0][T][T][T] = 1

for leng in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[leng][c1][c2][c3] == 0:
                    continue
                for x in range(4):
                    if x == C and c1 == G and c2 == A:
                        continue
                    if x == G and c1 == C and c2 == A:
                        continue
                    if x == C and c1 == G and c3 == A:
                        continue
                    if x == C and c2 == G and c3 == A:
                        continue
                    if x == C and c1 == A and c2 == G:
                        continue
                    dp[leng + 1][x][c1][c2] += dp[leng][c1][c2][c3]
                    dp[leng + 1][x][c1][c2] %= 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())
ng = ["agc", "aagc", "acgc", "aggc", "atgc", "agac", "agcc", "aggc", "agtc", "acg", "gac"]

x = {"a": 1, "g": 1, "c": 1, "t": 1}

for _ in range(1,N):
    y = dict()
    for let,num in x.items():
        for a in ["a", "c", "g", "t"]:
            if let[-3:] + a in ng or (let[-3:] + a)[-3:] in ng:
                continue
            else:
                if let[-3:] + a in y.keys():
                    y[let[-3:] + a] += num
                else:
                    y[let[-3:]+a] = num
    x = y

print(sum(x.values()) % (10**9+7))

Solution (Python):
def solve():
  n = int(input())
  mod = 10**9+7
  dp = [[[[0 for i in range(4)]for j in range(4)]for k in range(4)]for t in range(105)]
  dp[0][2][2][2] = 1
  
  for i in range(n):
    for c1 in range(4):
      for c2 in range(4):
        for c3 in range(4):
          for a4 in range(4):
            if [c2,c3,a4] == [0,1,2] or [c2,c3,a4] == [0,2,1] or [c2,c3,a4] == [1,0,2] or [c1,c2,a4] == [0,1,2] or [c1,c3,a4] == [0,1,2]:
              continue
            else:
              dp[i+1][c2][c3][a4] += dp[i][c1][c2][c3]
              dp[i+1][c2][c3][a4] %= mod
  ans = 0
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        ans += dp[n][c1][c2][c3]
        ans %= mod
  print(ans)
solve()

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

    
    ng_list_3 = [
        'AGC',
        'GAC',
        'ACG'
    ]
    ng_list_4 = [
        
        
        'AGGC',
        'ATGC',
        
        
        
        'AGTC'
    ]

    
    
    memo = dict()
    
    def count(s, n):
        
        if len(s) >= 4:
            l4 = s[-4:]
            if l4 in ng_list_4:
                return 0
        
        if len(s) >= 3:
            l3 = s[-3:]
            if l3 in ng_list_3:
                return 0

        
        if len(s) >= 4 and (s[-4:], n) in memo:
            return memo[(s[-4:], n)]
        
        
        if n == 0:
            return 1
        
        x = [
            count(s + 'A', n - 1),
            count(s + 'C', n - 1),
            count(s + 'G', n - 1),
            count(s + 'T', n - 1),
        ]
        x = sum(x) % (10**9 + 7)

        if len(s) >= 4:
            memo[(s[-4:], n)] = x
        
        return x

    print(count('', N))
    
resolve()

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

dp={b:1 for b in "ACGT"}

for _ in range(N-1):
  dp_new={}
  for k in dp:
    for b in "ACGT":
      new=k[-3:]+b
      if new[-3:] in ("AGC","GAC","ACG") or new in ("AGGC","ATGC","ACGC","AGTC","AGGC"):
        continue
      else:
        dp_new.setdefault(new,0)
        dp_new[new]+=dp[k]
  dp=dp_new

print(sum(dp.values())%MOD)

Solution (Python):
def solve(string):
    n = int(string)
    dp = [[0] * 4 for _ in range(n)]
    dp[0] = [1] * 4
    for i in range(1, n):
        base = sum(dp[i - 1])
        for j in range(4):
            dp[i][j] = base
        
        if i >= 2:
            dp[i][1] -= dp[i - 2][0] + dp[i - 2][2]
            dp[i][2] -= dp[i - 2][0]
        
        if i >= 3:
            dp[i][1] -= dp[i - 3][0] * 3
            dp[i][2] += dp[i - 3][2]

    return str(sum(dp[n - 1]) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
from itertools import product

N = int(input())
MOD = 10**9 + 7
A = 'A'
T = 'T'
G = 'G'
C = 'C'
ATGC = [A, T, G, C]

dp = {i: {c1: {c2: {c3: 0 for c3 in ATGC} for c2 in ATGC} for c1 in ATGC} for i in range(N+1)}
dp[0][T][T][T] = 1

for i, c1, c2, c3 in product(range(N), ATGC, ATGC, ATGC):
    if dp[i][c1][c2][c3] == 0:
        continue
    for c in ATGC:
        if (c1, c2, c) == (A, G, C) or (c1, c3, c) == (A, G, C):
            continue
        elif (c2, c3, c) == (A, G, C) or (c2, c3, c) == (A, C, G) or (c2, c3, c) == (G, A, C):
            continue
        dp[i+1][c2][c3][c] += dp[i][c1][c2][c3]
        dp[i+1][c2][c3][c] %= MOD

ans = 0
for c1, c2, c3 in product(ATGC, ATGC, ATGC):
    ans += dp[N][c1][c2][c3]
    ans %= MOD
print(ans)

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 + 1)]
dp[0][3][3][3] = 1

for i, l1, l2, l3 in product(range(N), range(4), range(4), range(4)):
    if dp[i][l1][l2][l3] == 0:
        continue

    for a in range(4):
        if (0, 1, 2) == (l2, l1, a):
            continue
        if (1, 0, 2) == (l2, l1, a):
            continue
        if (0, 2, 1) == (l2, l1, a):
            continue
        if (0, 1, 2) == (l3, l1, a):
            continue
        if (0, 1, 2) == (l3, l2, a):
            continue

        dp[i + 1][a][l1][l2] += dp[i][l1][l2][l3]
        dp[i + 1][a][l1][l2] %= mod

ans = 0
for l1, l2, l3 in product(range(4), range(4), range(4)):
    ans += dp[N][l1][l2][l3]
    ans %= mod
print(ans)

Solution (Python):
from functools import lru_cache


def check(s):
    bads = ["AGC", "ACG", "GAC"] + [b.format(_s) for b in ["AG{}C", "A{}GC"] for _s in "ACGT"]
    return not any(map(lambda x: x in s, bads))


def solve(string):
    n = int(string)

    @lru_cache(n * 4**3)
    def dfs(pos, last3):
        if pos == n:
            return 1
        ans = 0
        for _s in "ACGT":
            ans += dfs(pos + 1, last3[1:] + _s) if check(last3 + _s) else 0
        return ans % (10**9 + 7)

    return str(dfs(0, "TTT"))


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
from functools import lru_cache


def check(s):
    bads = ["AGC", "ACG", "GAC"] + ["AG{}C".format(_s) for _s in "ACGT"
                                   ] + ["A{}GC".format(_s) for _s in "ACGT"]
    return not any(map(lambda x: x in s, bads))


def solve(string):
    n = int(string)

    @lru_cache(n * 4**3)
    def dfs(pos, last3):
        if pos == n:
            return 1
        ans = 0
        for _s in "ACGT":
            ans += dfs(pos + 1, last3[1:] + _s) if check(last3 + _s) else 0
        return ans % (10**9 + 7)

    return str(dfs(0, "TTT"))


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


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

N = INT()

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


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


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


print(dfs(0, 'TCT'))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()

dp = [{} for i in range(N+1)]

def swap_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(current, last3):
	if last3 in dp[current]:
		return dp[current][last3]
	if current == N:
		return 1
	ret = 0
	for c in 'AGCT':
		if swap_ok(last3 + c):
			ret = (ret + dfs(current + 1, last3[1:] + c)) % MOD
	dp[current][last3] = ret
	return ret

print(dfs(0, 'ATC'))

Solution (Python):
from collections import defaultdict as dd
n = int(input())
mod,x,y,ans = 10**9+7,{"TTT":1},dd(int),0
def f(s):
    if s[1:]=="AG" or s[1:]=="GA" or s[:2]=="AG" or (s[0]=="A" and s[2]=="G"): return True
    else: return False
def make(s):
    global y
    for i in "ATGC":
        if (s[1:]=="AC" and i=="G") or (f(s) and i=="C"): pass
        else: y[s[1:]+i] = (y[s[1:]+i]+x[s])%mod
for i in range(n):
    for j in x.keys(): make(j)
    x,y = y,dd(int)
for i in x.values(): ans = (ans+i)%mod
print(ans)

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

if N == 3:
	print(61)

else:
	chars = "ACGT"
	invalid = [c+"AGC" for c in chars] + [c+"GAC" for c in chars] + [c+"ACG" for c in chars] + ["A"+c+"GC" for c in chars] + ["AG"+c+"C" for c in chars] + ["AGC"+c for c in chars] + ["GAC"+c for c in chars] + ["ACG"+c for c in chars]

	now={}
	for w in chars:
		for x in chars:
			for y in chars:
				for z in chars:
					s=w+x+y+z
					if s not in invalid:
						now[s] = 1

	for _ in range(N-4):
		new={}
		for s in now.keys():
			for c in chars:
				ns=s[1:]+c
				if ns not in invalid:
					if ns not in new:
						new[ns] = 0
					new[ns] += now[s]
					new[ns] %= 10**9+7
		now=new

	print(sum(now.values()) % (10**9+7))

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

memoCou = {}

n = int(input())


def cou(n, s):
    if(memoCou.get((n, s)) != None):
        return memoCou.get((n, s))
    if(not ok(s)):
        return 0
    
    if(n == 0):
        return 1
    memoCou.update({(n, s): cou(
        n-1, s[1:]+"A")+cou(n-1, s[1:]+"C")+cou(n-1, s[1:]+"G")+cou(n-1, s[1:]+"T")})
    return memoCou.get((n, s))


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


print(cou(n, "TTTT") % 1000000007)

Solution (Python):
n=int(input())
a=3
b=4
c=4
d=1
e=1
f=1
g=4
h=9
i=12
j=22
for x in range(3,n):
    anew=i
    bnew=c+d+e+h
    cnew=b+i
    dnew=c
    enew=g
    fnew=c
    gnew=b+i
    hnew=d+e+f+h+j
    inew=a+b+f+g+i+j
    jnew=a*2+d+e+f+(g+h+j)*2
    a=anew
    b=bnew
    c=cnew
    d=dnew
    e=enew
    f=fnew
    g=gnew
    h=hnew
    i=inew
    j=jnew
Sum=a+b+c+d+e+f+g+h+i+j
print(Sum%(10**9+7))

Solution (Python):


N = int(input())

dp = {b: 1 for b in "ACGT"}
for _ in range(N - 1):
    dp_new = {}
    for k in dp:
        for b in "ACGT":
            n = k[-3:] + b
            if n[-3:] in ("AGC", "ACG", "GAC") or n in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                continue
            else:
                if n in dp_new:
                    dp_new[n] += dp[k]
                else:
                    dp_new[n] = dp[k]
    dp = dp_new

print(sum(dp.values()) % (10 ** 9 + 7))

Solution (Python):


import itertools
comb = list(map(''.join, itertools.product("ACGT", repeat=4)))

N = int(input())

dp = {c: [0, 0] for c in comb}
dp["TTTT"] = [1, 0]

for _ in range(N):
    dp_new = {c: [0, 0] for c in comb}
    for k in dp:
        for b in "ACGT":
            if k[2:4] + b in ("AGC", "ACG", "GAC") or k[1:4] + b in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                dp_new[k[1:4] + b][1] += dp[k][0] + dp[k][1]
            else:
                dp_new[k[1:4] + b][0] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
    dp = dp_new

mod = int(1e9) + 7
print((4 ** N - sum([dp[k][1] for k in dp])) % mod)

Solution (Python):


import itertools
comb = list(map(''.join, itertools.product("ACGT", repeat=4)))

mod = int(1e9) + 7

N = int(input())

dp = {c: [0, 0] for c in comb}
dp["TTTT"] = [1, 0]

for _ in range(N):
    dp_new = {c: [0, 0] for c in comb}
    for k in dp:
        for b in "ACGT":
            if k[2:4] + b in ("AGC", "ACG", "GAC") or k[1:4] + b in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                dp_new[k[1:4] + b][1] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
            else:
                dp_new[k[1:4] + b][0] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
    dp = dp_new


print((4 ** N - sum([dp[k][1] for k in dp])) % mod)

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







def dfs(index,last3):
	if last3 in memo[index]:
		return memo[index][last3]
	if index == N:
		return 1
	c_next = 'AT'
	if last3[1:] != 'AC':
		c_next += 'G'
	if ('AG' in last3) == False:
		if  last3[1:] != 'GA':
			if last3[0]+last3[2] != 'AG':
				c_next += 'C'
	count = 0
	for c in c_next:
		count += dfs(index+1,last3[1:]+c)
		count %= MOD

	memo[index][last3] = count
	return count

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):
        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())
ng = ["agc", "aagc", "acgc", "aggc", "atgc", "agac", "agcc", "aggc", "agtc", "acg", "gac"]
c = 0

x = {"a": 1, "g": 1, "c": 1, "t": 1}
for _ in range(N - 1):
    y = {}
    for k, v in x.items():
        n = k[-3:]
        for s in ["a", "c", "g", "t"]:
            if n + s in ng or (n + s)[-3:] in ng:
                continue
            if n + s in y.keys():
                y[n + s] += v
            else:
                y[n + s] = v
    x = y

print(sum(x.values()) % 1000000007)

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


bad   = [0]
badA  = [0]
badG  = [0]
badAC = [0]

def nall(n):
    """長さnのACGT列の総数"""
    return 4 ** n if n >= 0 else 0

def good(n):
    """条件を満たす長さnのACGT列の個数"""
    return nall(n) - bad[n] if n >= 0 else 0
def goodG(n):
    """条件を満たす長さnのACGT列のうち接尾辞がGであるものの個数"""
    return nall(n - 1) - badG[n] if n >= 0 else 0
def goodAC(n):
    """条件を満たす長さnのACGT列のうち接尾辞がACであるものの個数"""
    return nall(n - 2) - badAC[n] if n >= 0 else 0

for n in range(1, N + 1):
    b  = bad [n - 1] * 4              
    b += good(n - 3)                  
    b += good(n - 3) - goodG (n - 3)  
    b += good(n - 3) - goodAC(n - 3)  
    b += good(n - 4) * 3              
    bad.append(b)
    bA   = bad [n - 1]  
    bG   = bad [n - 1]  
    bAC  = badA[n - 1]  
    bG  += good(n - 3) - goodG (n - 3)  
    bAC += good(n - 3) - goodAC(n - 3)  
    badA.append(bA)
    badG.append(bG)
    badAC.append(bAC)

print(good(N) % (10 ** 9 + 7))

Solution (Python):
a = "$ACGT"
mod = 10**9 + 7
N = int(input())
dp = [[[[0 for l in range(5)] for k in range(5)] for j in range(5)]
      for i in range(N + 1)]

dp[0][0][0][0] = 1
ans = 0
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 (m == 2):
                        if (j == 1) and (k == 3):
                            continue
                        if (j == 1) and (l == 3):
                            continue
                        if (k == 1) and (l == 3):
                            continue
                        if (k == 3) and (l == 1):
                            continue
                    elif (m == 3):
                        if (k == 1) and (l == 2):
                            continue

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

                    if i + 1 == N:
                        ans += dp[i][j][k][l]
                        ans %= mod

print(ans)

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


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

memo = [{} for i in range(n)]

def dfs(depth=0, last3="TTT"):
    if depth == n:
        
        
        return 1
    if last3 in memo[depth]:
        return memo[depth][last3]

    res = 0
    for c in "ACGT":
        if check(last3+c):
            res += dfs(depth+1, last3[1:]+c)
            res %= mod
    memo[depth][last3] = res
    return res

print(dfs())