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):


log = lambda *x: print(*x)

def no_c(f,s,t):
    if f==1 and t==2: return True
    if f==1 and s==2: return True
    if s==1 and t==2: return True
    if s==2 and t==1: return True
    return False

def no_g(f,s,t):
    if s==1 and t==3: return True
    return False

def solve(k):
    dp = [[ [([0]*5) for i in range(5)] for i in range(5) ] for i in range(k+1)]

    for l in range(k, 0, -1):
        for f in range(0,5):
            for s in range(0,5):
                for t in range(0,5):
                    if l == k:
                        dp[l][f][s][t] = 1
                        continue

                    if l == 1:
                        dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][3] + dp[l+1][s][t][4]

                    if l == 2:
                        if (s==1 and t==2) or (s==2 and t==1): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][4]
                        if (s==1 and t==3): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][3] + dp[l+1][s][t][4]
                        else: dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][3] + dp[l+1][s][t][4]

                    if no_c(f,s,t): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][4]
                    elif no_g(f,s,t): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][3] + dp[l+1][s][t][4]
                    else: dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][3] + dp[l+1][s][t][4]

    return sum(dp[1][0][0][t] for t in (1,2,3,4)) % 1000000007

log(solve(int(input())))

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

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):
  if last3 in memo[cur]:
    return memo[cur][last3]
  if cur == N:
    return 1
  ret = 0
  
  for c in 'ACGT':
    
    if check(last3 + c):
      ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
  memo[cur][last3] = ret
  return ret
print(dfs(0, 'TTT'))

Solution (Python):
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main_old(): 
    N = II()
    
    dp = {'a': [1,1,4,16] + [0 for _ in range(N)],
    't': [1,1,4,16] + [0 for _ in range(N)],
    'g': [1,1,4,15] + [0 for _ in range(N)],
    'c': [1,1,4,14] + [0 for _ in range(N)]
    }

    codons = ['a', 't', 'g', 'c']

    
    
    
    
    
    
    for i in range(4, N+1):
        dp['a'][i] = dp['a'][i-3] * 14 + dp['t'][i-3] * 16 + dp['g'][i-3] * 15 + dp['c'][i-3] * 16
        dp['t'][i] = dp['a'][i-3] * 14 + dp['t'][i-3] * 16 + dp['g'][i-3] * 15 + dp['c'][i-3] * 16
        dp['g'][i] = dp['a'][i-3] * 13 + dp['t'][i-3] * 15 + dp['g'][i-3] * 15 + dp['c'][i-3] * 15
        dp['c'][i] = dp['a'][i-3] * 9 + dp['t'][i-3] * 14 + dp['g'][i-3] * 13 + dp['c'][i-3] * 14

    sum_ = 0
    for x in codons:
        sum_ += dp[x][N] % MOD
    print(sum_ % MOD)
    return

def is_valid(s):
    if s[0:3] == 'AGC' or s[0]+s[2:4] == 'AGC' or s[0:2] + s[3] == 'AGC' or s[1:4] == 'AGC' or s.count('GAC') > 0 or s.count('ACG') > 0:
        return False
    else:
        return True

def main(): 
    N = II()

    if N == 3:
        print(61)
        return
    
    import collections
    dp = collections.defaultdict(int)
    import itertools
    for st in itertools.product('AGCT', repeat=4):
        st = ''.join(st)
        if is_valid(st):
            dp[st] = 1
        else:
            dp[st] = 0

    for i in range(4, N):
        dp2 = collections.defaultdict(int)
        for st in itertools.product('AGCT', repeat=4):
            st = ''.join(st)
            for char in 'AGCT':
                nex = st[1:4] + char
                if is_valid(nex):
                    dp2[nex] = (dp2[nex] + dp[st])%MOD
                else:
                    pass
        dp = dp2

    sum_ = 0
    for st in itertools.product('AGCT', repeat=4):
        st = ''.join(st)
        sum_ = (sum_ + dp[st])%MOD
    print(sum_)

main()

Solution (Python):
n = int(input())
aa = [1]
ac = [1]
ag = [1]
cc = [1]
cg = [1]
ca = [1]
gc = [1]
ga = [1]
gg = [1]
at = [1]
gt = [1]
t = [2]
ta = [1]
tc = [1]
tg = [1]
mod = 10**9 + 7
for i in range(n-2):
    ac.append((ca[i]+ta[i]+aa[i])%mod)
    ag.append((ca[i]+ga[i]+ta[i]+aa[i])%mod)
    cg.append((cc[i]+gc[i]+tc[i])%mod)
    aa.append((ca[i]+aa[i]+ga[i]+ta[i])%mod)
    cc.append((ac[i]+cc[i]+gc[i]+tc[i])%mod)
    ca.append((ac[i]+cc[i]+gc[i]+tc[i])%mod)
    if i > 0:
        gc.append((cg[i]+gg[i]+tg[i]-ag[i-1]-at[i-1])%mod)
    else:
        gc.append((cg[i]+gg[i]+tg[i])%mod)
    ga.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    gg.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    at.append((ca[i]+ga[i]+ta[i]+aa[i])%mod)
    gt.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    t.append((ac[i]+cc[i]+gc[i]+tc[i]+t[i]+at[i]+gt[i])%mod)
    ta.append(t[i]+at[i]+gt[i])
    if i > 0:
        tc.append(t[i]+at[i]+gt[i]-ag[i-1])
    else:
        tc.append(t[i]+at[i]+gt[i])
    tg.append(t[i]+at[i]+gt[i])
ans = 0
ans = (aa[n-2]+ac[n-2]+ag[n-2]+cc[n-2]+cg[n-2]+ca[n-2]+gc[n-2]+ga[n-2]+gg[n-2]+t[n-2]+ta[n-2]+tc[n-2]+tg[n-2]+at[n-2]+gt[n-2])%mod
print(ans)

Solution (Python):
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    n = I()


    def ok(last, c):
        last_plus = last + c
        if 'agc' in last_plus:
            return 0
        for i in range(len(last_plus)-1):
            tmp = list(last_plus)
            tmp[i], tmp[i+1] = tmp[i+1], tmp[i]
            if 'agc' in ''.join(tmp):
                return 0
        return 1



    D = [defaultdict(int) for _ in range(n+1)]
    D[0][''] = 1


    for i in range(n):
        for k, v in D[i].items():
            for c in 'acgt':
                if ok(k, c):
                    D[i+1][(k + c)[-3:]] += v
                    D[i + 1][(k + c)[-3:]] %= mod
    return sum(D[n].values()) % mod





print(main())

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



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

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

def rec(cur, s):
    if s in memo[cur]:
        return memo[cur][s]
    if cur==N:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(s+c):
            ret = (ret + rec(cur+1, s[-2:]+c))%mod
    memo[cur][s] = ret
    return ret

print(rec(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())
mod = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(n)]


dp[0] = [1, 1, 1, 1]
dp[1] = [4, 4, 4, 4]


for i in range(2, n):
    if i == 2:
        dp[i][0] = dp[i - 1][0] * 4
        dp[i][1] = dp[i - 1][1] * 4 - 2
        dp[i][2] = dp[i - 1][2] * 4 - 1
        dp[i][3] = dp[i - 1][3] * 4
    else:
        dp[i][0] = sum(dp[i - 1])
        
        dp[i][1] = sum(dp[i - 1]) - dp[i - 2][0] - dp[i - 2][2] - dp[i - 3][0] * 3
        
        dp[i][2] = sum(dp[i - 1]) - dp[i - 2][0] + dp[i - 3][2]
        dp[i][3] = sum(dp[i - 1])


print(sum(dp[n - 1]) % mod)

Solution (Python):
from itertools import product
from functools import lru_cache
n = int(input())
mod = 10**9+7
condition = True

@lru_cache(64*n)
def func(tpl, count) :
    if tpl in (("A","G","C"), ("A","C","G"), ("G","A","C")) :
        return 0
    if count :
        count -= 1
        if tpl[1:] == ("A","G") :
            return sum(func(("A","G",c), count) for c in "AGT")%mod
        if tpl[1:] == ("A","C") :
            return sum(func(("A","C",c), count) for c in "ACT")%mod
        if tpl[1:] == ("G","A") :
            return sum(func(("G","A",c), count) for c in "AGT")%mod
        if tpl[:2] == ("A","G") :
            return sum(func(tpl[1:]+(c,), count) for c in "AGT")%mod
        if tpl[0]+tpl[2] == "AG" :
            return sum(func(tpl[1:]+(c,), count) for c in "AGT")%mod
        return sum(func(tpl[1:]+(c,), count) for c in "ACGT")%mod
    return 1

ans = 0
for firstthree in product("ACGT", repeat=3) :
    ans = (ans+func(firstthree, n-3))%mod
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 j 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[j][k][l][m+1] %= 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 re

N = int(input())

memo = dict()


def is_agc(text):
    if re.match("(.agc|.acg|.gac|a.gc|ag.c)", text):
        return True
    return False


def dfs(s, m):
    if (s, m) in memo:
        return memo[(s, m)]
    if m == N:
        return 1

    count = 0
    for c in "acgt":
        t = s + c
        if is_agc(t):
            continue
        count += dfs(t[-3:], m+1)

    
    memo[(s, m)] = count % (10**9+7)
    return memo[(s, m)]


print(dfs("ttt", 0))

Solution (Python):
n, MOD = int(input()), 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], t[i-1] = t[i-1], t[i]
        if "".join(t).count("AGC") != 0:
            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):
def main():
    
    
    from collections import defaultdict
    N = int(input())
    mod = 10**9+7
    
    A = [defaultdict(int) for i in range(N)]
    helix = ["A","T","C","G"]
    out = ["AGC","GAC","ACG"]
    for i in helix:
        for j in helix:
            for k in helix:
                s = i+j+k
                if not s in out:
                    A[2][s] = 1
    for n in range(N-3):
        for i in helix:
            for j in helix:
                for k in helix:
                    m = n+3
                    s = i+j+k
                    if not s in out:
                        for l in helix:
                            t = l+i+j
                            if (not t in helix) and (not (k=="C" and (l+j=="AG" or i+j=="GA" or l+i=="AG"))) and (not (k=="G" and (i+j=="AC"))):
                                A[m][s] += A[m-1][t]
                                A[m][s] %= mod
    answer = 0
    for i in helix:
        for j in helix:
            for k in helix:
                s = i+j+k
                if not s in out:
                    answer += A[N-1][s]
                    answer %= mod
    print(answer)
main()

Solution (Python):
from collections import defaultdict

n = int(input())
mod = 10**9 + 7
DP = [defaultdict(int) for _ in range(n+1)]
DP[0]['TTT'] = 1

for length in range(n):
    for seq, count in DP[length].items():

        if seq[1:] in ['AG', 'GA'] or seq[:2] == 'AG' or seq[0]+seq[2] == 'AG':
            for ns in 'AGT':
                new_seq = seq[1:] + ns
                DP[length+1][new_seq] += count
                DP[length + 1][new_seq] %= mod

        elif seq[1:] == 'AC':
            for ns in 'ACT':
                new_seq = seq[1:] + ns
                DP[length + 1][new_seq] += count
                DP[length + 1][new_seq] %= mod

        else:
            for ns in 'ACGT':
                new_seq = seq[1:] + ns
                DP[length + 1][new_seq] += count
                DP[length + 1][new_seq] %= mod

ans = sum(DP[n].values()) % mod
print(ans)

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


N = int(input())
mod=1e+9 +7
dp = [[[[0]*4 for i in range(4)] for j in range(4)] for k in range(N+1)]
dp[0][3][3][3]=1
for len in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[len][c1][c2][c3] == 0: continue
                for a in range(4):
                    if c2==0 and c3==1 and a==2: continue
                    if c2==0 and c3==2 and a==1: continue
                    if c2==1 and c3==0 and a==2: continue
                    if c1==0 and c3==1 and a==2: continue
                    if c1==0 and c2==1 and a==2: continue
                    dp[len+1][c2][c3][a]+=dp[len][c1][c2][c3]
                    dp[len+1][c2][c3][a]%=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(int(ans))

Solution (Python):
MOD = 10 ** 9 + 7
n = int(input())
memo = [dict() 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):
def main():
    N = int(input())
    div = pow(10, 9) + 7
    
    
    
    
    
    
    three = [""]
    for _ in range(3):
        temp = []
        for s in three:
            for c in "ACGT":
                temp.append(s + c)
        three = temp
    d = dict()
    for s in three:
        if s not in ["AGC", "GAC", "ACG"]:
            d[s] = 1
    for _ in range(3, N):
        temp = dict()
        for s in d:
            NotAllowed = forbidden(s)
            for c in "ACGT":
                if c not in NotAllowed:
                    temp[s[1:]+c] = temp.get(s[1:]+c, 0) + d[s]
        d = temp
    ans = 0
    for s in d:
        ans += d[s] % div
    return ans % div

def forbidden(s):
    if s[1:] == "AG" or s[1:]=="GA" or s[:2] == "AG" or (s[0]== "A" and s[2]== "G"):
        return ["C"]
    if s[1:] == "AC":
        return ["G"]
    else:
        return []


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

Solution (Python):
import copy

def ok(len_4):    
    for i in range(3):
        alpha = list(copy.deepcopy(len_4))
        alpha[i], alpha[i + 1] = alpha[i + 1], alpha[i]
        if "AGC" in "".join(alpha):
            return False
    if "AGC"in len_4:
        return False
    return True


def check(len_3, n):
    if n == N:
        return 1
    if len_3 in memo[n]:
        return memo[n][len_3]
    ret = 0
    for alpha in "AGCT":
        t = len_3 + alpha
        if ok(t):
            temp = check(t[1:], n + 1)
            memo[n + 1][t[1:]] = temp % mod
            ret += temp % mod
    return ret % mod


mod = (10 ** 9) + 7
N = int(input())
memo = [{} for _ in range(N + 1)]
ans = check("TTT", 0)
print(ans)

Solution (Python):
n = int(input())
d = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
law = 10 ** 9 + 7

dp = {'TTT': 1}
def check(s):
    if 'AGC' in s or 'GAC' in s or 'ACG' in s:
        return False
    if s[0] + s[2:] == 'AGC':
        return False
    if s[:2] + s[3] == 'AGC':
        return False
    return True
for _ in range(n):
    
    new = {}
    for i, c in dp.items():
        for add in 'ACGT':
            s = i + add
            if check(s):
                s = s[1:]
                if s not in new:
                    new[s] = c % law
                else:
                    new[s] += c
                    new[s] %= law
    dp = new
print(sum(dp.values()) % law)

Solution (Python):
N = int(input())
MOD = int(1e9+7)
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]

dp[0][0][0][0] = 1
for n in range(N):
    for i in range(4):
        for j in range(4):
            if dp[n][i][j] == 0:
                continue
            for k in range(4):
                for a in range(4):
                    if j == 1 and i == 2 and a == 3: 
                        continue
                    if j == 2 and i == 1 and a == 3: 
                        continue
                    if j == 1 and i == 3 and a == 2: 
                        continue
                    if k == 1 and i == 2 and a == 3: 
                        continue
                    if k == 1 and j == 2 and a == 3: 
                        continue
                    dp[n+1][a][i][j] += dp[n][i][j][k]
                    dp[n + 1][a][i][j] %= MOD
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= MOD
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


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

dp = [[[0]*4 for j in range(4)] for i in range(4)]
dp[3][3][3] = 1
for _ in range(n):
    ndp = [[[0]*4 for j in range(4)] for i in range(4)]

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


print(sum(sum(sum(j) for j in i) for i in dp)%MOD)

Solution (Python):
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v
    return [nlist(n[1:], v) for _ in range(n[0])]
import random


def main():
    N = input(int)

    dp = nlist([N + 1, 5, 5, 5], 0)
    dp[0][0][0][0] = 1
    for n in range(1, N + 1):
        for i in range(5):  
            for j in range(5):  
                for k in range(5):  
                    for l in range(1, 5):  
                        if j == 1 and k == 3 and l == 2: continue
                        if j == 3 and k == 1 and l == 2: continue
                        if j == 1 and k == 2 and l == 3: continue
                        if i == 1 and k == 3 and l == 2: continue
                        if i == 1 and j == 3 and l == 2: continue
                        dp[n][j][k][l] += dp[n - 1][i][j][k]
                        dp[n][j][k][l] %= MOD
    ans = 0
    for i in range(1, 5):
        for j in range(1, 5):
            for k in range(1, 5):
                ans += dp[N][i][j][k]
                ans %= MOD
    print(ans)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
mod=1000000007

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

@lru_cache(maxsize=None)
def dfs(cur,last3):
    if cur==0:
        return 1
    ret=0
    for c in 'ACGT':
        if judge(last3+c):
            ret+=dfs(cur-1,last3[1:]+c)
            ret%=mod
    return ret

n=int(input())
print(dfs(n,'TTT'))

Solution (Python):



from collections import deque, defaultdict
import copy
import bisect

import math
import heapq


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

N = int(input())

num = [4,4,4,4,4,4,4,4,3,4,4,4,3,4,3,4,1,1,1]

for i in range(N - 3):
	num2 = [0]*19
	num2[0] = num[0] + num[1] + num[2] + num[3]
	num2[4] = num2[0]
	num2[5] = num2[0] - num[17]
	num2[6] = num2[0]
	num2[1] = num[4] + num[7] + num[10] + num[13]
	num2[7] = num2[1]
	num2[8] = num2[1] - num[13]
	num2[9] = num2[1]
	num2[2] = num[5] + num[8] + num[11] + num[14]
	num2[10] = num2[2]
	num2[11] = num2[2]
	num2[12] = num2[2] - num[8]
	num2[3] = num[6] + num[9] + num[12] + num[15]
	num2[13] = num2[3]
	num2[14] = num2[3] - num[9] - num[16] - num[18]
	num2[15] = num2[3]
	num2[16] = num[9]
	num2[17] = num[9]
	num2[18] = num[1]
	for i in range(19):
		num2[i] = num2[i] % 1000000007
	num = copy.deepcopy(num2)

print(sum(num[0:16]) % 1000000007)

Solution (Python):
import numpy as np
n = int(input())
A_1 = np.zeros((4,4), dtype='int64')
A_2 = np.ones((4,4), dtype='int64')
B = np.ones((4,4), dtype='int64')
for _ in range(n-2):
    A_3 = np.dot(B, A_2).T
    A_3 %= 10**9+7
    A_3[2,1] -= A_2[0,2]+A_1[0,2]+A_1[0,3]
    A_3[1,2] -= A_2[0,1]
    A_3[0,1] -= A_2[2,0]
    A_3[3,1] -= A_1[0,2]
    A_1, A_2 = A_2, A_3
print(np.sum(A_3)%(10**9+7))

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



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


 

for i in range(n):
    
    for j in range(4):
        
        for k in range(4):
            
            if dp[i][j][k] == 0:
                continue
            
            for l in range(4):
                
                for a in range(4):
                    
 
                    
                    if a == 2 and j == 1 and k == 0:continue
                    
                    if a == 2 and j == 0 and k == 1:continue
                    
                    if a == 1 and j == 2 and k == 0:continue
                    
                    if a == 2 and j == 1 and l == 0:continue
                    
                    if a == 2 and k == 1 and l == 0:continue
 
                    
                    dp[i+1][a][j][k] += dp[i][j][k][l]
                    dp[i+1][a][j][k] %= mod
 
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            
            ans += dp[n][j][k][l]
            ans %= mod
print(ans)

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

k = 2
f = [1,4,16]
r = [{"AG":0,"GA":0,"AC":0,"AGG":0,"A":0,"G":0},
     {"AG":0,"GA":0,"AC":0,"AGG":0,"A":1,"G":1},
     {"AG":1,"GA":1,"AC":1,"AGG":0,"A":4,"G":4,"ATG":0,"AGT":0,"AT":1}]
while k < n:
    k += 1
    r.append({})
    r[k]["AC"] = r[k-1]["A"]-r[k-1]["GA"]
    r[k]["GA"] = r[k-1]["G"]
    r[k]["AG"] = r[k-1]["A"]
    r[k]["AGG"] = r[k-1]["AG"]
    r[k]["A"] = f[k-1]
    r[k]["G"] = f[k-1]-r[k-1]["AC"]
    r[k]["ATG"] = r[k-1]["AT"]
    r[k]["AT"] = r[k-1]["A"]
    r[k]["AGT"] = r[k-1]["AG"]
    f.append(0)
    f[k] = f[k-1]*4 - r[k-1]["AG"] - r[k-1]["GA"] - r[k-1]["AC"] - r[k-1]["AGG"] - r[k-1]["ATG"] - r[k-1]["AGT"]
print(f[n]%(10**9+7))

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

dp[0] = [1,1,1,1]
dp[1] = [4,4,4,4]


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

Solution (Python):

import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    MOD = 10**9 + 7
    
    
    

    
    dp =[1] * 64
    A = 0
    C = 1
    G = 2
    T = 3
    
    dp[G * 4**2 + A * 4**1 + C * 4**0] = 0
    
    dp[A * 4**2 + C * 4**1 + G * 4**0] = 0
    
    dp[A * 4**2 + G * 4**1 + C * 4**0] = 0

    N = II()
    pre = dp
    for _ in range(N-3):
        
        pre = dp
        dp = [0] * 64
        for i in range(64):
            
            
            
            
            for j in range(4):
                
                if i % 16 == G*4+A and j == C:
                    
                    continue
                
                elif i % 16 == A*4+C and j == G:
                    
                    continue
                
                elif i % 16 == A*4+G and j== C:
                    continue 
                
                elif i // 4 == A*4+G and j == C:
                    continue
                
                elif i//16 == A and i%4 ==G and j == C:
                    continue

                dp[i%16*4+j] += pre[i]
        dp = list(map(lambda x:x%MOD, dp))

        
        

    print(sum(dp)%MOD)

    






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

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 "ACGT":
        if ok(last3+c):
            ret=(ret+dfs(cur+1,last3[1:]+c))%mod
    memo[cur][last3]=ret
    return ret
dfs(0,"TTT")
print(memo[0]["TTT"])

Solution (Python):
import copy
def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]
    ans = sum(dp_list)%mod

print(ans)

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

if __name__ == "__main__":
    n, mod = int(input()), 10 ** 9 + 7
    memo = [{} for i in range(n + 1)]
    print(dfs(0, "TTT"))

Solution (Python):

N = int(input())

now = 4 

lis = [1] * (4**3)

lis[2 * (4**1) + 1] = 0 
lis[1 * (4**1) + 2] = 0 
lis[2 * (4**2) + 1] = 0 


while now <= N:

    nlis = [0] * (4**3)
    
    for i in range(4**3):

        

        nlis[ ( i * 4 ) % 64 ] += lis[i]

        

        nlis[ (i * 4) % 64 + 3 ] += lis[i]

        

        if i % 16 != 1:
            nlis[ (i * 4) % 64 + 2 ] += lis[i]

        

        if (i % 16 not in [2,8] ) and (not( i // 16 == 0 and i % 4 == 2)) and (not(i // 16 == 0 and i // 4 == 2)):

            nlis[ (i * 4) % 64 + 1 ] += lis[i]

    for j in range(4**3):

        lis[j] = nlis[j] % (10 ** 9 + 7)

    
        
    now += 1

print (sum(lis) % (10**9 + 7))