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


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




import numpy as np
dp = np.zeros((N+1, 4, 4, 4), dtype="longlong")

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


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

print(dp[N, :, :, :].sum() % MOD)

Solution (Python):
import re,functools as f
@f.lru_cache(None)
def d(n,b):return n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7)
print(d(int(input()),'TTT'))

Solution (Python):


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




import numpy as np
dp = np.zeros((N+1, 4, 4, 4), dtype=int)

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


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

print(dp[N, :, :, :].sum() % MOD)

Solution (Python):
N = int(input())
mod = 1000000000+7

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

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

Solution (Python):
from copy import deepcopy

N = int(input())

dp = [{}] * 4

mod = int(1e9 + 7)


def ok(wxyz):
    if wxyz[1:] == "AGC" or wxyz == "AAGC" or wxyz == "ACGC" or wxyz == "AGGC" or wxyz == "ATGC" \
            or wxyz[1:] == "GAC" or wxyz[1:] == "ACG" \
            or wxyz == "AGAC" or wxyz == "AGCC" or wxyz == "AGTC" or wxyz == "AGGC":
        return 0
    else:
        return 1


for x in ["A", "C", "G", "T"]:
    for y in ["A", "C", "G", "T"]:
        for z in ["A", "C", "G", "T"]:
            xyz = "{}{}{}".format(x, y, z)
            dp[3][xyz] = 1 * ok("P" + xyz)



for i in range(3, N):
    dp.append({})
    for x in ["A", "C", "G", "T"]:
        for y in ["A", "C", "G", "T"]:
            for z in ["A", "C", "G", "T"]:
                xyz = "{}{}{}".format(x, y, z)
                dp[i + 1][xyz] = 0

                for w in ["A", "C", "G", "T"]:
                    wxyz = "{}{}".format(w, xyz)
                    dp[i + 1][xyz] = (dp[i + 1][xyz] + deepcopy(dp[i][wxyz[:-1]]) * ok(wxyz)) % mod


print(sum(dp[N].values()) % mod)

Solution (Python):
import re
import functools

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


@functools.lru_cache(maxsize=2**24)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    return ret % MOD


print(dfs(0, 'TTT'))

Solution (Python):
import re
import functools

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


@functools.lru_cache(maxsize=None)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    return ret % MOD


print(dfs(0, 'TTT'))

Solution (Python):
import re

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


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 not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    ret = ret % MOD
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))

Solution (Python):
n = int(input())
p = 10**9 + 7
memo = [{} for _ in range(n+1)]
def check(L4):
  for i in range(4):
    t = list(L4)
    if i > 0:
      t[i], t[i-1] = t[i-1], t[i]
    if "".join(t).count("AGC") >= 1:
      return False
  return True
def dfs(d, L3):
  if L3 in memo[d]:
    return memo[d][L3]
  if d >= n:
    return 1
  ret = 0
  for L in list("ACGT"):
    L4 = L3 + L
    if check(L4):
      ret += dfs(d + 1, L4[1:]) 
    memo[d][L3] = ret
  return ret % p
    
  
  
print(dfs(0, "TTT"))

Solution (Python):

from sys import exit
def check(a, b, c):
	d = a + b + c;
	off = ['ACG', 'AGC', 'GAC']
	if d in off:
		return False
	else:
		return True


n = int(input())

base = 1000000007

c = ['A', 'C', 'G', 'T']
pre = {}
cur = {}
for ch1 in c:
	for ch2 in c:
		for ch3 in c:
			if check (ch1, ch2, ch3):
				pre[ch1 + ch2 + ch3] = 1
for i in range(4, n+1):
	for s in pre.keys():
		for ch in c:
			st = s + ch
			if check(st[1], st[2], st[3]) and st[0] + st[2] + st[3] != 'AGC' and st[0] + st[1] + st[3] != 'AGC':
				key = st[1] + st[2] + st[3]
				if key in cur:
					tmp = cur[st[1] + st[2] + st[3]]
					tmp = (tmp + pre[s]) % base
					cur[st[1] + st[2] + st[3]] = tmp
				else:
					cur[key] = pre[s] 
				
	pre = cur
	cur = {} 

res = 0
for num in pre.values():
	res = (res + num) % base 

print(res)

Solution (Python):
n = int(input())
memo = [{} for _ in range(n+1)]

def ok(last4):
  if "AGC" in last4:
    return False
  if "ACG" in last4:
    return False
  if "GAC" in last4:
    return False
  if last4[0] == "A" and last4[2:] == "GC":
  	return False
  if last4[:2] == "AG" and last4[3] == "C":
    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 += dfs(cur+1, last3[1:] + c)
  memo[cur][last3] = ret
  return ret

print(dfs(0, "TTT") % 1000000007)

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):
dp=[[[[0]*4 for i in range(4)] for i in range(4)] for i in range(101)]
dp[0][3][3][3]=1
mod=10**9+7

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

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

Solution (Python):
n = int(input())
dp = [{} for i in range(0, n + 1)]

for i in "ATGC":
    for j in "ATGC":
        for k in "ATGC":
            dp[3][i + j + k] = 1
            
del dp[3]["AGC"]
del dp[3]["ACG"]
del dp[3]["GAC"]

def add(i, k, v):
    global dp
    if k in dp[i]:
        dp[i][k] += v
    else:
        dp[i][k] = v

for i in range(4, n + 1):
    for k in dp[i - 1].keys():
        for c in "ATGC":
            l3 = k[1:] + c
            l4 = k + c
            if l3 != "AGC" and l3 != "ACG" and l3 != "GAC" and l4 != "AGGC" and l4 != "AGTC" and l4 != "ATGC":
                add(i, l3, dp[i - 1][k])

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

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

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

print(ans[n])

Solution (Python):
"""
n, mod = int(input()), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(l):
    for i in range(4):
        t = list(l)
        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
    print(cur, memo)
    return ret

print(dfs(0, 'TTT'))
"""

n, mod = int(input()), 10 ** 9 + 7
memo = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
memo[0][3][3][3] = 1
for length in range(n):
    for s3 in range(4):  
        for s2 in range(4):  
            for s1 in range(4):  
                
                
                for s4 in range(4):
                    
                    if s4 == 2 and s3 == 1 and s2 == 0: continue
                    if s4 == 2 and s3 == 0 and s2 == 1: continue
                    if s4 == 1 and s3 == 2 and s2 == 0: continue
                    if s4 == 2 and s3 == 1 and s1 == 0: continue
                    if s4 == 2 and s2 == 1 and s1 == 0: continue
                    
                    memo[length + 1][s4][s3][s2] += memo[length][s3][s2][s1]
                    memo[length + 1][s4][s3][s2] %= mod
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += memo[n][i][j][k]
            ans %= mod

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

for a in range(4):
    for b in range(4):
        for c in range(4):
            dp[2][a][b][c] = 1

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

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][b][c][0] + dp[i-1][a][b][c]) % MOD
                dp[i][b][c][3] = (dp[i][b][c][3] + dp[i-1][a][b][c]) % MOD
                if not (b == 0 and c == 2):
                    dp[i][b][c][1] = (dp[i][b][c][1] + dp[i-1][a][b][c]) % MOD
                if not ((b == 0 and c == 1) or (b == 1 and c == 0) or (a == 0 and (b == 1 or c == 1))):
                    dp[i][b][c][2] = (dp[i][b][c][2] + dp[i-1][a][b][c]) % MOD



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

print(ans)

Solution (Python):
def check(i, j, k, l):
    if (j, k, l) in {(0, 1, 2), (0, 2, 1), (1, 0, 2)} or (i, k, l) == (0, 1, 2) or (i, j, l) == (0, 1, 2):
        return False
    return True


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

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

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

    for i in range(2, N):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if check(j, k, l, m):
                            dp[i+1][k][l][m] = (dp[i+1][k][l][m] + dp[i][j][k][l]) % MOD

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

    print(ans)


if __name__ == '__main__':
    main()

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

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

Solution (Python):
MOD = 1000000007

def violate(s):
    if s[1:] == 'GAC' or s[1:] == 'ACG' or s[1:] == 'AGC':
        return True
    if s[:3] == 'GAC' or s[:3] == 'ACG' or s[:3] == 'AGC':
        return True
    if s[0] == 'A' and s[2:] == 'GC':
        return True
    if s[:2] == 'AG' and s[3] == 'C':
        return True
    return False

def dfs(i, s):
    if s in memo[i]:
        return memo[i][s]
    if i == n:
        return 1
    ret = 0
    for c in 'ATGC':
        if not violate(s + c):
            ret = (ret + dfs(i + 1, s[1:] + c)) % MOD
    memo[i][s] = ret
    return ret

if __name__ == '__main__':
    n = int(input())
    memo = []
    for _ in range(n + 1):
        memo.append({})

    print(dfs(0, 'TTT'))

Solution (Python):
import numpy as np

def main():
    N = int(input())
    dp = [[[[0 for _ in range(4)]for _ in range(4)]for _ in range(4)]for _ 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 a == 2 and c1 == 1 and c2 == 0:
                            continue
                        if a == 2 and c1 == 0 and c2 == 1:
                            continue
                        if a == 1 and c1 == 2 and c2 == 0:
                            continue
                        if a == 2 and c1 == 1 and c3 == 0:
                            continue
                        if a == 2 and c2 == 1 and c3 == 0:
                            continue

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

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import re


xAG = re.compile('[ACGT]AG')
AxG = re.compile('A[ACGT]G')
xGA = re.compile('[ACGT]GA')
AGx = re.compile('AG[ACGT]')


xAC = re.compile('[ACGT]AC')

def func(N):
    d = {a+b+c:1 for a in 'ACGT' for b in 'ACGT' for c in 'ACGT' if a+b+c not in ('AGC','ACG','GAC')}
    for i in range(N-3):
        e = {a+b+c:0 for a in 'ACGT' for b in 'ACGT' for c in 'ACGT' if a+b+c not in ('AGC','ACG','GAC')}
        for k,v in d.items():
            if xAG.match(k) or AxG.match(k) or xGA.match(k) or AGx.match(k):
                n = 'AGT'
            elif xAC.match(k):
                n = 'ACT'
            else:
                n = 'ACGT'
                
            for i in n:
                e[k[1:]+i] += v
                    
        d = e
    print(sum(d.values())%(10**9+7))
    
    
func(N=int(input()))

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 collections import Counter
from itertools import product

def main():
    N = II()
    dp = Counter()
    dp['000'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for (p3, p2, p1), n in pre.items():
            for cur in 'AGCT':
                new = p2 + p1 + cur
                if new in ['AGC', 'GAC', 'ACG']:
                    continue
                if p3 + p1 + cur == 'AGC':
                    continue
                if p3 + p2 + cur == 'AGC':
                    continue
                dp[new] = (dp[new] + n) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

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 collections import Counter
from itertools import product

def main():
    N = II()
    dp = Counter()
    dp['000'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for (p3, p2, p1), n in pre.items():
            for cur in 'AGCT':
                if p2 + p1 + cur in ['AGC', 'GAC', 'ACG']:
                    continue
                if p3 + p1 + cur == 'AGC':
                    continue
                if p3 + p2 + cur == 'AGC':
                    continue
                new = p2 + p1 + cur
                dp[new] = (dp[new] + n) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

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 collections import Counter
from itertools import product

def main():
    N = II()
    dp = Counter()
    dp['000'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for old, n in pre.items():
            for cur in 'AGCT':
                new = old[-2:] + cur
                if new in ['AGC', 'GAC', 'ACG']:
                    continue
                if old[-3] + old[-1] + cur == 'AGC':
                    continue
                if old[:-1] + cur == 'AGC':
                    continue
                dp[new] = (dp[new] + n) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

Solution (Python):

import sys
import numpy as np












MOD = 1000000007  








def solve(N: int):
    A, C, G, T = 0, 1, 2, 3
    dp = np.zeros((102, 4, 4, 4))
    dp[3] = np.ones((4, 4, 4))
    dp[3][A][G][C] = 0
    dp[3][G][A][C] = 0
    dp[3][A][C][G] = 0
    for i in range(3, 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
                        elif k == G and l == A and m == C:
                            
                            continue
                        elif k == A and l == C and m == G:
                            
                            continue
                        elif j == A and k == G and m == C:
                            
                            continue
                        elif j == A and l == G and m == C:
                            
                            continue
                        else:
                            dp[i+1][k][l][m] += dp[i][j][k][l] % MOD
        
    print(int(np.sum(dp[N])) % MOD)
    
    
    
    
    
    
    
    
    
    
    
    
    return


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


if __name__ == '__main__':
    main()

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

def swap(a,b):
    c=[i for i in a]
    c[b],c[b+1]=c[b+1],c[b]
    return "".join(c)

def ok(a):
    if "AGC" in swap(a,0) or "AGC" in swap(a,1) or "AGC" in swap(a,2) or "AGC" in a:
        return False
    return True

if n==1:
    print(4)
elif n==2:
    print(16)
else:
    a={}
    for i in "ACGT":
        for j in "ACGT":
            for k in "ACGT":
                if not i+j+k in ["AGC","ACG","GAC"]:
                    a[i+j+k]=1
    for q in range(n-3):
        b={}
        for i in a:
            for j in "ACGT":
                if ok(i+j):
                    w=i[1:]+j
                    if w in b:
                        b[w]+=a[i]
                    else:
                        b[w]=a[i]
        a=dict(b)
    al=0
    for i in a:
        al+=a[i]
    print(al%(10**9+7))

Solution (Python):
n=int(input())
R=range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][3][3][3]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(2,0,1)!=(k,l,m)!=(0,1,2)!=(k,l,m)!=(0,2,1)!=(j,l,m)!=(0,2,1)!=(j,k,m):dp[i][k][l][m]+=dp[i-1][j][k][l]
print(sum(c for a in dp[n]for b in a for c in b)%(10**9+7))

Solution (Python):
n=int(input())
M,R=10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][3][3][3]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(2,0,1)!=(k,l,m)!=(0,1,2)!=(k,l,m)!=(0,2,1)!=(j,l,m)!=(0,2,1)!=(j,k,m):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)

Solution (Python):
n=int(input())
A,C,G,T,M,R=0,1,2,3,10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][T][T][T]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(G,A,C)!=(k,l,m)!=(A,C,G)!=(k,l,m)!=(A,G,C)!=(j,l,m)!=(A,G,C)!=(j,k,m):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)

Solution (Python):
from collections import Counter

mod = 1000000007
ng3 = ("AGC", "ACG", "GAC")
ng4 = ("AAGC", "ACGC", "AGGC", "ATGC", "AGAC", "AGCC", "AGGC", "AGTC")


def isok(s):
    if s[-3:] in ng3:
        return False
    if s[-4:] in ng4:
        return False
    return True


N = int(input())
dp = [Counter() for _ in range(N + 1)]
dp[0] = {"": 1}
for n in range(1, N + 1):
    for s, v in dp[n-1].items():
        for c in "ACGT":
            if isok(s + c):
                dp[n][s[-3:] + c] += v
print(sum(dp[N].values()) % mod)

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

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

import re
def make_agct(n):        
    agct = ['A', 'G', 'C', 'T']
    accept_list = {}
    
    accept_list[3] = {}
    for s0 in agct:
        for s1 in agct:
            for s2 in agct:
                s = s0 + s1 + s2
                if s == 'AGC':
                    continue
                if s == 'ACG':
                    continue
                if s == 'GAC':
                    continue
                accept_list[3][s] = 1
    
    for i in range(3, n):
        accept_list[i+1] = {}
        for si, v in accept_list[i].items():
            for sn in agct:
                s = si + sn
                last4 = s
                if re.match('.AGC', last4 ):
                    continue
                if re.match('.ACG', last4 ):
                    continue
                if re.match('.GAC', last4 ):
                    continue
                if re.match('AG.C', last4 ):
                    continue
                if re.match('A.GC', last4 ):
                    continue
                last3 = s[1:]
                if last3 in accept_list[i+1]:
                    accept_list[i+1][last3] +=v
                else:
                    accept_list[i+1][last3] = v
    
    ans = 0
    for k, v in accept_list[n].items():
        ans += v
    
    ans = ans % (10 ** 9 + 7)
    print(ans)       
                
make_agct(N)

Solution (Python):
def pow_mod(a: int, n: int, mod: int)->int:
    ret = 1
    for _ in range(n):
        ret = (ret * a) % mod
    return ret


def ok(s: str)->bool:
    '''s が条件をみたすかを判定。
    :param s: 判定対象
    :return: 判定結果
    '''
    if 'AGC' == s[-3:]:
        return False
    if 'GAC' == s[-3:]:
        return False
    if 'ACG' == s[-3:]:
        return False
    if 'A' == s[0] and 'GC' == s[-2:]:
        return False
    if 'AG' == s[:2] and 'C' == s[-1]:
        return False
    return True


def we_like_agc(N: int)->int:
    MOD = 10**9 + 7
    AGCT = 'AGCT'

    
    
    dp = [{}, {}]

    
    
    for c1 in AGCT:
        for c2 in AGCT:
            for c3 in AGCT:
                dp[0][c1 + c2 + c3] = 1 if ok(c1 + c2 + c3) else 0
                dp[1][c1 + c2 + c3] = 0

    
    
    turn = 0
    for _ in range(3, N):
        next_turn = 1-turn
        for s, v in dp[turn].items():
            for c in AGCT:
                next_word = s[1:] + c
                if ok(s + c):
                    
                    
                    dp[next_turn][next_word] += v
                    dp[next_turn][next_word] %= MOD
            
            dp[turn][s] = 0
        
        turn = next_turn

    return sum(v for s, v in dp[(N+1) & 1].items() if ok(s)) % MOD


if __name__ == "__main__":
    N = int(input())
    ans = we_like_agc(N)
    print(ans)

Solution (Python):
n=int(input())
A,C,G,T,M,R=0,1,2,3,10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][T][T][T]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if not(any(t==(k,l,m)for t in((A,G,C),(A,C,G),(G,A,C)))or(j,l,m)==(A,G,C)or(j,k,m)==(A,G,C)):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)

Solution (Python):
n, mod = int(input()), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(l):
    for i in range(4):
        t = list(l)
        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):
n=int(input())
A,C,G,T,M=0,1,2,3,10**9+7
r=range
dp=[[[[0]*4for k in r(4)]for j in r(4)]for i in r(n+1)]
dp[0][T][T][T]=1
for i in r(1,n+1):
  for j in r(4):
    for k in r(4):
      for l in r(4):
        for m in r(4):
          if any(t==(k,l,m)for t in((A,G,C),(A,C,G),(G,A,C)))or(j,l,m)==(A,G,C)or(j,k,m)==(A,G,C):continue
          dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(dp[n][i][j][k]for i in r(4)for j in r(4)for k in r(4))%M)

Solution (Python):
n=int(input())
A,C,G,T,M=0,1,2,3,10**9+7
r=range
dp=[[[[0]*4for k in r(4)]for j in r(4)]for i in r(n+1)]
dp[0][T][T][T]=1
for i in r(1,n+1):
  for j in r(4):
    for k in r(4):
      for l in r(4):
        for m in r(4):
          if any(t==(k,l,m)for t in((A,G,C),(A,C,G),(G,A,C)))or(j,l,m)==(A,G,C)or(j,k,m)==(A,G,C):continue
          dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(dp[n][i][j][k]for i in r(4)for j in r(4)for k in r(4))%M)