Problem:
 Score : 400 points    Problem Statement You are given an integer N . Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7 :   The string does not contain characters other than A , C , G and T .  The string does not contain AGC as a substring.  The condition above cannot be violated by swapping two adjacent characters once.       Notes A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T .  For example, the substrings of ATCODER include TCO , AT , CODER , ATCODER and (the empty string), but not AC .      Constraints  3 \leq N \leq 100         Input Input is given from Standard Input in the following format:  N       Output Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7 .        Sample Input 1 3      Sample Output 1 61  There are 4^3 = 64 strings of length 3 that do not contain characters other than A , C , G and T . Among them, only AGC , ACG and GAC violate the condition, so the answer is 64 - 3 = 61 .       Sample Input 2 4      Sample Output 2 230       Sample Input 3 100      Sample Output 3 388130742  Be sure to print the number of strings modulo 10^9+7 .

Solution (Python):
n = int(input()); x = 0
dp = [[[[0]*4 for q in range(4)] for p in range(4)] for i in range(n-2)]
ng = ["012", "021", "102", "0112", "0132", "0312"]
for p in range(4):
    for q in range(4):
        for r in range(4):
            if str(p)+str(q)+str(r) not in ng:
                dp[0][p][q][r] += 1
for i in range(n-3):
    for p in range(4):
        for q in range(4):
            for r in range(4):
                for s in range(4):
                    if str(p)+str(q)+str(r)+str(s) not in ng and str(q)+str(r)+str(s) not in ng:
                        dp[i+1][q][r][s] += dp[i][p][q][r]
for p in range(4):
    for q in range(4):
        for r in range(4):
            x = (x+dp[-1][p][q][r])%(10**9+7)
print(x)

Solution (Python):
from copy import deepcopy

def getval():
    n = int(input())
    return n

def main(n):
    mod = 10**9 + 7
    
    dp = [[[1 for i in range(4)] for i in range(4)] for i in range(4)]
    dp[0][2][1] = 0
    dp[0][1][2] = 0
    dp[2][0][1] = 0

    def pow4(arr):
        ans = 0
        for i in range(4):
            ans += arr[i]*(4**(3-i))
        return ans 

    p = []
    for i in range(4):
        p.append(pow4([0,2,1,i]))
        p.append(pow4([0,1,2,i]))
        p.append(pow4([2,0,1,i]))
        p.append(pow4([i,0,2,1]))
        p.append(pow4([i,0,1,2]))
        p.append(pow4([i,2,0,1]))
        p.append(pow4([0,i,2,1]))
        p.append(pow4([0,2,i,1]))

    it1 = iter(p)
    it2 = iter(p)
    co = 0
    di = dict(zip(it1,it2))
    for i in range(n-3):
        temp = [[[0 for i in range(4)] for i in range(4)] for i in range(4)]
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    for d in range(4):
                        if pow4([a,b,c,d]) in di:
                            temp[b][c][d] += 0
                        else:
                            temp[b][c][d] += dp[a][b][c]
                            temp[b][c][d] %= mod
        dp = temp

    ans = 0
    if n>=4:
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    ans += temp[i][j][k]
    elif n==3:
        ans = 61
    ans %= mod
    print(ans)

if __name__=="__main__":
    n = getval()
    main(n)

Solution (Python):












import sys
readline = sys.stdin.readline

N = int(readline())
DIV = 10 ** 9 + 7



dp = [[[[0] * 4 for b in range(4)] for a in range(4)] for i in range(N)]

C = {0:"A", 1:"G", 2:"C", 3:"T", 4:""}
NG = set(["AGC","ACG","GAC","AGGC","ACGC","AGAC","AGGC","ATGC","AGTC"])

def check_ok(i,j,k,l = 4):
  if (C[i] + C[j] + C[k] + C[l]) in NG:
    return False
  return True


for i in range(4):
  for j in range(4):
    for k in range(4):
      if check_ok(i,j,k):
        dp[2][i][j][k] += 1


for i in range(2, len(dp) - 1):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        for k in range(4):
          if check_ok(a,b,c,k) and check_ok(b,c,k):
            dp[i + 1][b][c][k] += dp[i][a][b][c]
            dp[i + 1][b][c][k] %= DIV
        
ans = 0
for a in range(4):
  for b in range(4):
    for c in range(4):
      ans += dp[-1][a][b][c]
      ans %= DIV
      
print(ans)

Solution (Python):
import itertools

s=dict()
for i in itertools.product(["A","C","G","T"], repeat=3):
    s[i]=1
s[("A","G","C")]=0
s[("G","A","C")]=0
s[("A","C","G")]=0

n=int(input())

mod=10**9+7
nn=3
t=dict()
while nn<n:
    for i in itertools.product(["A","C","G","T"], repeat=3):
        t[i]=0
    nn+=1
    for ky in s.keys():
        if ky[0]=="G" and ky[1]=="C":
            t[("A",ky[0],ky[1])]=0
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[0]=="A" and ky[1]=="C":
            t[("A",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]=0
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[0]=="C" and ky[1]=="G":
            t[("A",ky[0],ky[1])]=0
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[0]=="G" and ky[2]=="C":
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[1]=="G" and ky[2]=="C":
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        else:
            t[("A",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
    for ky in s.keys():
        s[ky]=t[ky]           

icnt=0
for i in s.values():
    icnt=(icnt+i)%mod
print(icnt)

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

mod = 10**9 + 7

a = [0]*n
c = [0]*n
g = [0]*n
t = [0]*n

a[0] = c[0] = g[0] = t[0] = 1
a[1] = c[1] = g[1] = t[1] = 4
a[2], c[2], g[2], t[2] = 16, 14, 15, 16

for i in range(3, n):
    v = (a[i-1] + c[i-1] + g[i-1] + t[i-1]) % mod
    a[i] = v
    c[i] = (v - a[i-2] - g[i-2] - 3*a[i-3]) % mod
    g[i] = (v - a[i-2] + g[i-3]) % mod
    t[i] = v
print((a[n-1] + c[n-1] + g[n-1] + t[n-1]) % mod)

Solution (Python):









def solve(N):
    mod = 10 ** 9 + 7
    dp = [{} for _ in range(N + 1)]
    dp[0].setdefault('TTT', 1)

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

    for i in range(1, N + 1):
        for last3, count in dp[i - 1].items():
            for c in 'AGCT':
                if check(last3 + c):
                    new_last3 = last3[1:] + c
                    dp[i].setdefault(last3[1:] + c, 0)
                    dp[i][new_last3] = (dp[i][new_last3] + count) % mod

    print(sum(dp[-1].values()) % mod)


if __name__ == '__main__':
    N = int(input())
    solve(N)

Solution (Python):









def solve(N):
    mod = 10 ** 9 + 7
    memo = [{} for _ in range(N + 1)]

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

    def dfs(memo, digit, last3):
        
        if last3 in memo[digit]:
            return memo[digit][last3]  
        if digit == 0:
            return 1  
        re = 0
        for c in 'AGCT':
            if check(last3 + c):
                re = (re + dfs(memo, digit - 1, last3[1:] + c)) % mod
        memo[digit][last3] = re
        return re

    print(dfs(memo, N, 'TTT'))  


if __name__ == '__main__':
    N = int(input())
    solve(N)

Solution (Python):


import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())

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

dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = 1
dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = 4

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

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

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

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

                    
                    for l in range(4):
                        new_dp[j][k][l] += num

                    
                    
                    if (i == 0 and j == 2) or (j == 0 and k == 2) or (i == 0 and k == 2) or (j == 2 and k == 0):
                        new_dp[j][k][1] -= num
                    
                    if j == 0 and k == 1:
                        new_dp[j][k][2] -= num

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

        dp = new_dp

    for i in range(4):
        for j in range(4):
            dp[i][j] = sum(dp[i][j]) % mod
    for i in range(4):
        dp[i] = sum(dp[i]) % mod
    print(sum(dp) % mod)

main()

Solution (Python):
from collections import defaultdict
from functools import reduce

def main():
  m = 10 ** 9 + 7
  n = int(input())
  current = defaultdict(int)
  current['TTT'] = 1
  for i in range(n):
    wip = defaultdict(int)

    for c in 'AGCT':
      for k, v in current.items():
        if k + c in ['ATGC', 'AGTC', 'AGGC']:
          continue
        z = k[1:]+c
        if z in ['AGC', 'ACG', 'GAC']:
          continue
        wip[z] = (wip[z] + v) % m

    current = wip
  
  print(reduce(lambda acc, x: (acc + x) % m, wip.values()))

main()

Solution (Python):
def is_ok(s):
    if s[1:] in ['AGC', 'ACG', 'GAC']:
        return False
    if s[0] == 'A' and s[2:] == 'GC':
        return False
    if s[:2] == 'AG' and s[3] == 'C':
        return False
    return True


m = 1000000007

N = int(input())

d = {}
for i in 'ACGT':
    for j in 'ACGT':
        for k in 'ACGT':
            d[i + j + k] = 1
for k in ['AGC', 'ACG', 'GAC']:
    del d[k]

for i in range(N - 3):
    t = {}
    for k in d:
        for i in 'ACGT':
            s = k + i
            if is_ok(s):
                t.setdefault(s[1:], 0)
                t[s[1:]] += d[k]
                t[s[1:]] %= m
    d = t

print(sum(d.values()) % m)

Solution (Python):
N = int(input())
mod = 10**9+7
A = [1]+(N+3)*[0]
G = [1]+(N+3)*[0]
C = [1]+(N+3)*[0]

for n in range(1,N):
  T = (2*A[n-1]+G[n-1]+C[n-1])%mod
  A[n] = T
  G[n] = (T-A[n-2]+G[n-3])%mod
  C[n] = (T-A[n-2]-G[n-2]-3*A[n-3])%mod

print((2*A[N-1]+G[N-1]+C[N-1])%mod)

Solution (Python):
n = int(input())
mod = 10**9+7
A=[1] + [0]*(n+3)
G=[1] + [0]*(n+3)
C=[1] + [0]*(n+3)
for i in range(1,n):
    t=(2*A[i-1]+G[i-1]+C[i-1])%mod
    A[i]=t
    G[i]=(t-A[i-2]+G[i-3])%mod
    C[i]=(t-A[i-2]-G[i-2]-3*A[i-3])%mod
print((2*A[n-1]+G[n-1]+C[n-1])%mod)

Solution (Python):
n = int(input())
mod = 10**9+7
A=[1] + [0]*(n-1)
G=[1] + [0]*(n-1)
T=[1] + [0]*(n-1)
C=[1] + [0]*(n-1)

AG =[0]*n
GA =[0]*n
AC =[0]*n

AGG=[0]*n
AGT=[0]*n
ATG=[0]*n
for i in range(1,n):
    tmp=A[i-1]+G[i-1]+C[i-1]+T[i-1]

    A[i]=tmp%mod
    T[i]=tmp%mod
    G[i]=(tmp - AC[i-1])%mod
    C[i]=(tmp -AG[i-1]-GA[i-1]-AGG[i-1] -AGT[i-1]-ATG[i-1])%mod

    AG[i]=A[i-1]
    GA[i]=G[i-1]
    AC[i]=(A[i-1]-GA[i-1])%mod

    AGG[i]=AG[i-1]
    AGT[i]=AG[i-1]
    ATG[i]=A[i-2]


print((A[-1]+G[-1]+C[-1]+T[-1])%mod)

Solution (Python):
from collections import defaultdict
N=int(input())
A = {}
B = {}
for a in "ATGC":
    for b in "ATGC":
        for c in "ATGC":
            if a+b+c not in ["AGC", "ACG", "GAC"]:
                B[a+b+c] = 1
X=set()
for a in "ATGC":
    for b in "ATGC":
        for c in "ATGC":      
            for d in "ATGC":
                s=a+b+c+d
                t=b+a+c+d
                u=a+c+b+d
                v=a+b+d+c
                if any(["AGC" in x for x in [s,t,u,v]]):
                    X.add(s)

for _ in range(N-3):
    A = B
    B = defaultdict(int)
    for k in A:
        for l in "ATGC":
            if k+l not in X:
                B[k[1:]+l] += A[k]
    
print(sum(B.values())%(10**9+7))

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N):
    M = 10**9 + 7

    def gp(n):
        prohibit = []
        for c in product('AGCT', repeat=n):
            c = ''.join(c)
            if 'AGC' in c:
                prohibit.append(c)

            for i in range(n-1):
                j = i+1
                l = list(c)
                l[i], l[j] = l[j], l[i]
                if 'AGC' in ''.join(l):
                    prohibit.append(c)
        return set(prohibit)

    p3 = gp(3)
    p4 = gp(4)



    memo = {}
    for c in product('AGCT', repeat=3):
        c = ''.join(c)
        if c not in p3:
            memo[c] = 1

    for _ in range(N-3):
        nm = Counter()
        for c in 'AGCT':
            for k, v in memo.items():
                kk = k + c
                if kk not in p4:
                    nm[kk[1:]] += v
                    nm[kk[1:]] %= M

        memo = nm


    return sum(memo.values()) % M


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


if __name__ == '__main__':
    main()

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

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i==0 and j==1 and k==2) or (i==0 and j==2 and k==1) or (i==2 and j==0 and k==1):
                pass
            else:
                dp[3][i][j][k] = 1

for a in range(3,n):
    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):
                        if l==2:
                            continue
                    if (j==0 and k==2):
                        if l==1:
                            continue
                    if (j==2 and k==0):
                        if l==1:
                            continue

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

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


DP = [[[[0 for _ in range(4)] for _ in range(4)]
       for _ in range(4)] for _ in range(N + 1)]





for a in range(4):
    for b in range(4):
        for c in range(4):
            if (a, b, c) not in ((1, 2, 3), (2, 1, 3), (1, 3, 2)):
                DP[3][a][b][c] = 1



for i in range(4, N + 1):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                
                DP[i][b][c][0] += DP[i - 1][a][b][c]
                DP[i][b][c][1] += DP[i - 1][a][b][c]
                
                if (b, c) != (1, 3):
                    DP[i][b][c][2] += DP[i - 1][a][b][c]
                
                if (b, c) != (1, 2) and (b, c) != (2, 1) and (a, c) != (1, 2) and (a, b) != (1, 2):
                    DP[i][b][c][3] += DP[i - 1][a][b][c]

ans = 0

for a in range(4):
    for b in range(4):
        for c in range(4):
            ans += DP[N][a][b][c]
            ans %= MOD

print(ans % MOD)

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


DP = [[[[0 for _ in range(4)] for _ in range(4)]
       for _ in range(4)] for _ in range(N + 1)]





for a in range(4):
    for b in range(4):
        for c in range(4):
            if (a, b, c) not in ((1, 2, 3), (2, 1, 3), (1, 3, 2)):
                DP[3][a][b][c] = 1



for i in range(4, N + 1):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                
                DP[i][b][c][0] += DP[i - 1][a][b][c]
                DP[i][b][c][1] += DP[i - 1][a][b][c]
                
                if (b, c) != (1, 3):
                    DP[i][b][c][2] += DP[i - 1][a][b][c]
                
                if (b, c) != (1, 2) and (b, c) != (2, 1) and (a, c) != (1, 2) and (a, b) != (1, 2):
                    DP[i][b][c][3] += DP[i - 1][a][b][c]

ans = 0

for a in range(4):
    for b in range(4):
        for c in range(4):
            ans += DP[N][a][b][c]
            ans %= MOD

print(ans % MOD)

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9+7

N = int(input())

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

def ok(last4):
    if "AGC" in last4 or "GAC" in last4 or "ACG" in last4 or last4 == "AGGC" or last4 == "ATGC" or last4 == "AGGC" or last4 == "AGTC":
        return False
    else:
        return True

def DFS(now,last3):
    if last3 in memo[now]:
        return memo[now][last3] 
    if now == N:
        return 1
    ret = 0
    for c in "AGCT":
        last4 = last3 + c
        if ok(last4):
            ret += DFS(now+1,last4[1:])
            ret %= MOD
    memo[now][last3] = ret
    return ret

print(DFS(0,"TTT"))

Solution (Python):
n = int(input())
mod = pow(10, 9) + 7
alph = list("AGCT")
ng1 = [list("AGC"), list("ACG"), list("GAC")]
dp = [0] * 64
for i in range(4):
    for j in range(4):
        for k in range(4):
            if not [alph[i], alph[j], alph[k]] in ng1:
                dp[16 * i + 4 * j + k] = 1
for _ in range(n - 3):
    dp0 = [0] * 64
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if not [alph[j], alph[k], alph[l]] in ng1:
                        if not ([alph[i], alph[l]] == list("AC") and (alph[j] == "G" or alph[k] == "G")):
                            dp0[16 * j + 4 * k + l] += dp[16 * i + 4 * j + k]
                            dp0[16 * j + 4 * k + l] %= mod
    for i in range(64):
        dp[i] = dp0[i]
ans = sum(dp) % mod
print(ans)

Solution (Python):



import itertools
L = [''.join(i) for i in itertools.product('0123', repeat=3)]
l = len(L)

mod = 10**9+7

AGC = '021'
ACG = '012'
GAC = '201'
nc3 = set([AGC, ACG, GAC])

AGGC = '0221'
AGTC = '0231'
ATGC = '0321'
nc4 = set([AGGC, AGTC, ATGC])

n = int(input())
dp = [[0]*l for _ in range(n+1)]
for i in L:
    if i in nc3: continue
    dp[3][int(i, 4)] = 1

for i in range(3, n):
    for jl in L:
        for k in "0123":
            nxt = jl[1:] + k
            if nxt in nc3: continue
            if jl+k in nc4: continue
            dp[i+1][int(nxt, 4)] += dp[i][int(jl, 4)]
print(sum(dp[n])%mod)

Solution (Python):
import itertools
L = [''.join(i) for i in itertools.product('0123', repeat=3)]
l = len(L)

mod = 10**9+7

AGC = '021'
ACG = '012'
GAC = '201'
nc3 = set([AGC, ACG, GAC])

AGGC = '0221'
AGTC = '0231'
ATGC = '0321'
nc4 = set([AGGC, AGTC, ATGC])

n = int(input())
dp = [[0]*l for _ in range(n+1)]
for i in L:
  if i in nc3: continue
  dp[3][int(i, 4)] = 1

for i in range(3, n):
  for jl in L:
    for k in "0123":
      nxt = jl[1:] + k
      if nxt in nc3: continue
      if jl+k in nc4: continue
      dp[i+1][int(nxt, 4)] += dp[i][int(jl, 4)]
print(sum(dp[n])%mod)

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

DP = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N)]

Banned = {(1,2,3),(2,1,3),(1,3,2)}

for a in range(4):
  for b in range(4):
    for c in range(4):
      if (a,b,c) not in Banned:
        DP[2][a][b][c] = 1
      

for i in range(3,N):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        DP[i][b][c][0] += DP[i-1][a][b][c]
        DP[i][b][c][1] += DP[i-1][a][b][c]
        if not ((b,c) == (1,2) or (b,c) == (2,1) or (a,c) == (1,2) or (a,b) == (1,2)):
          DP[i][b][c][3] += DP[i-1][a][b][c]
        if not (b,c) == (1,3):
          DP[i][b][c][2] += DP[i-1][a][b][c]

ans = 0
for a in range(4):
  for b in range(4):
    for c in range(4):   
      ans += DP[N-1][a][b][c]
print(ans % MOD)

Solution (Python):
N = int(input())
mod = int(1e+9 + 7)

options = ["A", "C", "G", "T"]
dp = [{options[i] + options[j] + options[k]: 0 for i in range(len(options)) for j in range(len(options)) for k in range(len(options))} for _ in range(N+1)]
keys = list(dp[0].keys())

dp[0]["TTT"] = 1

for i in range(N):
    for key in keys:
        for option in options:
            if key[1] == "A" and key[2] == "G" and option == "C":
                continue
            if key[0] == "A" and key[2] == "G" and option == "C":
                continue
            if key[1] == "G" and key[2] == "A" and option == "C":
                continue
            if key[1] == "A" and key[2] == "C" and option == "G":
                continue
            if key[0] == "A" and key[1] == "G" and option == "C":
                continue
            
            dp[i+1][key[1:3] + option] += dp[i][key]
            dp[i+1][key[1:3] + option] = dp[i+1][key[1:3] + option] % mod

print(sum(list(dp[-1].values()))%mod)

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    dp = [1]*(4**3)
    dp[0*16+2*4+1] = 0
    dp[2*16+0*4+1] = 0
    dp[0*16+1*4+2] = 0
    for _ in range(n-3):
        ndp = [0]*(4**3)
        for i in range(4):
            ndp[0*16+2*4+1] -= dp[i*16+0*4+2]
            ndp[i*16+2*4+1] -= dp[0*16+i*4+2]
            ndp[2*16+i*4+1] -= dp[0*16+2*4+i]
        ndp[0*16+2*4+1] += dp[0*16+0*4+2]
        ndp[2*16+2*4+1] += dp[0*16+2*4+2]
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        ndp[i*16+j*4+k] += dp[l*16+i*4+j]
        
        ndp[2*16+0*4+1] = 0
        ndp[0*16+1*4+2] = 0
        for i in range(4**3):
            ndp[i] %= mod
        dp = ndp*1


    ans = 0
    for i in dp:
        ans += i
    print(ans%mod)
    return None

if __name__ == '__main__':
    main()

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

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

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

print(dfs(0,"TTT"))

Solution (Python):
N=int(input())
mod=10**9+7
DP=[[0]*256 for i in range(N+2)]
NO=[False]*256
S='AGCT'
T=0
for a in range(4):
  for b in range(4):
    for c in range(4):
      for d in range(4):
        T=list(S[a]+S[b]+S[c]+S[d])
        NO[a*64+b*16+c*4+d]=('AGC' in ''.join(T))
        for l in range(3):
          T[l],T[l+1]=T[l+1],T[l]
          NO[a*64+b*16+c*4+d]|=('AGC' in ''.join(T))
          T[l],T[l+1]=T[l+1],T[l]
DP[0][-1]=1
for i in range(N+1):
  for j in range(256):
    if NO[j]:
      DP[i][j]=0
      continue
    for k in range(4):
      DP[i+1][(j*4+k)&255]=(DP[i+1][(j*4+k)&255]+DP[i][j])%mod
P=0
for i in range(256):
  P+=DP[N][i]
print(P%mod)

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n = getN()
    dp = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    
    

    for i in range(n):
        tmp = [0] * 12

        tmp[3] = dp[1] + dp[6] + dp[7]
        tmp[4] = dp[1]
        tmp[5] = dp[1] + dp[6] + dp[7]
        tmp[6] = dp[2] + dp[8] + dp[10]
        tmp[7] = dp[3]
        tmp[8] = dp[3]
        tmp[9] = dp[3]
        tmp[10] = dp[5]
        tmp[11] = dp[3] + dp[4] + dp[6] + dp[7] + dp[8] + dp[9] + dp[10] + dp[11] * 4
        tmp[1] = dp[0] + dp[1] + dp[4] + dp[5] + dp[6] + dp[7] + dp[9]
        tmp[2] = dp[0] + dp[2] + dp[8] + dp[9] + dp[10]
        tmp[0] = dp[0] * 2 + dp[2] * 2 + dp[4] * 2 + dp[5] * 2 + dp[8] + dp[9] + dp[10]

        dp = [x % MOD for x in tmp]
    
    
    
    print(sum(dp[:-1]) % MOD)

def gu(n=5):
    ban = ["AGC", "ACG", "GAC", "AGAC", "AGGC", "AGTC", "ATGC"]
    select = ["A", "G", "C", "T"]
    ans = 0
    space = [0] * 11
    sp = ["ATG", "AGT", "AGG", "AGA", "GA", "AT", "AC", "AG", "G", "A"]
    for i in range(4 ** n):
        lis = []
        for j in range(n):
            lis.append(select[i%4])
            i //= 4
        ji = "".join(lis)
        fl = True
        
        for b in ban:
            if b in ji:
                fl = False
        if fl:
            ans += 1
            en = False
            for dd, spp in enumerate(sp):
                if ji.endswith(spp):
                    space[dd] += 1
                    en = True
                    break
            if not en:
                space[-1] += 1

    space.reverse()

    print(space)
    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
import numpy as np

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

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

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

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

Solution (Python):
n = int(input())
mod = 10**9 + 7
dp = [[0]*(4**3) for i in range(n)]
dic = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
agct_to_num = dict()
num_to_agct = dict()
for i in 'AGCT':
    for j in 'AGCT':
        for k in 'AGCT':
            num = dic[i]*16 + dic[j]*4 + dic[k]*1
            agct_to_num[i+j+k] = num
            num_to_agct[num] = i+j+k

dp[0] = [1] * (4**3)
dp[1] = [1] * (4**3)
dp[2] = [1] * (4**3)
dp[2][agct_to_num['AGC']] = 0
dp[2][agct_to_num['ACG']] = 0
dp[2][agct_to_num['GAC']] = 0


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


for i in range(3, n):
    for j in range(64):
        for c in 'ACGT':
            tmp = num_to_agct[j] + c
            if is_ok(tmp):
                dp[i][agct_to_num[tmp[1:]]] += dp[i-1][j]

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

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


print(dfs(0, "TTT"))