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())
dp=[[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4) ]for _ in range(N+1)]
P=10**9+7

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

for len in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for a in range(4):
                    if j==0 and k==2 and a==1:continue
                    if j==0 and k==1 and a==2:continue
                    if j==2 and k==0 and a==1:continue
                    if i==0 and k==2 and a==1:continue
                    if i==0 and j==2 and a==1:continue
                    dp[len+1][j][k][a]+=dp[len][i][j][k]
                    dp[len+1][j][k][a]%=P

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

Solution (Python):


"""
参考：https://img.atcoder.jp/abc122/editorial.pdf
・数え上げDP
"""

import sys
from itertools import product
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()


dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]

for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1

keys = [''.join(key) for key in product('ACGT', repeat=4)]
for i in range(4, N+1):
    for key in keys:
        for j in range(4):
            tmp=list(key)
            if j>=1:
                
                tmp[j],tmp[j-1]=tmp[j-1],tmp[j]
            if ''.join(tmp).count('AGC'):
                break
        else:
            
            cur,nxt=key[:3],key[1:]
            dp[i][nxt]=(dp[i][nxt]+dp[i-1][cur])%MOD
print((sum(dp[N].values()))%MOD)

Solution (Python):


"""
参考：https://img.atcoder.jp/abc122/editorial.pdf
・数え上げDP
・正規表現
"""

import sys, re
from itertools import product
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()


patterns = [
    
    re.compile(r'^(.?)AGC(.?)$'),
    re.compile(r'^(.?)GAC(.?)$'),
    re.compile(r'^(.?)ACG(.?)$'),
    
    re.compile(r'^A.GC$'),
    re.compile(r'^AG.C$'),
]


dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]

for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1

keys = [''.join(key) for key in product('ACGT', repeat=4)]
for i in range(4, N+1):
    for key in keys:
        
        if not any([ptn.match(key) for ptn in patterns]):
            cur,nxt=key[:3],key[1:]
            dp[i][nxt]=(dp[i][nxt]+dp[i-1][cur])%MOD
print((sum(dp[N].values()))%MOD)

Solution (Python):


"""
参考：https://img.atcoder.jp/abc122/editorial.pdf
・数え上げDP
・正規表現
"""

import sys, re
from itertools import product
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()


patterns = [
    
    re.compile(r'^(.?)AGC(.?)$'),
    re.compile(r'^(.?)GAC(.?)$'),
    re.compile(r'^(.?)ACG(.?)$'),
    
    re.compile(r'^A.GC$'),
    re.compile(r'^AG.C$'),
]


dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]

for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1
    else:
        dp[3][key]=0

for i in range(4, N+1):
    for key in keys:
        for nxt in 'ACGT':
            
            if not any([ptn.match(key+nxt) for ptn in patterns]):
                dp[i][key[1:]+nxt]=(dp[i][key[1:]+nxt]+dp[i-1][key])%MOD
print((sum(dp[N].values()))%MOD)

Solution (Python):














MOD = 10**9+7
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] \
    for _ in range(101) ]
dp[0][3][3][3] = 1
for l in range(100):
    for last3 in range(4):
        for last2 in range(4):
            for last1 in range(4):
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1:
                        continue
                    if last2 == 0 and last1 == 1 and now == 2:
                        continue
                    if last2 == 2 and last1 == 0 and now == 1:
                        continue
                    if last3 == 0 and last2 == 2 and now == 1:
                        continue
                    if last3 == 0 and last1 == 2 and now == 1:
                        continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD
N = int(input())
ans = 0
for last3 in range(4):
    for last2 in range(4):
        for last1 in range(4):
            ans += dp[N][last3][last2][last1]
print(ans%MOD)

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

    def __init__(self, n):
        self.memo = [{} for _ in range(n+1)]
        self.end = n
        self.mod = 10 ** 9 + 7

    def dp(self, cur, last3):
    
        if last3 in self.memo[cur]:
            return self.memo[cur][last3]
        if cur == self.end:
            return 1
        
        ret = 0
        for c in 'ACTG':
            if self.is_ok(last3 + c):
                ret = (ret + self.dp(cur + 1, last3[1:] + c)) % self.mod

        self.memo[cur][last3] = ret
        return ret

    def is_ok(self, 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') > 0:
                return False
        return True


def main():

    n = int(input())
    solver = DP(n)

    print(solver.dp(0, 'CCC'))


main()

Solution (Python):
n = int(input())
mod = int(1e9+7)
dp = [[0 for i in range(4)]for k in range(n+1)] 
for i in range(4):
    dp[1][i] = 1
    dp[2][i] = 4
dp[3][0] = 16
dp[3][1] = 14
dp[3][2] = 15
dp[3][3] = 16
for i in range(4,n+1):
    for k in range(4):
        dp[i][k] = sum(dp[i-1])%mod
    dp[i][1] = dp[i][1] - (dp[i-2][0] + dp[i-2][2]) - dp[i-3][0]*3
    dp[i][2] = dp[i][2] - dp[i-2][0] + dp[i-3][2]
print(sum(dp[n])%mod)

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

m = 10**9 + 7

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




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

A[3][0][2][1] = 0
A[3][0][1][2] = 0
A[3][2][0][1] = 0

for i in range(4, n+1):
    

    for j in range(4):
        for k in range(4):
            for p in range(4):
                for q in range(4):
                    A[i][j][k][p] += A[i-1][q][j][k]
                    A[i][j][k][p] %= m


    for j in range(4) :
        hiku0 = A[i-1][0][j][2]
        A[i][j][2][1] -= hiku0
        hiku1 = A[i-1][0][2][j]
        A[i][2][j][1] -= hiku1

    A[i][2][2][1] += A[i-1][0][2][2]
    
    A[i][0][2][1] = 0
    A[i][0][1][2] = 0
    A[i][2][0][1] = 0
        

ans = 0
for j in range(4):
    for k in range(4):
        ans += sum(A[n][j][k]) % m
print(ans % m)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    d = collections.defaultdict(int)
    d[''] = 1
    t = [
            'AGC',
            'ACG',
            'GAC',
            'AGAC',
            'AGCC',
            'AGTC',
            'ACGC',
            'AGGC',
            'ATGC'
        ]
    for i in range(n):
        e = collections.defaultdict(int)
        for c,v in d.items():
            v %= mod
            for g in 'ACGT':
                if c + g in t or (c + g)[-3:] in t:
                    continue
                e[(c + g)[-3:]] += v
        d = e

    return sum(d.values()) % mod


print(main())

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

m = int(1e9 + 7)
s = "AGCT"
ng = ["AGC", "ACG", "GAC"]
dp = [[0 for _ in range(64)] for _ in range(2)]
for j in range(64):
    t = s[j // 16] + s[(j // 4) % 4] + s[j % 4]
    if t not in ng:
        dp[1][j] = 1
for i in range(4, n + 1):
    for j in range(64):
        dp[i % 2][j] = 0
    for j in range(64):
        for k in range(4):
            t = s[j // 16] + s[(j // 4) % 4] + s[j % 4] + s[k]
            if t[1:] not in ng and t[0] + t[2:] != ng[0] and t[:2] + t[3] != ng[0]:
                dp[i % 2][4 * (j % 16) + k] += dp[1 - i % 2][j]
                dp[i % 2][4 * (j % 16) + k] %= m
ans = sum(dp[n % 2]) % m
print(ans)

Solution (Python):
MAX_NUM = 10 ** 9 + 7

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

def ok(last4):
  if 'AGC' in last4 or \
  'GAC' in last4 or \
  'ACG' in last4 or \
  last4[0] == 'A' and last4[2:] == 'GC' or \
  last4[:2] == 'AG' and last4[-1] == 'C':
    return False
  return True

def dfs(cur, last3):
  if cur == N:
    return 1

  if last3 in memo[cur]:
      return memo[cur][last3]

  res = 0
  for c in 'ACGT':
    last4 = last3 + c
    if ok(last4):
      res += dfs(cur + 1, last4[1:])
      res %= MAX_NUM

  memo[cur][last3] = res
  return res

print dfs(0, 'TTT')

Solution (Python):
MAX_NUM = 10 ** 9 + 7

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

def ok(last4):
  if 'AGC' in last4 or \
  'GAC' in last4 or \
  'ACG' in last4 or \
  last4[0] == 'A' and last4[2:] == 'GC' or \
  last4[:2] == 'AG' and last4[-1] == 'C':
    return False
  return True

def dfs(cur, last3):
  if cur == N:
    return 1

  if last3 in memo[cur]:
      return memo[cur][last3]

  res = 0
  for c in 'ACGT':
    last4 = last3 + c
    if ok(last4):
      res = (res + dfs(cur + 1, last4[1:])) % MAX_NUM

  memo[cur][last3] = res
  return res

print dfs(0, 'TTT')

Solution (Python):
MAX_NUM = 10 ** 9 + 7

N = input()
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 'AGC' in ''.join(t):
      return False
  return True

def dfs(cur, last3):
  if cur == N:
    return 1

  if last3 in memo[cur]:
      return memo[cur][last3]

  res = 0
  for c in 'ACGT':
    last4 = last3 + c
    if ok(last4):
      res = (res + dfs(cur + 1, last4[1:])) % MAX_NUM

  memo[cur][last3] = res
  return res

print dfs(0, 'TTT')

Solution (Python):
dame=['AAGC', 'AACG', 'AGAC', 'AGAC', 'AGGC',
      'AGGC', 'AGTC', 'ATGC', 'GAGC', 'GGAC',
      'CAGC', 'CACG', 'CGAC', 'TAGC', 'TACG', 'TGAC']
memo={"TTT":1}

n=int(input())
for i in range(n):
    nmemo={}
    for c in ["A","G","C","T"]:
        for mk,mv in memo.items():
            nk=mk+c
            if nk not in dame:
                nk=nk[1:]
                if nk in nmemo:
                    nmemo[nk]+=mv
                else:
                    nmemo[nk]=mv
    memo=nmemo
print(sum(memo.values())%(10**9+7))

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


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


DP = [{} for i in range(N+1)]
for i in range(0, N+1):
    
    if i == 0:
        DP[i]['TTT'] = 1
    else:
        for c in 'AGCT':
            for last3, count in DP[i-1].items():
                if ok(last3+c):
                    ret = count % MOD
                    if last3[1:]+c in DP[i]:
                        DP[i][last3[1:]+c] += ret
                    else:
                        DP[i][last3[1:]+c] = ret
print(sum(DP[i].values()) % MOD)

Solution (Python):


n, mod = int(input()), 10 ** 9 + 7


memo = [{} for i in range(n + 1)]

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

def dfs(cnt, last):
    if last in memo[cnt]:
        return memo[cnt][last]
    if cnt == n:
        return 1
    ret = 0
    for c in "ACGT":
        if check(last + c):
            ret = (ret + dfs(cnt + 1, last[1:] + c)) % (10 ** 9 + 7)
    memo[cnt][last] = ret 
    return ret 

print(dfs(0, "TTT"))

Solution (Python):
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,g*4-b-c-d-a*3;'*input());print g%(10**9+7)

Solution (Python):
from collections import defaultdict
import re
from itertools import product

atcg = ['A', 'T', 'C', 'G']
num = int(input())

def validate(tpl):
    string = tpl[0] + tpl[1] + tpl[2] + tpl[3]
    for pat in [r'A.GC', r'AG.C', 'ACG', 'AGC', 'GAC']:
         if re.search(pat, string):
                return False
    return True

def transition(dic):
    new_dic = defaultdict(int)
    for k, v in dic.items():
        for c in atcg:
            tpl = k[1], k[2], k[3], c
            if validate(tpl):
                new_dic[tpl] += v
    return new_dic

it = product(atcg, atcg, atcg, atcg)
dic = {}
for s in it:
    if validate(s):
        dic[s] = 1

if num == 3:
    print(61)
elif num == 4:
    print(230)
else:
    for n in range(num - 4):
        dic = transition(dic)
    print(sum(dic.values()) % 1000000007)

Solution (Python):
N = int(input())
memo = [{} for _ in range(N+1)]
def isOk(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") > 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 isOk(last3+c):
      ret = (dfs(cur+1,last3[1:]+c)+ret)%(10**9+7)
  memo[cur][last3] = ret
  return ret

print(dfs(0,"TTT"))

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

DENOM = 10 ** 9 + 7

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

BASE = "ACGT"
AGC = "AGC"


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


def dfs(cur, last3):
  ret = 0
  if last3 in memo[cur]:
    return memo[cur][last3]
  if cur == N:
    return 1
  for c in BASE:
    if check(last3 + c):
      ret = (ret + dfs(cur + 1, last3[1:] + c)) % DENOM

  memo[cur][last3] = ret
  return ret

print(dfs(0, "TTT"))

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

N = int(input())

STT = [
    [1,0,2,0],[1,3,4,5],[6,0,2,0],[1,0,10,0],[6,10,7,8],
    [1,0,9,0],[1,10,4,5],[6,10,2,0],[1,10,2,0],[6,10,2,0]
]

dp = [[0]*(11) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for st in range(10):
        for ch in range(4):
            dp[i+1][STT[st][ch]] += dp[i][st]
            dp[i+1][STT[st][ch]] %= MOD

print(sum(dp[-1][:-1]) % MOD)

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

mod = 10 ** 9 + 7

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

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

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

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

Solution (Python):
N = int(input())
mod = 10**9+7
dp = [[[[0 for k in range(4)] for j in range(4)] for i in range(4)] for length 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
                    elif a == 2 and c1 == 0 and c2 ==1:
                        continue
                    elif a == 1 and c1 == 2 and c2 ==0:
                        continue
                    elif a == 2 and c1 == 1 and c3 == 0:
                        continue
                    elif a == 2 and c2 == 1 and c3 == 0:
                        continue
                    else:
                        dp[length+1][a][c1][c2] += dp[length][c1][c2][c3]
                        dp[length][c2][c3][a] %= mod
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
print(ans%mod)

Solution (Python):
from functools import lru_cache
from itertools import product


N = int(input())


T = [''.join(t) for t in product(('A', 'C', 'G', 'T'), repeat=3)]



@lru_cache(maxsize=None)
def p(s):
    return all(
        'AGC' not in s[:i] + s[i + 1:i + 2] + s[i] + s[i + 2:]
        for i in range(len(s))
    )



@lru_cache(maxsize=None)
def f(i, s):
    return (
        0 if i == 3 and not p(s) else
        1 if i == 3 and p(s) else
        sum(f(i - 1, t) for t in T if t[1:] == s[:2] and p(t + s[-1]))
    )



ans = sum(f(N, t) for t in T) % (10**9 + 7)


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):
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,g*4-b-c-d-a*3;'*int(input()));print(g%(10**9+7))

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

N = int(input())







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


dp[1] = [1]*4


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

ans = sum(dp[N]) % mod
print(ans)

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

N = int(input())







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


dp[1] = [1]*4


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

ans = sum(dp[N]) % mod
print(ans)

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

N = int(input())







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


dp[1] = [1]*4


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

ans = sum(dp[N]) % mod
print(ans)

Solution (Python):
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,(g*4-b-c-d-a*3)%(10**9+7);'*int(input()));print(g)

Solution (Python):
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,(g*4-(b+c+d+a*3))%(10**9+7);'*int(input()));print(g)

Solution (Python):
a,b,c,d,e,f,g=[0]*6+[1]
for i in [0]*int(input()):d,c,e,f,a,b,g=c,a,a-f,b,g,g-e,(g*4-(c+e+f+d*3))%(10**9+7)
print(g)

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

N = int(input())

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

ans = sum(dp[N]) % mod
print(ans)

Solution (Python):
a,g,a_,a__,ac,ga,al=[0]*6+[1]
for i in range(int(input())):
    a__,a_,ac,ga,a,g,al=a_,a,a-ga,g,al,al-ac,(al*4-(a_+ac+ga+a__*3))%(pow(10,9)+7)
print(al)

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

t=[1,4,16]
a=[0,1,4]
g=[0,1,4]
c=[0,0,1]
 
for i in range(3, N + 1):
    
    t.append(t[i-1]*4 - a[i-2] - c[i-1] - g[i-2] - a[i-3]*3)
    a.append(t[i-1])
    g.append(t[i-1] - c[i-1])
    c.append(t[i-2] - g[i-2])

print(t[N] % (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, 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):
import itertools
import functools
L = "ATGC"
MOD = 10 ** 9 + 7
@functools.lru_cache(maxsize = None)
def rec(s, k):
    if s.count("AGC"):
        return 0
    for i in range(3):
        t = list(s)
        t[i], t[i + 1] = t[i + 1], t[i]
        if ''.join(t).count("AGC"):
            return 0
    if k == 0:
        return 1
    ret = 0
    for x in L:
        ret = (ret + rec(x + s[:3], k - 1)) % MOD
    return ret

N = int(input())
if N == 3:
    print(61)
else:
    ret = 0
    for s in itertools.product(L, repeat = 4):
        ret = (ret + rec(''.join(s), N - 4)) % MOD
    print(ret)

Solution (Python):

import sys
import collections

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 length in range(N):
		for c3 in range(4):
			for c2 in range(4):
				for c1 in range(4):
					if DP[length][c3][c2][c1] == 0:
						continue
					for a in range(4):
						if c2 == 0 and c1 == 1 and a == 2:
							continue
						if c2 == 0 and c1 == 2 and a == 1:
							continue
						if c2 == 1 and c1 == 0 and a == 2:
							continue
						if c3 == 0 and c1 == 1 and a == 2:
							continue
						if c3 == 0 and c2 == 1 and a == 2:
							continue
						DP[length+1][c2][c1][a] = (DP[length+1][c2][c1][a] + DP[length][c3][c2][c1]) % 1000000007
	
	ans = 0
	for c3 in range(4):
		for c2 in range(4):
			for c1 in range(4):
				ans = (ans + DP[N][c3][c2][c1]) % 1000000007
	print(ans)
			
if __name__ == "__main__":
	main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    b = S()
    b = b[0]
    if b == "A":
        print("T")
    elif b == "T":
        print("A")
    elif b == "C":
        print("G")
    elif b == "G":
        print("C")
    return


def B():
    s = S()
    agct = ["A", "G", "C", "T"]
    ans = 0
    for num, i in enumerate(s):
        ansb = 0
        if i in agct:
            ansb += 1
            for k in range(num+1, len(s)):
                if s[k] in agct:
                    ansb += 1
                else:
                    break
        ans = max(ans, ansb)
    print(ans)
    return


def C():
    n, q = LI()
    s = S()
    ans = [0 for i in range(n+1)]
    ac = 0
    for num, ss in enumerate(s):
        if (not ac) and ss == "A":
            ac = 1
            ans[num] = ans[num - 1]
        elif ac and ss == "C":
            ac = 0
            ans[num] = ans[num - 1] + 1
        else:
            if ss == "A":
                ac = 1
            else:
                ac = 0
            ans[num] = ans[num - 1]
    lr = LIR_(q)
    for l,r in lr:
        print(ans[r]-ans[l])

    return


def D():
    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("012") >= 1:
                return False
        return True

    n = II()
    ans = [[[[0 for i in range(4)] for k in range(4)] for l in range(4)] for m in range(n+1)]
    ans[0][3][3][3] = 1
    for l in range(n):
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    if ans[l][a][b][c] == 0:
                        continue
                    for new in range(4):
                        if check(str(a) + str(b) + str(c) + str(new)):
                            ans[l + 1][b][c][new] += ans[l][a][b][c]
                            ans[l + 1][b][c][new] %= mod
    num_ans = 0
    for a in range(4):
        for b in range(4):
            for c in range(4):
                num_ans += ans[n][a][b][c]
                num_ans %= mod
    print(num_ans)                            
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    D()

Solution (Python):
from collections import defaultdict

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

dp = [defaultdict(int) for i in range(N + 1)]
dp[0]['TTT'] = 1
for length in range(N):
    for c1 in 'ACGT':
        for c2 in 'ACGT':
            for c3 in 'ACGT':
                if dp[length][c3 + c2 + c1] == 0:
                    continue
                for c0 in 'ACGT':
                    if c2 + c1 + c0 in ['AGC', 'ACG', 'GAC']:
                        continue
                    if c3 + c1 + c0 == 'AGC':
                        continue
                    if c3 + c2 + c0 == 'AGC':
                        continue
                    dp[length + 1][c2 + c1 + c0] += dp[length][c3 + c2 + c1]

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