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())
memo = [{} for i in range(n+1)]
m = 10**9+7

def ppp(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(c,l):
    if l in memo[c]:
        return memo[c][l]
    if c == n:
        return 1
    ret = 0
    for b in "AGCT":
        if ppp(l+b):
            ret = (ret + dfs(c + 1,l[1:] + b)) % m
    memo[c][l] = ret
    return ret
print(dfs(0,"TTT"))

Solution (Python):
import itertools
from collections import defaultdict

N = int(input())

chs = ['A', 'C', 'G', 'T']
ngs = ['AGC', 'ACG', 'GAC']

memo = defaultdict(int)
for s in list(set(map(''.join, itertools.product(chs, repeat=3))) - set(ngs)):
    memo[s] += 1


for i in range(3, N):
    m = defaultdict(int)
    for key in memo.keys():
        m['C'+key[:2]] += memo[key]
        m['T'+key[:2]] += memo[key]
        if key[:2] != 'AC':
            m['G'+key[:2]] += memo[key]
        if key[:2] != 'CG' and key[:2] != 'GC' and key[0]+key[2] != 'GC' and key[1]+key[2] != 'GC':
            m['A'+key[:2]] += memo[key]
    memo = m
print(sum(memo.values()) % (10**9+7))

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
memo = [{} for _ in range(N)]
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 'AGC' in ''.join(t):
            return False
    return True
def dfs(cur, last3):
    if cur == N:
        return 1
    elif last3 in memo[cur]:
        return memo[cur][last3]
    else:
        ret = 0
        for c in 'ACGT':
            if ok(last3 + c):
                ret += dfs(cur + 1, last3[1:] + c)
        ret = ret % MOD
        memo[cur][last3] = ret
        return ret
print(dfs(0, '   '))

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

from collections import defaultdict

memo=[defaultdict(int) for i in range(N+1)]

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

memo[0]['TTT']=1
for i in range(1,N+1):
    for last3 in memo[i-1].keys():
        v = memo[i-1][last3]%m
        tmp=0
        for c in ['A','G','T','C']:
            if ok(last3+c):
                memo[i][last3[1:]+c]+=v

print(sum(memo[N].values())%m)

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!=3:
      t[i],t[i+1]=t[i+1],t[i]
    if "".join(t).count("AGC")>=1:
      return False
  return True

def solve(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=(solve(cur+1,last3[1:]+c)+ret)%MOD
  memo[cur][last3]=ret
  return ret

print(solve(0,"TTT"))

Solution (Python):

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

memo = [{'AGC':0, 'ACG':0, 'GAC':0} for i in range(N + 4)]
C = list('ACGT')
for c in itertools.product(C, C, C):
    c = ''.join(c)
    if c in memo[3]:
        continue
    else:
        memo[3][c] = 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]
    ret = 0
    for c in 'ACGT':
        if ok(c + last3):
            ret = (ret + dfs(cur - 1, c + last3[:-1])) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(N + 3, 'TTT'))

Solution (Python):

import itertools
N, MOD = int(input()), 10**9+7
memo = [{'AGC':0, 'ACG':0, 'GAC':0} for i in range(N + 1)]
C = list('ACGT')
for c in itertools.product(C, C, C):
    c = ''.join(c)
    if c in memo[3]:
        continue
    else:
        memo[3][c] = 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]
    ret = 0
    for c in 'ACGT':
        if ok(c + last3):
            ret = (ret + dfs(cur - 1, c + last3[:-1])) % MOD
    memo[cur][last3] = ret
    return ret

def answer(n):
    ans = 0
    clist = list('ACGT')
    for c in itertools.product(clist, clist, clist):
        ch = ''.join(c)
        ans += dfs(n, ch)
    return ans % MOD

print(answer(N))

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

def chk_agc(char):
    l=len(char)
    
    result=True
    if l>2:
        last3=char[l-3:l]
        if last3=="AGC" or last3=="ACG" or last3=="GAC":
            result=False
    if l>3:
        if char[l-4]=="A" and char[l-1]=="C":
            if char[l-3]=="G" or char[l-2]=="G":
                result=False
    return result
def count_agc(i,n,last4):
    if i==n:
        return 1
    if last4 in memo[i]:
        return memo[i][last4]
    ret=0
    if i>3:
        last3=last4[1:4]
    else:
        last3=last4
    for char in ["A","G","C","T"]:
        next_last4 = last3+char
        if chk_agc(next_last4):
            ret += count_agc(i+1,n,next_last4)
    if i>2:
        memo[i][last4]=ret
    return ret
print(count_agc(0,n,"")%mod)

Solution (Python):
import pprint

N = int(input())

MOD = pow(10, 9) + 7


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 index in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[index][c1][c2][c3] == 0:
                    continue

                
                for n in range(4):
                    if n == 2 and c1 == 1 and c2 == 0:
                        continue
                    if n == 2 and c1 == 0 and c2 == 1:
                        continue
                    if n == 1 and c1 == 2 and c2 == 0:
                        continue
                    if n == 2 and c1 == 1 and c3 == 0:
                        continue
                    if n == 2 and c2 == 1 and c3 == 0:
                        continue

                    dp[index + 1][n][c1][c2] += dp[index][c1][c2][c3]
                    dp[index + 1][n][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):
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())
P = 10**9 + 7
memo = [{} for i in range(n + 1)]
def ok(last4):
    if last4.count('AGC') >= 1:return False
    for i in range(3):
        t = list(last4)
        t[i], t[i+1] = t[i+1] , t[i]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

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

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

first3s = []
for c in 'ACGT':
	for c2 in 'ACGT':
		for c3 in 'ACGT':
			first3s.append(c + c2 + c3)

ans = 0
for three in first3s:
  mem[3][three] = 0 if three in ['AGC', 'ACG', 'GAC'] else 1
  ans += mem[3][three]

def check4(four):
  if 'AGC' in four:
    return False
  for i in range(3):
    if 'AGC' in four[:i] + four[i+1] + four[i] + four[i+2:]:
      return False
  return True

if n > 3:
  for i in range(4, n + 1):
    ans = 0
    for three in first3s:
      for c in 'ACGT':
        four = c + three
        if check4(four):
          ans = (ans + mem[i - 1][three]) % (10**9 + 7)
          mem[i][(c + three)[:3]] = (mem[i].get((c + three)[:3], 0) + mem[i - 1][three]) % (10**9 + 7)
print(ans)

Solution (Python):
from itertools import product

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

dpm = {
    ''.join(k):1
    for k in product('ACGT', repeat = 3)
}

for k in ('AGC', 'ACG', 'GAC'):
    dpm[k] = 0

def ok4(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

i = 3
ans = 61

while i < N:
    ndpm = {k:0 for k in dpm}
    for k in dpm:
        for c in 'AGCT':
            ns = k + c
            if ok4(ns):
                ndpm[ns[-3:]] += dpm[k]
    dpm = ndpm
    i += 1                

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

Solution (Python):


N = int(input())




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

mod = 10**9+7


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


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

print(ans % mod)

Solution (Python):
import functools
import re

MOD = 10 ** 9 + 7
ACGT = 'ACGT'
GOOD = 'TTT'
BAD = re.compile(r'AGC|GAC|ACG|A.GC|AG.C')


@functools.lru_cache(maxsize=None)
def dfs(n, i, last3):
    if i == n:
        return 1
    else:
        return sum(
            dfs(n, i + 1, last3[1:] + c)
            for c in ACGT
            if not re.search(BAD, last3 + c)) % MOD


N = int(input())
print(dfs(N, 0, GOOD))

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)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[0][i][j][k] = 0
            dp[1][i][j][k] = 1
            dp[2][i][j][k] = 1
            if i == 2 and j == 1 and k == 0:
                continue
            elif i == 1 and j == 2 and k == 0:
                continue
            elif i == 2 and j == 0 and k == 1:
                continue
            dp[3][i][j][k] = 1


for n in range(3, N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for c in range(4):
                    if c == 1 and i == 2 and j == 0:
                        continue
                    elif c == 2 and i == 1 and j == 0:
                        continue
                    elif c == 2 and i == 0 and j == 1:
                        continue
                    elif c == 2 and i == 1 and k == 0:
                        continue
                    elif c == 2 and j == 1 and k == 0:
                        continue
                    dp[n + 1][c][i][j] += dp[n][i][j][k]
                    dp[n + 1][c][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]
print(ans % MOD)

Solution (Python):
import numpy as np
N=int(input())


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(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]%=10**9+7

                    

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

Solution (Python):
def d_we_like_agc(N, MOD=10**9 + 7):
    from itertools import product

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

    for k in range(N):
        for c0, c1, c2, c3 in product(range(4), repeat=4):
            
            strings = ''.join(map(lambda x: 'ACGT'[x], (c0, c1, c2, c3)))
            for s in (strings[:i] + '*' + strings[i + 1:] for i in range(3)):
                if s in ('*AGC', '*GAC', '*ACG', 'A*GC', 'AG*C'):
                    break
            else:
                
                
                dp[k + 1][c1][c2][c3] += dp[k][c0][c1][c2]
                dp[k + 1][c1][c2][c3] %= MOD
    return sum([dp[N][c0][c1][c2] for c0, c1, c2 in product(range(4), repeat=3)]) % MOD

N = int(input())
print(d_we_like_agc(N))

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for x in range(N + 1)]
def ok(sec4):
  for i in range(4):
    tem = list(sec4)
    if i >= 1:
      tem[i - 1], tem[i] = tem[i], tem[i - 1]
    tem2 = "".join(tem)  
    if tem2[:3] == "AGC" or tem2[1:] == "AGC":
      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 s in "AGCT":
    if ok(last3 + s):
      ret = ret + dfs(cur + 1, last3[1:] + s)
  memo[cur][last3] = ret
  return ret
print(dfs(0, "TTT") % MOD)

Solution (Python):
def dfs(index, last, string, memo):
    mod = 10 ** 9 + 7
    if string in memo[index]:
        return memo[index][string]
    if index == last:
        return 1

    ret = 0
    for s in "ACGT":
        if check(string + s):
            ret = (ret + dfs(index + 1, last, string[1:] + s, memo)) % mod
    memo[index][string] = ret
    return ret


def check(string):
    for i in range(4):
        s_list = list(string)
        if i >= 1:
            s_list[i-1], s_list[i] = s_list[i], s_list[i-1]
        if "".join(s_list).count("AGC") >= 1:
            return False
    return True


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

    ans = dfs(0, n, "TTT", memo)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, MOD = int(input()), 10**9 + 7
memo = [{} for x 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):
from sys import exit

N = int(input())


dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for length 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][2][1] = 0
dp[3][2][0][1] = 0
dp[3][0][1][2] = 0

for length in range(4, N + 1):
    
    for c1 in range(4):
        
        for c2 in range(4):
            
            for c3 in range(4):
                
                for s in range(4):
                    if [c2, c3, s] not in ([0, 2, 1], [2, 0, 1], [0, 1, 2]):
                        if [c1, c3, s] != [0, 2, 1] and [c1, c2, s] != [0, 2, 1]:
                            dp[length][c2][c3][s] += dp[length - 1][c1][c2][c3]

ans = 0

for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
print(ans % (10 ** 9 + 7))

Solution (Python):
from sys import exit

N = int(input())


dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for length 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][2][1] = 0
dp[3][2][0][1] = 0
dp[3][0][1][2] = 0

for length in range(4, N + 1):
    
    for c1 in range(4):
        
        for c2 in range(4):
            
            for c3 in range(4):
                if dp[length - 1][c1][c2][c3] == 0:
                    continue
                
                for s in range(4):
                    if [c2, c3, s] not in ([0, 2, 1], [2, 0, 1], [0, 1, 2]):
                        if [c1, c3, s] != [0, 2, 1] and [c1, c2, s] != [0, 2, 1]:
                            dp[length][c2][c3][s] += dp[length - 1][c1][c2][c3]

ans = 0

for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
print(ans % (10 ** 9 + 7))

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],t[i-1] = t[i-1],t[i]
        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 i in 'ACGT':
        if ok(last3 + i):
            ret = (ret + dfs(cur+1,last3[1:]+i)) % mod
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))

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

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

def isAGC(char4):
    for i in range(4):
        tmp = list(char4)
        if i != 3:
            tmp[i], tmp[i + 1] = tmp[i + 1], tmp[i]
        if ''.join(tmp).count('AGC') >= 1:
            return True
    return False

def dfs(cur, char3):
    if char3 in memo[cur]:
        return memo[cur][char3]
    if cur == N:
        return 1
    
    ret = 0
    for c in ['A', 'C', 'G', 'T']:
        if not isAGC(char3 + c):
            ret = (ret + dfs(cur + 1, char3[1:] + c)) % MOD

    memo[cur][char3] = ret
    return ret

print(dfs(0, 'XXX'))

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


for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[3][i][j][k] = 1

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

for i in range(4, n+1):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4):
                    if [b,c,d] not in ([0,2,1],[2,0,1],[0,1,2]):
                        if [a,c,d] != [0,2,1] and [a,b,d] != [0,2,1]:
                                dp[i][b][c][d] += dp[i-1][a][b][c]
                                
count = 0
for i in range(4):
    for j in range(4):
            count = (count + sum(dp[n][i][j])) % (10**9+7)
print(count)

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


def AGCin(s):
    for i in range(len(s) - 2):
        if s[i] == 'A' and s[i+1] == 'G' and s[i+2] == 'C':
            return True
    return False


def isok(last4):
    if AGCin(last4):
        return False
    for i in range(3):
        last4_ = [c for c in last4]
        tmp = last4_[i]
        last4_[i] = last4_[i+1]
        last4_[i+1] = tmp
        if AGCin(''.join(last4_)):
            return False
    return True


def dfs(i, last3):
    if i == n:
        return 1
    if last3 in memo[i]:
        return memo[i][last3]
    ret = 0
    for c in 'AGCT':
        last4 = last3 + c
        if isok(last4):
            new_last3 = last4[1:]
            delta = dfs(i+1, new_last3)
            memo[i+1][new_last3] = delta
            ret = (ret + delta) % mod
    return ret


print(dfs(0, 'TTT'))

Solution (Python):



DNA = ["A","C","G","T"]
ng3 = ["AGC","ACG","GAC"]
ng4 = ["ACGC","AGGC","ATGC", "AGAC","AGTC"]
MOD = 10**9 +7

def main():
    N = int(input())
    memo = [{} for i in range(N+1)]
    
    
        
    
        
        
        
        

    

    
        
        
    
    
    ans = string_check("",0,N,memo)
    
    print(ans%MOD)

    
    


def string_check(nowstr,i,N,memo):
    
    slen = len(nowstr)
    if slen == 3:
        if nowstr in ng3:
            return 0
    if slen == 4:
        if nowstr[-3:] in ng3:
            return 0
        elif nowstr in ng4:
            return 0
    elif slen > 4:
        if nowstr[-3:] in ng3:
            return 0
        elif nowstr[-4:] in ng4:
            return 0
    if nowstr[-3:] in memo[i]:
        return memo[i][nowstr[-3:]]
    elif slen == N:
        return 1
    else:
        count = 0
        for s in DNA:
            count += string_check(nowstr+s,i+1,N,memo)
        if slen >= 4:
            memo[i][nowstr[-3:]] = count
        return count
    


if __name__ == "__main__":
    main()

Solution (Python):

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


def ok(last4):
    if last4.count("AGC")>0:
        return False
    if last4.count("ACG")>0:
        return False
    if last4.count("GAC")>0:
        return False
    if last4[:2]=="AG" and last4[3]=="C":
        return False
    if last4[0]=="A" and last4[2:]=="GC":
        return False
    return True

memo = [{} for _ in range(n+1)]
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==n:
        return 1

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

print(dfs(0, "TTT"))

Solution (Python):






import numpy as np

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

S = np.ones([4, 4, 4], dtype=np.int64)
S[0, 1, 2] = 0
S[0, 2, 1] = 0
S[2, 0, 1] = 0
for _ in range(3, N):
    St = np.zeros([4, 4, 4], dtype=np.int64)
    for i in range(4):
        for j in range(4):
            if i == 0 and j == 2:
                St[j, :, 0] += S[i, j, :]
                St[j, :, 2] += S[i, j, :]
                St[j, :, 3] += S[i, j, :]
            else:
                for k in range(4):
                    St[j, k, 0] += S[i, j, k]
                    St[j, k, 3] += S[i, j, k]
                    if j == 0 and k == 1:
                        St[j, k, 1] += S[i, j, k]
                    elif (j == 0 and k == 2) or (j == 2 and k == 0):
                        St[j, k, 2] += S[i, j, k]
                    elif i == 0 and k == 2:
                        St[j, k, 2] += S[i, j, k]
                    else:
                        St[j, k, 1] += S[i, j, k]
                        St[j, k, 2] += S[i, j, k]
    S = St % x
print(np.sum(S) % x)

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


def judge(last4):
    ret = True
    if any([last4[1:] == s for s in ["AGC","ACG","GAC"]]):
        ret = False
    elif last4[0]+last4[2:] == "AGC":
        ret = False
    elif last4[:2]+last4[3] == "AGC":
        ret = False
    return ret

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

print(dfs(0,"TTT"))

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-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 x in 'ATGC':
        if ok(last3 + x):
            ret = (ret + dfs(cur + 1, last3[1:] + x)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True
for i in range(N+1):
    if i == 0:
        memo[0]["****"] = 1
    elif i == 1:
        memo[1]["***A"] = 1
        memo[1]["***C"] = 1
        memo[1]["***G"] = 1
        memo[1]["***T"] = 1
    else:
        
        for c in 'ACGT':
            for j in memo[i-1]:
                
                if ok(j[1:] + c):
                    if j[1:] + c not in memo[i]:               
                        memo[i][j[1:] + c] = memo[i-1][j] % MOD
                    else:
                        memo[i][j[1:] + c] += memo[i-1][j] % MOD

s = 0
for i in memo[N].values():
    s += i % MOD
print(s % MOD)

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


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

print(dfs(0, 'TTT'))

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret
print(dfs(0, 'TTT'))

Solution (Python):

"""
Created on Mon Apr  1 18:53:11 2019

@author: Yamazaki Kenichi
"""

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

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]

        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in '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, M = int(input()), pow(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)) % M
  memo[cur][last3] = ret
  return ret

print(dfs(0, 'TTT'))

Solution (Python):

import copy
import numpy as np
import random

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 "AGCT":
        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())
N += 1
dp = []
for l in range(N):
  L = []
  for i in range(4):
    I = []
    for j in range(4):
      J = [0,0,0,0]
      I.append(J)
    L.append(I)
  dp.append(L)
dp[0][0][0][0] = 1
NGLIST_JKL = [[1,0,2],[1,1,2],[1,2,2],[1,3,2],[1,2,0],[1,2,1],[1,2,2],[1,2,3]]
NGLIST_KLM = [[1,2,3],[2,1,3],[1,3,2]]
for i in range(N-1):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        if not [j,k,l] in NGLIST_JKL:
          for m in range(4):
            if not [k,l,m] in NGLIST_KLM:
              dp[i+1][k][l][m] += dp[i][j][k][l]
              dp[i+1][k][l][m] = dp[i+1][k][l][m]%(10**9+7)
        else:
          if j == 1 and l == 2:
            for m in range(4):
              if m != 3:
                dp[i+1][k][l][m] += dp[i][j][k][l]
                dp[i+1][k][l][m] = dp[i+1][k][l][m]%(10**9+7)
          elif j == 1 and k == 2:
            for m in range(4):
              if m != 3:
                dp[i+1][k][l][m] += dp[i][j][k][l]
                dp[i+1][k][l][m] = dp[i+1][k][l][m]%(10**9+7)
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans += dp[N-1][i][j][k]%(10**9+7)
print(ans%(10**9+7))