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 bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m
    
    def add(self, a, b):
        return (a + b ) % self.m

    def sub(self, a, b):
        return (a - b) % self.m
    
    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, self.pow(b, self.m-2))

    def pow(self, x, y):
        if y == 0: 
            return 1
        elif y == 1: 
            return x % self.m
        elif y % 2 == 0: 
            return self.pow(x, y//2)**2 % self.m
        else: 
            return self.pow(x, y//2)**2 * x % self.m


@mt
def slv(N):
    if N==3:
        return 61

    m = Mod(10**9+7)
    dp = {}
    iv = [
        'agc',
        'acg',
        'gac',
        'aggc'
        'acgc',
        'atgc',
        'agac',
        'aggc',
        'agtc',
    ]
    for s in product('agct', repeat=4):
        s = ''.join(s)
        if not any(map(lambda x: x in s, iv)):
            dp[s] = 1

    for _ in range(N-4):
        dp_ = Counter()
        for k, v in dp.items():
            for c in 'agct':
                s = k + c
                s = s[1:]
                if s in dp:
                    dp_[s] = m.add(v, dp_[s])
        dp = dp_
    
    return reduce(lambda x, y: m.add(x, y), dp.values())


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = ["A","C","G","T"]
lis = ["AGC","ACG","GAC"]

d = {}
for i in s:
    for j in s:
        for k in s:
            if i + j + k in lis:
                d[i + j + k] = 0
            else:
                d[i + j + k] = 1

dd = {}
for _ in range(n-3):
    for i in s:
        for j in s:
            for k in s:
                num = 0
                for nu in s:
                    if nu + j + k != "AGC" and nu + i + k != "AGC":
                        num += d[nu + i + j]
                    if i + j + k in lis:
                        dd[i + j + k] = 0
                    else:
                        dd[i + j + k] = num % (10 ** 9 + 7)
    dd,d = d,dd

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

Solution (Python):
N = int(input())
dp = [[[[0 for l in range(4)] for k in range(4)]
       for j in range(4)] for i in range(N)]
for j in range(4):
    for k in range(4):
        for l in range(4):
            if not (j == 0 and k == 1 and l == 2)\
                    and not(j == 0 and k == 2 and l == 1)\
                    and not (j == 2 and k == 0 and l == 1):
                dp[2][j][k][l] = 1
for i in range(2, N-1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] %= 10**9+7
                dp[i+1][k][l][0] += dp[i][j][k][l]
                
                
                
                
                
                if not (j == 0 and k == 2) \
                   and not (k == 2 and l == 0)\
                   and not (j == 0 and l == 2)\
                   and not (k == 0 and l == 2):
                    dp[i+1][k][l][1] += dp[i][j][k][l]
                
                if not (k == 0 and l == 1):
                    dp[i+1][k][l][2] += dp[i][j][k][l]
                dp[i+1][k][l][3] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N-1][j][k][l]
ans %= 10**9+7
print(ans)

Solution (Python):
N=int(input())
if N==3:
  print(61)
  exit()
dp=[[0]*64 for i in range(N+1)]
dp[3]=[1]*64
dp[3][11],dp[3][14],dp[3][35]=0,0,0
NG=[]
mask=63
mod=10**9+7
for i in range(4):
  NG.append(64*i+16*0+4*2+3)
  NG.append(64*0+16*2+4*i+3)
  NG.append(64*0+16*i+4*2+3)
  NG.append(64*i+16*0+4*3+2)
  NG.append(64*i+16*2+4*0+3)
for i in range(3,N):
  for k in range(64):
    for s in range(4):
      flag=True
      for ng in NG:
        if ng==((k<<2)+s):
          flag=False
          break
      if flag:
        dp[i+1][((k<<2)+s)&mask]+=dp[i][k]
        dp[i+1][((k<<2)+s)&mask]%=mod
ans=0
for k in range(64):
  ans+=dp[N][k]
  ans%=mod
print(ans)

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
dp = [[[[0 for k in range(4)] for k in range(4)] for j in range(4)] for i in range(101)]
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 a in range(4):
          if a == 2 and i == 1 and j == 0: continue
          if a == 2 and i == 0 and j == 1: continue
          if a == 1 and i == 2 and j == 0: continue
          if a == 2 and i == 1 and k == 0: continue
          if a == 2 and j == 1 and k == 0: continue

          dp[length + 1][a][i][j] += dp[length][i][j][k]
          dp[length + 1][a][i][j] %= MOD

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

print(ans)

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

DP=[1]+[0]*13

for i in range(N):
    NDP=[0]*14

    NDP[0]=DP[0]*2+DP[1]*2+DP[5]*2+DP[7]*2+DP[9]+DP[10]+DP[11]*2+DP[13]
    NDP[1]=DP[0]+DP[13]
    NDP[2]=DP[1]+DP[9]+DP[10]+DP[11]
    NDP[3]=DP[0]+DP[5]+DP[7]+DP[13]
    NDP[4]=DP[2]+DP[3]+DP[12]
    NDP[5]=DP[3]+DP[6]
    NDP[6]=DP[2]+DP[3]+DP[6]+DP[12]
    NDP[7]=DP[2]+DP[3]+DP[6]+DP[12]
    NDP[8]=DP[6]
    NDP[9]=DP[7]
    NDP[10]=DP[4]+DP[8]
    NDP[11]=DP[1]+DP[9]+DP[10]+DP[11]
    NDP[12]=DP[4]+DP[8]
    NDP[13]=DP[4]+DP[8]

    for i in range(14):
        NDP[i]=NDP[i]%mod


    DP=NDP
    

print(sum(DP)%mod)

Solution (Python):


import math
import sys
import itertools
import numpy as np


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

a=[[[[0]*4]*4]*4]*101
a=[[[[0 for i in range(4)] for j in range(4)] for j in range(4)] for j in range(101)]
a[3][0][0][0]= 1
a[3][0][0][1]= 1
a[3][0][0][2]= 1
a[3][0][0][3]= 1
a[3][0][1][0]= 1
a[3][0][1][1]= 1
a[3][0][1][2]= 0
a[3][0][1][3]= 1
a[3][0][2][0]= 1
a[3][0][2][1]= 0
a[3][0][2][2]= 1
a[3][0][2][3]= 1
a[3][0][3][0]= 1
a[3][0][3][1]= 1
a[3][0][3][2]= 1
a[3][0][3][3]= 1
 
a[3][1][0][0]= 1
a[3][1][0][1]= 1
a[3][1][0][2]= 1
a[3][1][0][3]= 1
a[3][1][1][0]= 1
a[3][1][1][1]= 1
a[3][1][1][2]= 1
a[3][1][1][3]= 1
a[3][1][2][0]= 1
a[3][1][2][1]= 1
a[3][1][2][2]= 1
a[3][1][2][3]= 1
a[3][1][3][0]= 1
a[3][1][3][1]= 1
a[3][1][3][2]= 1
a[3][1][3][3]= 1
 
a[3][2][0][0]= 1
a[3][2][0][1]= 0
a[3][2][0][2]= 1
a[3][2][0][3]= 1
a[3][2][1][0]= 1
a[3][2][1][1]= 1
a[3][2][1][2]= 1
a[3][2][1][3]= 1
a[3][2][2][0]= 1
a[3][2][2][1]= 1
a[3][2][2][2]= 1
a[3][2][2][3]= 1
a[3][2][3][0]= 1
a[3][2][3][1]= 1
a[3][2][3][2]= 1
a[3][2][3][3]= 1
 
a[3][3][0][0]= 1
a[3][3][0][1]= 1
a[3][3][0][2]= 1
a[3][3][0][3]= 1
a[3][3][1][0]= 1
a[3][3][1][1]= 1
a[3][3][1][2]= 1
a[3][3][1][3]= 1
a[3][3][2][0]= 1
a[3][3][2][1]= 1
a[3][3][2][2]= 1
a[3][3][2][3]= 1
a[3][3][3][0]= 1
a[3][3][3][1]= 1
a[3][3][3][2]= 1
a[3][3][3][3]= 1
 

for i in range(4,n+1):
    for s in range(4):
        for t in range(4):
            for u in range(4):
                if (s==0 and t==2 and u==1) or (s==2 and t==0 and u ==1) or (s==0 and t==1 and u ==2):
                    a[i][s][t][u]=0
                elif (s==2 and t==3 and u==1) or (s==2 and t==2 and u ==1) or (s==3 and t==2 and u ==1):
                    a[i][s][t][u] = a[i-1][1][s][t] + a[i-1][2][s][t] + a[i-1][3][s][t]
                else:
                    a[i][s][t][u] = a[i-1][0][s][t] + a[i-1][1][s][t] + a[i-1][2][s][t] + a[i-1][3][s][t]


answer =0
for s in range(4):
    for t in range(4):
        for u in range(4):
            answer += a[n][s][t][u]

print(answer % p)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import product
import numpy as np

def main():
    N = II()
    A, G, C, T = 0, 1, 2, 3
    dp = np.zeros((N + 1, 4, 4, 4), int)
    dp[0, T, T, T] = 1
    for n in range(N):
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) == (A, G, C):
                    continue
                if (p2, p1, cur) == (A, C, G):
                    continue
                if (p2, p1, cur) == (G, A, C):
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                dp[n + 1, cur, p1, p2] = \
                    (dp[n + 1, cur, p1, p2] + dp[n, p1, p2, p3]) % MOD
    ans = np.sum(dp[N])

    return ans % MOD

print(main())

Solution (Python):

"""
Created on Sun Mar 24 20:51:04 2019

@author: Yamazaki Kenichi
"""

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

res = [[0 for j in range(14)] for i in range(N+1)]
res[1][0],res[1][1],res[1][2],res[1][3] = 1,1,1,1


for i in range(2,N+1):
    res[i][0] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][2]-res[i-1][4]-res[i-1][11]-res[i-1][12]-res[i-1][13]
    res[i][1] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][10]-res[i-1][11]-res[i-1][12]-res[i-1][13]
    res[i][2] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][7]-res[i-1][12]-res[i-1][5]
    res[i][3] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][12]
    res[i][4] = res[i-1][0]            +res[i-1][8]+res[i-1][9]
    res[i][5] = res[i-1][0]+res[i-1][6]
    res[i][6] = res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    res[i][7] = res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    res[i][8] = res[i-1][2]+res[i-1][11]+res[i-1][13]
    res[i][9] = res[i-1][4]+res[i-1][12]
    res[i][10] = res[i-1][4]+res[i-1][12]
    res[i][11] = res[i-1][4]+res[i-1][12]
    res[i][12] = res[i-1][6]
    res[i][13] = res[i-1][7]

print(sum(res[-1])%mod)

Solution (Python):
N = input()

T = [[[0]*4 for i in range(4)] for j in range(4)]
for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      if (0, 1, 2) not in [
        (c1, c2, c3),
        (c2, c1, c3),
        (c1, c3, c2),
      ]:
        T[c1][c2][c3] = 1

for i in range(3, N):
  P = T
  T = [[[0]*4 for i in range(4)] for j in range(4)]
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for c4 in range(4):
          if (0, 1, 2) not in [
            (c2, c3, c4),
            (c3, c2, c4),
            (c2, c4, c3),
            (c1, c3, c4),
            (c1, c2, c4),
          ]:
            T[c2][c3][c4] += P[c1][c2][c3]
            T[c2][c3][c4] %= 1000000007
print sum(sum(sum(t2) for t2 in t1) for t1 in T) % 1000000007

Solution (Python):
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 l in range(N + 1)]
DP[0][3][3][3] = 1

for len in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if DP[len][i][j][k] == 0: continue
        for a in range(4):
          if (a, i, j) == (2, 1, 0): continue
          if (a, i, j) == (2, 0, 1): continue
          if (a, i, j) == (1, 2, 0): continue
          if (a, i, k) == (2, 1, 0): continue
          if (a, j, k) == (2, 1, 0): continue

          DP[len + 1][a][i][j] += DP[len][i][j][k]
          DP[len + 1][a][i][j] % MOD

Ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      Ans += DP[N][i][j][k]
      Ans %= MOD
                         
print(Ans)

Solution (Python):



from itertools import chain, product
from functools import reduce
from collections import OrderedDict, Counter, deque
import operator

IS = lambda: int(input())

N = IS()
p = 10**9+7

A, C, G, T = range(4)
prev = [1] * (4**2)
banned = set([
    (A << 4) + (G << 2) + C,
    (G << 4) + (A << 2) + C,
    (A << 4) + (C << 2) + G,
    ])

cur = [0] * (4**3)
for i in range(4):
    i4 = i << 2
    i8 = i << 4
    for j in range(4):
        j4 = j << 2
        for k in range(4):
            if (i8 + j4 + k) in banned: continue
            cur[i8 + j4 + k] += prev[i4 + j]
prev = [x % p for x in cur]

banned |= set(map(sum, product([x<<6 for x in range(4)], banned)))
banned |= set(map(sum, product([x<<4 for x in range(4)], [
    (A << 6) + (G << 2) + C,
    ])))
banned |= set(map(sum, product([x<<2 for x in range(4)], [
    (A << 6) + (G << 4) + C,
    ])))

for _ in range(3,N):
    cur = [0] * (4**3)
    for i in range(4):
        i4 = i << 2
        i8 = i << 4
        i16 = i << 6
        for j in range(4):
            j4 = j << 2
            j8 = j << 4
            for k in range(4):
                k4 = k << 2
                for l in range(4):
                    if (i16 + j8 + k4 + l) in banned: continue
                    cur[j8 + k4 + l] += prev[i8 + j4 + k]
    prev = [x % p for x in cur]

print(sum(prev) % p)

Solution (Python):
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = not True
R = 1000000007
def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = c = g = t = 1
ac = ag = at = 0
ga  = 0
agg = agt = atg = 0

for i in range(n-1):
    xatg = at
    xagg = ag
    xagt = ag
    xat = a
    xag = a
    xac = a - ga
    xga = g
    xa = a + c + g + t
    xc = a + c + g + t - ga - ag - atg - agg - agt
    xg = a + c + g + t - ac
    xt = a + c + g + t
    a = xa % R
    c = xc % R
    g = xg % R
    t = xt % R
    ac = xac % R
    ag = xag % R
    at = xat % R
    ga = xga % R
    agg = xagg % R
    agt = xagt % R
    atg = xatg % R
    ddprint("i {}: a {} c {} g {} t {} ".format(i,xa,xc,xg,xt))
    ddprint("     ac {} ag {} at {} ga {} ".format(xac,xag,xat,xga))
    ddprint("     agg {} agt {} atg {} ".format(xagg,xagt,xatg))

print((a+c+g+t)%R)

Solution (Python):



import sys
import itertools as itr

S = []

dp = [] 

def init():
  dct = {}
  for i in ['A','C','G','T']:
    for j in ['A','C','G','T']:
      for k in ['A','C','G','T']:
        s = i+j+k
        if s not in ['AGC','ACG','GAC']:
          dct[s] = 1
  return dct


def chk(s):
  if ('AGC' in s) or ('ACG' in s) or ('GAC' in s):
    return False
  elif ('AGAC' in s) or ('AGCC' in s) or ('AGGC' in s) or ('AGTC' in s):
    return False
  elif ('AAGC' in s) or ('ACGC' in s) or ('AGGC' in s) or ('ATGC' in s):
    return False
  else:
    return True


n = int(input())-3

dp = init()
for i in range(n):
  dct = {}
  for s in dp:
    for c in ['A','C','G','T']:
      if chk(s+c):
        if s[1:]+c not in dct:
          dct[s[1:]+c] = dp[s] % (10**9+7)
        else:
          dct[s[1:]+c] += dp[s] % (10**9+7)
  dp = dct

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

Solution (Python):
import itertools as it

N=int(input())
dp=dict()
def ok(s):
    return all(['AGC' not in t for t in 
        [s, s[0:2]+s[3]+s[2], s[0]+s[2]+s[1]+s[3], s[1]+s[0]+s[2:4]]]) 

def n(j, s):
    if j == 3:
        return 1 if s not in ["AGC", "ACG", "GAC"] else 0
    if (j, s) in dp:
        return dp[(j, s)]
    ret = sum([
        n(j-1, "A"+s[:3]) if ok("A"+s[:3]) else 0,
        n(j-1, "C"+s[:3]) if ok("C"+s[:3]) else 0,
        n(j-1, "G"+s[:3]) if ok("G"+s[:3]) else 0,
        n(j-1, "T"+s[:3]) if ok("T"+s[:3]) else 0]
    )
    dp[(j, s)]=ret
    return ret

m=sum([n(N, "".join(s)) for s in it.product("ACGT", repeat=3)])
print(m%(10**9+7))

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

def ok(last4):
    if "AGC" in last4:
        return False
    for i in range(3):
        t = list(last4)
        t[i], t[i+1] = t[i+1], t[i]
        if "AGC" in "".join(t):
            return False
    return True
def dfs(cur, last3):
    if cur == N:
        return 1
    if last3 in memo[cur]:
        return memo[cur][last3]
    ret = 0
    for c in "ACGT":
        if ok(last3+c):
            ret += dfs(cur + 1, last3[1:] + c) % (10**9 + 7)
    memo[cur][last3] = ret
    return ret % (10**9 + 7)
print(dfs(0, "TTT"))

Solution (Python):
import sys

def check(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, N, memo=[]):
    if last3 in memo[cur]:
        return memo[cur][last3]

    if cur == N:
        return 1

    ret = 0
    for c in 'AGCT':
        if check(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:]+c, N, memo)) % (10**9 + 7)
    memo[cur][last3] = ret
    return ret


def main():
    input = sys.stdin.readline
    N = int(input())

    memo = [{} for _ in range(N+1)]
    print(dfs(0, 'TTT', N, memo))

if __name__ == '__main__':
    main()

Solution (Python):


if __name__ == '__main__':
    n = int(input())
    pd = {"   ": 1}
    d = {"   ": 1}
    for i in range(n):
        pd = d
        d = {}
        for k, v in pd.items():
            for j in "AGTC":
                t = k+j
                t1 = t[1] + t[0] + t[2] + t[3]
                t2 = t[0] + t[2] + t[1] + t[3]
                t3 = t[0] + t[1] + t[3] + t[2]
                if not ("AGC" in t or "AGC" in t1 or "AGC" in t2 or "AGC" in t3):
                    if t[1:] in d:
                        d[t[1:]] += v
                    else:
                        d[t[1:]] = v
                    d[t[1:]] %= 1000000007
    sum = 0
    for v in d.values():
        sum += v
    sum %= 1000000007
    print(sum)

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











A=0
C=1
G=2
T=3
dp = [[[[0 for i4 in range(4)] for i3 in range(4)] for i2 in range(4)] for i in range(N+10)]
dp[0][T][T][T] = 1

for i1 in range(1,N+1):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                for i5 in range(4):
                    if i3==A and i4==C and i5==G: continue
                    if i3==A and i4==G and i5==C: continue
                    if i3==G and i4==A and i5==C: continue
                    if i2==A and i4==G and i5==C: continue
                    if i2==A and i3==G and i5==C: continue
                    dp[i1][i3][i4][i5] += dp[i1-1][i2][i3][i4]

ans=0
for i1 in range(4):
    for i2 in range(4):
        ans += sum(dp[N][i1][i2])

print(ans % mod)

Solution (Python):
import sys

N=int(input())
if N==3:
    print(61)
    sys.exit()

dp=[[[[0 for i in range(4)] for i in range(4)] for i in range(4)] for i in range(N+1)]
A=0;G=1;C=2;T=3;
mod=10**9+7
dp[0][3][3][3]=1
def check(i,j,k,l):
    if i==A and k==G and l==C:
        return 0
    if j==A and k==G and l==C:
        return 0
    if j==G and k==A and l==C:
        return 0
    if j==A and k==C and l==G:
        return 0
    if i==A and j==G and l==C:
        return 0
    else:
        return 1

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

Solution (Python):
n = int(input())
aaa = [1]
aat = [1]
aac = [1]
aag = [1]
ata = [1]
att = [1]
atc = [1]
atg = [1]
aca = [1]
act = [1]
acc = [1]
aga = [1]
agt = [1]
agg = [1]
taa = [1]
tat = [1]
tac = [1]
tag = [1]
tta = [1]
ttt = [1]
ttc = [1]
ttg = [1]
tca = [1]
tct = [1]
tcc = [1]
tcg = [1]
tga = [1]
tgt = [1]
tgc = [1]
tgg = [1]
caa = [1]
cat = [1]
cac = [1]
cag = [1]
cta = [1]
ctt = [1]
ctc = [1]
ctg = [1]
cca = [1]
cct = [1]
ccc = [1]
ccg = [1]
cga = [1]
cgt = [1]
cgc = [1]
cgg = [1]
gaa = [1]
gat = [1]
gag = [1]
gta = [1]
gtt = [1]
gtc = [1]
gtg = [1]
gca = [1]
gct = [1]
gcc = [1]
gcg = [1]
gga = [1]
ggt = [1]
ggc = [1]
ggg = [1]
for i in range(n-3):
    aaa.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    aat.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    aac.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    aag.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    ata.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    att.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    atc.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    atg.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    aca.append((aac[i]+tac[i]+cac[i])%(10**9+7))    
    act.append((aac[i]+tac[i]+cac[i])%(10**9+7))   
    acc.append((aac[i]+tac[i]+cac[i])%(10**9+7))   
    aga.append((aag[i]+tag[i]+cag[i]+gag[i])%(10**9+7)) 
    agt.append((aag[i]+tag[i]+cag[i]+gag[i])%(10**9+7)) 
    agg.append((aag[i]+tag[i]+cag[i]+gag[i])%(10**9+7))
    taa.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7)) 
    tat.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7)) 
    tac.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7))
    tag.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7)) 
    tta.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7))
    ttt.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7))
    ttc.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7))
    ttg.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7)) 
    tca.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7))
    tct.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7))
    tcc.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7))
    tcg.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7)) 
    tga.append((atg[i]+ttg[i]+ctg[i]+gtg[i])%(10**9+7))
    tgt.append((atg[i]+ttg[i]+ctg[i]+gtg[i])%(10**9+7))
    tgc.append((ttg[i]+ctg[i]+gtg[i])%(10**9+7))
    tgg.append((atg[i]+ttg[i]+ctg[i]+gtg[i])%(10**9+7)) 
    caa.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cat.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cac.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cag.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cta.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    ctt.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    ctc.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    ctg.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    cca.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    cct.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    ccc.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    ccg.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    cga.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    cgt.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    cgc.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    cgg.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    gaa.append((aga[i]+tga[i]+cga[i]+gga[i])%(10**9+7))
    gat.append((aga[i]+tga[i]+cga[i]+gga[i])%(10**9+7))
    gag.append((aga[i]+tga[i]+cga[i]+gga[i])%(10**9+7))
    gta.append((agt[i]+tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gtt.append((agt[i]+tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gtc.append((tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gtg.append((agt[i]+tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gca.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gct.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gcc.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gcg.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gga.append((agg[i]+tgg[i]+cgg[i]+ggg[i])%(10**9+7))
    ggt.append((agg[i]+tgg[i]+cgg[i]+ggg[i])%(10**9+7))
    ggc.append((tgg[i]+cgg[i]+ggg[i])%(10**9+7))
    ggg.append((agg[i]+tgg[i]+cgg[i]+ggg[i])%(10**9+7))
print((aaa[-1]+aat[-1]+aac[-1]+aag[-1]+ata[-1]+att[-1]+atc[-1]+atg[-1]+aca[-1]+act[-1]
      +acc[-1]+aga[-1]+agt[-1]+agg[-1]+taa[-1]+tat[-1]+tac[-1]+tag[-1]+tta[-1]+ttt[-1]
      +ttc[-1]+ttg[-1]+tca[-1]+tct[-1]+tcc[-1]+tcg[-1]+tga[-1]+tgt[-1]+tgc[-1]+tgg[-1]
      +caa[-1]+cat[-1]+cac[-1]+cag[-1]+cta[-1]+ctt[-1]+ctc[-1]+ctg[-1]+cca[-1]+cct[-1]
      +ccc[-1]+ccg[-1]+cga[-1]+cgt[-1]+cgc[-1]+cgg[-1]+gaa[-1]+gat[-1]+gag[-1]+gta[-1]
      +gtt[-1]+gtc[-1]+gtg[-1]+gca[-1]+gct[-1]+gcc[-1]+gcg[-1]+gga[-1]+ggt[-1]+ggc[-1]+ggg[-1])%(10**9+7))

Solution (Python):
def check(s):
    c = False
    if s[:3] == "AGC" or s[1:] == "AGC" or s[0] + s[2:] == "AGC" or s[:2] + s[3] == "AGC" or s[:3] == "ACG" or s[1:] == "ACG" or s[:3] == "GAC" or s[1:] == "GAC":
        c = True
    return c

from collections import defaultdict
from itertools import product
N = int( input())
Q = 10**9 + 7
dp = [ defaultdict( int) for _ in range(N+1)]

for s in product("AGCT", repeat = 3):
    dp[3]["".join(s)] = 1
ans = 0
for i in range(4, N+1):
    for c in product("AGCT", repeat = 3):
        c = "".join(c)
        for t in "AGCT":
            if check(c+t):
                
                ans += (dp[i-1][c]*pow(4,N-i,Q))%Q
                ans %= Q
            else:
                dp[i][c[1:]+t] += dp[i-1][c]
                dp[i][c[1:]+t] %= Q
if N == 3:
    ans = 3
print( (pow(4,N,Q) - ans)%Q)

Solution (Python):
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]
memo = [{} for _ in range(N+1)]

def func(cur, S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    if S[-3:] in memo[cur]:
        return memo[cur][S[-3:]]
    else:
        if cur==N:
            return 1
        ret = 0
        for s in "ACGT":
            ret = ret + func(cur+1, S+s)
        memo[cur][S[-3:]] = ret
        return ret


print(func(0, "____")%(10**9+7))

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int):
    dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    
    chars = ['A', 'G', 'C', 'T']
    for i in range(4):
        for j in range(4):
            for k in range(4):
                dp[3][i][j][k] = 1
    dp[3][0][1][2] = 0
    dp[3][0][2][1] = 0
    dp[3][1][0][2] = 0
    cnt = 0
    for i in range(3, N):
        for j1, c1 in enumerate(chars):
            for j2, c2 in enumerate(chars):
                for j3, c3 in enumerate(chars):
                    for j4, c4 in enumerate(chars):
                        cs4 = c1+c2+c3+c4
                        cs3 = c2+c3+c4
                        if 'AGC'==cs3 or 'ACG'==cs3 or 'GAC'==cs3 or 'AAGC'==cs4 or 'ACGC'==cs4 or 'AGGC'==cs4 or 'ATGC'==cs4 or 'AGAC'==cs4 or 'AGGC'==cs4 or 'AGCC'==cs4 or 'AGTC'==cs4:
                            continue
                        cnt += 1
                        dp[i+1][j2][j3][j4] += dp[i][j1][j2][j3]
                        dp[i+1][j2][j3][j4] %= MOD
    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                ans += dp[N][i][j][k]
                ans %= MOD
    print(ans)

    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):
A=0;G=1;C=2;T=3
N=int(input())
dp=[[[[0 for i in range(4)]for i in range(4)]for i in range(4)]for i in range(N+1)]
mod=10**9+7
dp[0][T][T][T]=1
for i in range(N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if (k==A and l==G and m==C):
                        continue
                    if (k==G and l==A and m==C):
                        continue
                    if (k==A and l==C and m==G):
                        continue
                    if (j==A and l==G and m==C):
                        continue
                    if (j==A and k==G and m==C):
                        continue
                    dp[i+1][k][l][m]+=dp[i][j][k][l]
                    dp[i+1][k][l][m]%=mod
ans=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans+=dp[N][i][j][k]
            ans%=mod
print(ans)

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

def ok(last4:str)->bool:
    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):
import functools


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


@functools.lru_cache(maxsize=None)
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


@functools.lru_cache(maxsize=None)
def dfs(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
    return ret


print(dfs(0, 'TTT'))

Solution (Python):
import collections as c
ip = lambda : map(int, input().split())


N = int(input())
mod = 1000000007
A=0
T=1
C=2
G=3
dp = [[[[0,0,0,0] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]

for j in range(4):
    for k in range(4):
        for l in range(4):
            dp[3][j][k][l] = 1
dp[3][A][G][C],dp[3][A][C][G],dp[3][G][A][C] = 0,0,0

for i in range(4,N+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] += (dp[i-1][A][j][k]+dp[i-1][T][j][k]+dp[i-1][C][j][k]+dp[i-1][G][j][k]) % mod
                dp[i][j][k][l] %= mod



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

    dp[i][T][G][C] -= dp[i-1][A][T][G]

    dp[i][G][G][C] -= dp[i-1][A][G][G]
    
    dp[i][G][T][C] -= dp[i-1][A][G][T]

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