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-----
3

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
mod = 10**9+7
a = []
l = ["A","C","G","T"]
ban = ["AAGC","CAGC","GAGC","TAGC","AGCA","AGCC","AGCG","AGCT","AGAC","CGAC","GGAC","TGAC","GACA","GACC","GACG","GACT","AACG","CACG","GACG","TACG","ACGA","ACGC","ACGG","ACGT","ATGC","ACGC","AGGC","AGTC","AGGC","AGAC"]
for i in l:
    for j in l:
        for k in l:
            a.append(i+j+k)
dp = [[0]*64 for _ in range(n+1)]
for i in range(64):
    if (a[i]=="AGC" or a[i]=="ACG" or a[i]=="GAC"):
        continue
    dp[3][i] = 1
for i in range(4,n+1):
    for j in range(64):
        for k in l:
            b = a[j]+k
            if b in ban:
                continue
            else:
                dp[i][a.index(b[1:])] += dp[i-1][j]
                dp[i][a.index(b[1:])] %= mod
print((sum(dp[-1])%mod))
        


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

moji = ['A','C','G','T']
for c1 in moji:
    for c2 in moji:
        for c3 in moji:
            mojis = c1+c2+c3
            if mojis in ['AGC','GAC','ACG']:continue
            if mojis in dp[3]:
                dp[3][mojis] += 1
            else:
                dp[3][mojis] = 1

for i in range(4,n+1):
    for c in moji:
        for c1 in moji:
            for c2 in moji:
                for c3 in moji:
                    mojis = c1+c2+c3
                    if mojis in ['AGC','GAC','ACG']:continue
                    nowmoji = c2+c3+c
                    if nowmoji in ['AGC','GAC','ACG']:continue
                    if c1 =='A' and c3 == 'G' and c == 'C':continue
                    if c1 =='A' and c2 == 'G' and c == 'C':continue
                    if nowmoji in dp[i]:
                        dp[i][nowmoji] += dp[i-1][mojis]%mod
                        dp[i][nowmoji] %=mod
                    else:
                        dp[i][nowmoji] =  dp[i-1][mojis]%mod
                        dp[i][nowmoji] %=mod

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

n = int(input())
mod = 10**9+7
  
dp = [[0]*4 for i in range(n)]
for i in range(4):
  dp[0][i] = 1
  dp[1][i] = 4
  dp[2][i] = 16
  
dp[2][1] -= 2
dp[2][2] -= 1
  
for i in range(3,n):
  for j in range(4):
    dp[i][j] = sum(dp[i-1])%mod
  dp[i][1] -= dp[i-2][0] #AGC
  dp[i][1] -= dp[i-2][2] #GAC
  dp[i][1] -= dp[i-3][0]*3 #AGTC,AGGC,ATGC
  dp[i][2] -= dp[i-2][0] #ACG
  dp[i][2] += dp[i-3][2] #GACG
  
print(sum(dp[n-1])%mod)

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

dp=[[[[0]*5 for i in range(5)] for i in range(5)] for i in range(N+1)]

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

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

#!/usr/bin/env python3
import copy

n = int(input())

mod = 10**9+7

memo = {}

banned = {'ACTG', 'TCAG', 'GCAG', 'TACG', 'AACG', 'ACAG', 'GAGC', 'CACG',
          'AGC', 'ATCG', 'ACCG', 'CAG', 'GACG', 'CCAG', 'AAGC', 'ACG', 'TAGC'}

count = 0


def dp(lettrs, state):

    if state in banned:
        return 0
    if lettrs == 0:
        return 1
    if (lettrs, state) in memo:
        return memo[lettrs, state]

    ans = 0
    for c in "ACGT":
        ans += dp(lettrs-1, (state+c)[-4:])
        ans %= mod
    ans %= mod
    memo[lettrs, state] = ans

    return ans


print((dp(n, "")))
# print(memo)
# AG = [0, 1]
# for i in range(2, n):
#     ans_pre = copy.deepcopy(ans)
#     ans = copy.deepcopy(ans_base)
#     print(ans_pre)
#     for key in ans_pre.keys():

#         for l in ["A", "C", "G", "T"]:

#             if key+l in miss:
#                 print(key+l)
#                 continue
#             else:
#                 # print((key+l))
#                 ans[(key+l)[1:]] += ans_pre[key] % mod
#     AG.append(ans["AG"])
#     print(AG)
#     ans["AC"] -= AG[-3]
#     ans["GC"] -= AG[-3]
#     ans["TC"] -= AG[-3]


# print(sum(ans.values()) % mod)

# AA
# AC
# AG
# AT
# CA
# CC
# CG
# CT
# GA
# GC
# GG
# GT
# TA
# TC
# TG
# TT


N = int(input())

MOD = 10 ** 9 + 7

total = 4 ** N

if N == 3:
    sub = 3
    ans = total - sub
    
elif N >= 4:
    last_three = [{} for _ in range(N - 3 + 1)]
    for n in range(N - 3 + 1):
        for i in ['A', 'G', 'C', 'T']:
            for j in ['A', 'G', 'C', 'T']:
                for k in ['A', 'G', 'C', 'T']:
                    if [i, j, k] != ['A', 'G', 'C'] and [i, j, k] != ['A', 'C', 'G'] and [i, j, k] != ['G', 'A', 'C']:
                        last_three[n]["".join([i, j, k])] = 0
    for k in last_three[0].keys():
        last_three[0][k] = 1
    for i in range(4, N + 1):
        for k in last_three[i - 4].keys():
            if k[1] == 'A' and k[2] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[1] == 'A' and k[2] == 'C':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[1] == 'G' and k[2] == 'A':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[0] == 'A' and k[2] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[0] == 'A' and k[1] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            else:
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD

    ans = sum(last_three[N - 3].values()) % MOD

print(ans)            

import itertools

ACGT = ['A', 'C', 'G', 'T', '']
MOD = 10 ** 9 + 7

N = int(input())

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

for i, p, q, r, s in itertools.product(list(range(N)), list(range(5)), list(range(5)), list(range(5)), list(range(4))):
    if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
            and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
            and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
        dp[i + 1][q][r][s] += dp[i][p][q][r]
        dp[i + 1][q][r][s] %= MOD

print((sum(sum(sum(y) for y in x) for x in dp[N]) % MOD))


N=int(input())
MOD=10**9+7
dp=[[[[0]*5 for _ in range(5)] for _ in range(5)]for _ in range(N+1)]
ans=0
dp[0][0][0][0]=1
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                for l in range(1,5):
                    if j==1 and k==2 and l==3:continue
                    if j==1 and k==3 and l==2:continue
                    if j==3 and k==1 and l==2:continue
                    if i==1 and j==3 and l==2:continue
                    if i==1 and k==3 and l==2:continue
                    dp[n+1][j][k][l]+=dp[n][i][j][k]
for j in range(1,5):
    for k in range(1,5):
        for l in range(1,5):
            ans+=dp[N][j][k][l]
print(ans%MOD)

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


# 隣接する2文字の入れ替えでAGCとなるパターン(もしくはAGCそのもの)
# AGC
# ACG
# GAC
# AGGC
# ACGC
# ATGC
# AGAC
# AGGC
# AGTC
# 上記を含まない文字列を数える

import sys
readline = sys.stdin.readline

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

# dp[i][a][b][c] = i文字目について、2つ前がa,1つ前がb,i文字目がdの数で条件を満たすものの数
# 0:"A", 1:"G", 2:"C", 3:"T"
dp = [[[[0] * 4 for b in range(4)] for a in range(4)] for i in range(N)]

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

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

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

# 4文字目以降を決める
for i in range(2, len(dp) - 1):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        for k in range(4):
          if check_ok(a,b,c,k) and check_ok(b,c,k):
            dp[i + 1][b][c][k] += dp[i][a][b][c]
            dp[i + 1][b][c][k] %= DIV
        
ans = 0
for a in range(4):
  for b in range(4):
    for c in range(4):
      ans += dp[-1][a][b][c]
      ans %= DIV
      
print(ans)

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 main():
    MOD = 10**9 + 7
    N = int(input())
    memo = [{} for _ in range(N + 1)]

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


def __starting_point():
    main()
__starting_point()

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

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    # dp[i][j][k][l] := 長さiの文字において，後ろから3つ目の文字がj,
    # 後ろから2つ目の文字がk, 後ろから1つの文字がlの時の組み合わせ数
    dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(N + 1)]

    A = 1
    G = 2
    C = 3
    T = 4

    # 文字の意味は，0 => None, 1 => A, 2 => G, 3 => C, 4 => T
    dp[0][0][0][0] = 1
    for i in range(1, N + 1):
        for j in range(5):
            for k in range(5):
                for l in range(5):
                    for m in range(1, 5):
                        if k == A and l == G and m == C:
                            continue
                        if k == A and l == C and m == G:
                            continue
                        if k == G and l == A and m == C:
                            continue
                        if j == A and l == G and m == C:
                            continue
                        if j == A and k == G and m == C:
                            continue

                        dp[i][k][l][m] += dp[i - 1][j][k][l]
                        dp[i][k][l][m] %= MOD

    ans = 0
    for j in range(1, 5):
        for k in range(1, 5):
            for l in range(1, 5):
                ans += dp[-1][j][k][l]
                ans %= MOD
    print(ans)


def __starting_point():
    main()

__starting_point()

from collections import defaultdict

MOD = 10 ** 9 + 7

N = int(input())


"""dp = dict()
for c1 in "ACGT":
    for c2 in "ACGT":
        for c3 in "ACGT":
            for c4 in "ACGT":
                s = c1 + c2 + c3 + c4
                if s[0:3] in ("AGC", "ACG", "GAC"):
                    continue
                if s[1:4] in ("AGC", "ACG", "GAC"):
                    continue
                if s in ("AGGC", "AGTC", "ATGC"):
                    continue

                dp[s] = 1"""

dp = {"TTT": 1}
for _ in range(N):
    new_dp = defaultdict(int)
    for s, count in dp.items():
        new_dp[s[1:] + 'A'] += count
        new_dp[s[1:] + 'T'] += count
        if s[1:] != "AC":
            new_dp[s[1:] + 'G'] += count
        if s not in ("AGG", "AGT", "ATG") and s[1:] not in ("AG", "GA"):
            new_dp[s[1:] + 'C'] += count

    dp = dict()
    for k, v in new_dp.items():
        dp[k] = v % MOD

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

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

mod=10**9+7
n=int(input())
dp=[[0]*64 for _ in range(n+1)]
dp[0][0]=1
#3前、2前,1前,今の文字
#t=0,a=1,g=2,c=3
ban_list=[]
for i in range(256):
	p=[i//64%4,i//16%4,i//4%4,i%4]
	if p[1:]==[1,2,3] or p[1:]==[1,3,2] or p[1:]==[2,1,3]\
	or (p[:2]==[1,2] and p[3]==3) or (p[0]==1 and p[2:]==[2,3]):
		ban_list.append(i)
for i in range(n):
	for j in range(4):
		for k in range(64):
			three=k*4%64+j
			four=k*4+j
			if four not in ban_list:
				dp[i+1][three]+=dp[i][k]
				dp[i+1][three]%=mod
ans=0
for x in dp[-1]:
	ans+=x
	ans%=mod
print(ans)

N = int(input())
dp = [[0]*64 for i in range(N-2)]
# 3進数で管理
mod = 10**9+7

d = dict()
d2 = dict()
d2[0] = 'A'
d2[1] = 'G'
d2[2] = 'C'
d2[3] = 'T'
for i in range(64):
    k = i
    ret = ''
    for j in range(3):
        ret += d2[k % 4]
        k //= 4
    d[i] = ret


for i in range(64):
    if d[i] == 'AGC' or d[i] == 'GAC' or d[i] == "ACG":
        continue

    else:
        dp[0][i] = 1


for i in range(N-3):
    for j in range(64):
        if dp[i][j] == 0:
            continue
        tmp = j // 4
        for k in range(4):
            idx = tmp + k * 16
            if d[idx] == "AGC" or d[idx] == 'ACG' or d[idx] == "GAC" or (d[j][0] == 'A' and d[j][1] == 'G' and k == 2) or (d[j][0] == 'A' and d[j][2] == 'G' and k == 2):
                #print(d[j] + d2[k])
                continue
            dp[i+1][idx] += dp[i][j]


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


def ch2int(ch):
    if ch == 'A':
        return 0
    elif ch == 'C':
        return 1
    elif ch == 'G':
        return 2
    else:
        return 3


def acgt2int(agct):
    ret = 0
    for ch in agct:
        ret = (ret << 2) + ch2int(ch)
    return ret


def int2acgt(val):
    ret = []
    tmp = val
    for i in range(3):
        amari = tmp % 4
        if amari == 0:
            ret.append('A')
        elif amari == 1:
            ret.append('C')
        elif amari == 2:
            ret.append('G')
        else:
            ret.append('T')
        tmp //= 4
    ret.reverse()
    return ret


n = int(input())
dp = [[0] * 64 for _ in range(n)]

dp[0][acgt2int('TTA')] = 1
dp[0][acgt2int('TTC')] = 1
dp[0][acgt2int('TTG')] = 1
dp[0][acgt2int('TTT')] = 1


def is_valid(chs):
    tmp = ''.join(chs)
    ng = ['AGC', 'GAC', 'ACG', 'AAGC', 'ACGC', 'AGGC',
          'ATGC', 'AGAC', 'AGCT', 'AGGC', 'AGTC']
    for item in ng:
        if item in tmp:
            return False
    return True


for i in range(1, n):
    for j in range(64):
        chs = int2acgt(j)
        tmp = 0
        for ch in ['A', 'C', 'G', 'T']:
            my_chs1 = [ch] + chs
            if is_valid(my_chs1):
                tmp += dp[i-1][acgt2int(my_chs1[:-1])] % (10 ** 9 + 7)
        dp[i][j] = tmp

print((sum(dp[-1]) % (10 ** 9 + 7)))


import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random
#Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(self.n))
        self.rank = [1] * n
        self.count = n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.rank[p] += self.rank[q]
        self.par[q] = p
        self.count -= 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return self.rank[x]
    def count(self):
        return self.count

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#Prime-Factorize
def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res
#nCr
mod = 10 ** 9 + 7
class counting:
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
    def per(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[n - r] % mod
#拡張Euclidの互除法
def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g
#BIT
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res
#Associative Array
class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)
#Floor Sum
def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
#Z-Algorithm
def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(self.s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and self.s[i - j] == self.s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
#mod-sqrt
def mod_sqrt(a, p):
    if a == 0:
        return 0
    if p == 2:
        return 1
    k = (p - 1) // 2
    if pow(a, k, p) != 1:
        return -1
    while True:
        n = random.randint(2, p - 1)
        r = (n ** 2 - a) % p
        if r == 0:
            return n
        if pow(r, k, p) == p - 1:
            break
    k += 1
    w, x, y, z = n, 1, 1, 0
    while k:
        if k % 2:
            y, z = w * y + r * x * z, x * y + w * z
        w, x = w * w + r * x * x, 2 * w * x
        w %= p
        x %= p
        y %= p
        z %= p
        k >>= 1
    return y
class SegmentTree:
    def __init__(self, lis, ele, op):
        self.len = len(lis)
        self.n = 1 << ((self.len - 1).bit_length())
        self.op = op
        self.ele = ele
        self.tree = self._build(lis)
    def _build(self, lis):
        res_tree = [self.ele] * (self.n - 1) + lis + [self.ele] * (self.n - self.len)
        for i in range(self.n - 2, -1, -1):
            res_tree[i] = self.op(res_tree[i * 2 + 1], res_tree[i * 2 + 2])
        return res_tree
    def __get__(self, i):
        return self.tree[self.n + i - 1]
    def update(self, i, x):
        i += self.n - 1
        self.tree[i] = x
        while i > 0:
            i -= 1
            i >>= 1
            self.tree[i] = self.op(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
    def query(self, l, r):
        l +=  self.n - 1
        r += self.n - 1
        L = self.ele
        R = self.ele
        while l < r:
            if l & 1 == 0:
                L = self.op(L, self.tree[l])
                l += 1
            if r & 1 == 0:
                r -= 1
                R = self.op(R, self.tree[r])
            l -= 1
            l >>= 1
            r >>= 1
        return self.op(L, R)
def compress(l):
    n = len(l)
    sorted_list = sorted(set(l))
    d = {sorted_list[i]: i for i in range(len(sorted_list))}
    return [d[i] for i in l]
class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y
    def unite(self, x, y, w):
        p, q = self.find(x), self.find(y)
        if self.rank[p] < self.rank[q]:
            self.par[p] = q
            self.weight[p] = w - self.weight[x] + self.weight[y]
        else:
            self.par[q] = p
            self.weight[q] = -w - self.weight[y] + self.weight[x]
            if self.rank[p] == self.rank[q]:
                self.rank[p] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
mod = 10 ** 9 + 7
n = int(input())
dp = [[0] * 4 for i in range(n + 1)]
dp[1][0], dp[1][1], dp[1][2], dp[1][3] = 1, 1, 1, 1
for i in range(1, n + 1):
    for j in range(4):
        dp[i][j] += dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]
        dp[i][j] %= mod
    if i > 1:
        dp[i][1] -= dp[i - 2][0] + dp[i - 2][2]
        dp[i][2] -= dp[i - 2][0]
    if i > 2:
        dp[i][1] -= dp[i - 3][0] * 3
        dp[i][2] += dp[i - 3][2]
print(sum(dp[n]) % mod)

import sys
sys.setrecursionlimit(10000000)
"""
違反文字列
AGC -> AGときたらCはNG
GAC -> GAときたらCはNG
ACG -> ACときたらGはNG
AQGC-> A*GときたらCはNG
AGQC-> AG*ときたらCはNG
"""
n=int(input())
p=10**9+7
ok = ['A','G','C','T']
ng = ['AGC','GAC','ACG']
memo =[{} for i in range(n+1)]

def check(text):
  if text[1:] in ng:
    return 0
  if (text[:2] == 'AG' and text[3]=='C') or (text[0]=='A' and text[2:]=='GC'):
    return 0
  return 1

def dfs(cnt, last):
  if last in memo[cnt]:
    return memo[cnt][last]
  if cnt == n:
    return 1
  ans=0
  for o in ok:
    if check(last+o):
      ans += dfs(cnt+1, last[1:]+o) % p
  memo[cnt][last] = ans
  return ans % p
  

print(dfs(0,'TTT')%p)

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

string = "ACGT"

# AGC
# A*GC
# GAC
# ACG
# AG*C

table = [{} for i in range(n + 1)]
def dfs(s="", depth=n):
    if table[depth].get(s) is not None:
        return table[depth][s]
    if re.search(r"(AGC|A.GC|GAC|ACG|AG.C)", s):
        table[depth][s] = 0
        return 0
    if depth == 0:
        table[depth][s] = 1
        return 1

    cnt = 0
    for i in string:
        cnt += dfs(s[-3:] + i, depth - 1)
        if cnt >= MOD:
            cnt %= MOD
    table[depth][s] = cnt
    return cnt

print((dfs()))


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

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




ACGT = ['A', 'C', 'G', 'T', '']
MOD = 10 ** 9 + 7

N = int(input())
dp = [[[[0] * 5
        for _ in range(5)]
       for _ in range(5)]
      for _ in range(N + 1)]

dp[0][4][4][4] = 1
for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(4):
                    if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
                            and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
                            and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
                        dp[i + 1][q][r][s] += dp[i][p][q][r]
                        dp[i + 1][q][r][s] %= MOD

print((sum(sum(sum(y) for y in x) for x in dp[N]) % MOD))


n = int(input())
mod = 1000000007
dp = [[[0]*4 for _ in range(4)] for _ in range(n+1)]
for j in range(4):
    for k in range(4): dp[2][j][k] = 1

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

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

# for i in range(n+1): print(dp[i])


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

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

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

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

def ok(x,y,z,nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def dfs(idx,lis):
    if idx==N:
      return 1
    x,y,z=lis[0],lis[1],lis[2]
    if (x,y,z) in memo[idx]:
        return memo[idx][(x,y,z)]
    ret=0
    for nx in ['A','G','C','T']:
        if ok(x,y,z,nx):
            ret+=dfs(idx+1,(y,z,nx))
    memo[idx][(x,y,z)]=ret%mod
    return ret%mod

print(dfs(0,'DDD'))

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 6)
import math
from collections import Counter
from collections import deque
from operator import itemgetter
import time, random
MOD = 10 ** 9 + 7
from itertools import permutations

def dfs(s):
    if len(s) == N:
        return 1
    if (s[-2] == 'A' and s[-1] == 'G') or (s[-2] == 'G' and s[-1] == 'A'):
        return dfs(s+'A') % MOD + dfs(s+'G') % MOD + dfs(s+'T') % MOD
    elif s[-2] == 'A' and s[-1] == 'C':
        return dfs(s+'A') % MOD + dfs(s+'C') % MOD + dfs(s+'T') % MOD
    else:
        return dfs(s+'A') % MOD + dfs(s+'C') % MOD + dfs(s+'G') % MOD + dfs(s+'T') % MOD

def main():
    N = int(readline())
    A, G, C, T = 0, 1, 2, 3
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for j in range(4):  # i - 2 文字目
        for k in range(4):  # i - 1 文字目
            for l in range(4):  # i 文字目
                if j == A and k == G and l == C:  continue
                if j == A and k == C and l == G:  continue
                if j == G and k == A and l == C:  continue
                dp[3][j][k][l] = 1
    
    for i in range(4, N+1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if j == A and k == G and l == C:  continue
                        if j == A and k == C and l == G:  continue
                        if j == G and k == A and l == C:  continue
                        if m == A and k == G and l == C:  continue
                        if m == A and j == G and l == C:  continue
                        dp[i][j][k][l] += dp[i-1][m][j][k]
                        dp[i][j][k][l] %= MOD
    
    res = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                res += dp[N][j][k][l]
                res %= MOD
    
    print(res)

def __starting_point():
    main()
__starting_point()

MOD = 10 ** 9 + 7
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 i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[len][i][j][k] == 0: continue

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

import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: list(map(int, sys.stdin.readline().split()))
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
MOD = 10 ** 9 + 7
AGCT3 = ["".join(x) for x in itertools.product("AGCT", repeat=3)]
M = 64
blacklist3 = {"AGC", "ACG", "GAC"}


def solve():
    dp = [[0] * M for _ in range(N + 1)]
    for i in range(M):
        if AGCT3[i] not in blacklist3:
            dp[3][i] = 1
    for i in range(4, N + 1):
        for j in range(M):
            p3 = AGCT3[j]
            if p3 in blacklist3:
                dp[i][j] = 0
                continue
            for k in range(M):
                q3 = AGCT3[k]
                q2 = q3[1:]
                if not p3.startswith(q2):
                    continue
                if p3[1] == "G" and p3[2] == "C" and q3[0] == "A":
                    continue
                if p3[0] == "G" and p3[2] == "C" and q3[0] == "A":
                    continue
                dp[i][j] += dp[i - 1][k]
                dp[i][j] %= MOD
    ans = 0
    for x in dp[N]:
        ans = (ans + x) % MOD
    return ans


print((solve()))


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A, G, C, T = 0, 1, 2, 3
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for j in range(4):  # i - 2 文字目
        for k in range(4):  # i - 1 文字目
            for l in range(4):  # i 文字目
                if j == A and k == G and l == C:  continue
                if j == A and k == C and l == G:  continue
                if j == G and k == A and l == C:  continue
                dp[3][j][k][l] = 1
    
    for i in range(4, N+1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if j == A and k == G and l == C:  continue
                        if j == A and k == C and l == G:  continue
                        if j == G and k == A and l == C:  continue
                        if m == A and k == G and l == C:  continue
                        if m == A and j == G and l == C:  continue
                        dp[i][j][k][l] += dp[i-1][m][j][k]
                        dp[i][j][k][l] %= MOD
    
    res = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                res += dp[N][j][k][l]
                res %= MOD
    
    print(res)

def __starting_point():
    main()
__starting_point()

N=int(input())
mod=10**9+7
dp=[{}for i in range(N)]
list=['AGC','ACG','GAC']
def dfs(x,y):
  if x in list:
    return 0
  if y==N:
    return 1
  if x in dp[y]:
    return dp[y][x]
  ans=0
  for i in 'ACGT':
    if x[0]=='A' and i=='C' and (x[1]=='G' or x[2]=='G'):
      continue
    ans+=dfs(x[1:]+i,y+1)
  dp[y][x]=ans%mod
  return ans%mod
print(dfs('TTT',0))

# D - We Like AGC

from collections import defaultdict

MOD = 10**9+7
N = int(input())
charactors = ['A', 'G', 'C', 'T']

# dp[l][s] := 長さがlで、末尾3文字がsである文字列の個数
dp = [defaultdict(int) for _ in range(N+1)]

# 無関係の文字で初期化しておく
dp[0]['ZZZ'] = 1

# NGケース: AGC, ACG, GAC, A?GC, AG?C
def check(s, c):
    if c=='C':
        if s[1:]=='AG' or s[1:]=='GA' or \
            (s[0]=='A' and (s[1]=='G' or s[2]=='G')):
            return False
        else:
            return True
    elif c=='G':
        if s[1:]=='AC':
            return False
        else:
            return True
    else:
        return True

for i in range(N):
    for s in list(dp[i].keys()):
        for c in charactors:
            # NGケースに該当しなければ、カウントする
            if check(s, c): 
                dp[i+1][s[1:]+c] += dp[i][s]
                dp[i+1][s[1:]+c] %= MOD

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


# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N):
    mod = 10 ** 9 + 7
    dp = [{} for _ in range(N + 1)]
    dp[0].setdefault('TTT', 1)

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

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

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


def __starting_point():
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

__starting_point()

# ABC122D - We Like AGC
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')))


N=int(input())
MOD=10**9+7
dp =[[[[0 for i in range(4)] for i in range(4)] for i in range(4)]for i in range(N+1)]
dp[0][0][0][0]=1
 
for i in range(1,N+1):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        for m in range(4):
          if k==1 and l==2 and m==3:
            continue
          if k==2 and l==1 and m==3:
            continue
          if k==1 and l==3 and m==2:
            continue
          if j==1 and l==2 and m==3:
            continue
          if j==1 and k==2 and m==3:
            continue
          dp[i][k][l][m] += dp[i-1][j][k][l]
          dp[i][k][l][m] %= 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)

import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

    dp = [defaultdict(int) for _ in range(N)]
    for c in 'ACGT':
        dp[0][c + 'XX'] = 1

    for i in range(1, N):
        for s, v in list(dp[i - 1].items()):
            for c in 'AT':
                dp[i][c + s[:2]] = (dp[i][c + s[:2]] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + s[:2]] = (dp[i]['G' + s[:2]] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + s[:2]] = (dp[i]['C' + s[:2]] + v) % MOD

    ans = sum(dp[N - 1].values()) % MOD
    print(ans)

    return


def __starting_point():
    main()

__starting_point()

n = int(input())
#dp[i][x][y][z] i文字目、3つ前がx, 2つ前がy, 1つ前がz
#A->0, C->1, G->2, T->3
#だめなパターンはA-GC, AG-C, GAC, ACGのみ

dp = [[[[0]*4 for i in range(4)] for j in range(4)] for k 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(3, n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for w in range(4):
                    if (y, z, w) == (2, 0, 1):
                        continue
                    if (y, z, w) == (0, 1, 2):
                        continue
                    if (y, z, w) == (0, 2, 1):
                        continue
                    if (x, y, w) == (0, 2, 1):
                        continue
                    if (x, z, w) == (0, 2, 1):
                        continue
                    dp[i+1][y][z][w] += dp[i][x][y][z]
                    dp[i+1][y][z][w] %= 10**9+7
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[n][i][j][k]
print((ans%(10**9+7)))


import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from functools import lru_cache

n = ni()
mod = 10**9+7

@lru_cache(maxsize=10000)
def dfs(n, l):
    rt = 0
    if n == 0:
        return 1
    if l[1:3] == 'AG' or l[1:3] == 'GA' or (l[0] == 'A' and l[2] == 'G') or l[:2] == 'AG':
        pass
    else:
        rt += dfs(n-1, l[1:]+'C')
    if l[1:] != 'AC':
        rt += dfs(n-1,l[1:]+'G')
    rt += dfs(n-1,l[1:]+'T')
    rt += dfs(n-1,l[1:]+'A')
    return rt%mod

print(dfs(n,'TTT')%mod)

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

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

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

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

import numpy as np
N = int(input())
dp = np.zeros((N+1, 5, 5, 5), dtype = np.int64)
#dp[文字列の長さ][3文字前][2文字前][1文字前]
#0:dummy A:1, C:2, G:3, T:4
p = 10**9 + 7
dp[0, 0, 0, 0] = 1
for n in range(N):
  for i in range(5):#3文字前
    for j in range(5):
      for k in range(5):
        for l in range(1, 5):#今回追加する文字#0 : dummmyは初期条件の為なので回さない
          if j == 1 and k == 3 and l == 2:continue #AGC
          if j == 3 and k == 1 and l == 2:continue #GAC
          if j == 1 and k == 2 and l == 3:continue #ACG
          if i == 1 and k == 3 and l == 2:continue #A?GC
          if i == 1 and j == 3 and l == 2:continue #AG?C
          dp[n+1, j, k, l] += dp[n, i, j, k]
          dp[n+1, j, k, l] %= p
ans = 0
for i in range(1, 5):
  for j in range(1, 5):
    for k in range(1, 5):
      ans += dp[N, i, j, k]
      ans %=  p
print(ans)


import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

    dp = [defaultdict(int) for _ in range(N)]
    for c in 'ACGT':
        dp[0][c + 'XX'] = 1

    for i in range(1, N):
        for s, v in list(dp[i - 1].items()):
            t = s[:2]
            for c in 'AT':
                dp[i][c + t] = (dp[i][c + t] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + t] = (dp[i]['G' + t] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + t] = (dp[i]['C' + t] + v) % MOD

    ans = sum(dp[N - 1].values()) % MOD
    print(ans)

    return


def __starting_point():
    main()

__starting_point()

import copy
def main():
    N = int(input())
    if N == 3:
        return 61
    mod = 10**9 + 7
    d = {'A':0, 'C':1, 'G':2, 'T':3}
    AGC = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    AGC[d['A']][d['G']][d['C']] = 0
    AGC[d['A']][d['C']][d['G']] = 0
    AGC[d['G']][d['A']][d['C']] = 0
    NAGC = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    for i in range(3, N):
        for i1 in range(4):
            for i2 in range(4):
                for i3 in range(4):
                    t = 0
                    if (i2 == d['G'] or i1 == d['G']) and i3 == d['C']:
                        for i4 in range(1, 4):
                            t += AGC[i4][i1][i2]
                    else:
                        for i4 in range(4):
                            t += AGC[i4][i1][i2]
                    if i1 == d['A'] and i2 == d['G'] and i3 == d['C']:
                        t = 0
                    if i1 == d['A'] and i2 == d['C'] and i3 == d['G']:
                        t = 0
                    if i1 == d['G'] and i2 == d['A'] and i3 == d['C']:
                        t = 0
                    t %= mod
                    NAGC[i1][i2][i3] = t
        AGC = copy.deepcopy(NAGC)
    return sum(sum(sum(j) for j in i) for i in AGC) % mod
print((main()))


from collections import defaultdict
from functools import reduce

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

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

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

main()

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

n = int(input())
dp = [[0] * 4 for i in range(n + 2)]  # dp[i][j]=(長さiの最後の文字がjで条件を満たす文字列の数:j= 0:A 1:G 2:C 3:T)
# 番兵を2つ置いておくと都合がいい
for i in range(4):
    dp[2][i] = 1
mod = 10**9 + 7
for i in range(3, n + 2):
    for j in range(4):
        for k in range(4):
            dp[i][j] += dp[i - 1][k]
    dp[i][2] -= dp[i - 2][0] # AGCを取り除く.
    dp[i][2] -= dp[i - 2][1] # GACを取り除く.
    dp[i][1] -= dp[i - 2][0] - dp[i - 3][1] # ACGを取り除く. ただしGACGはすでに取り除いている.
    dp[i][2] -= 3 * dp[i - 3][0] # すでに取り除いているものに注意する.結果的にAGGC,ATGC,AGTCを取り除く.
print(sum(dp[-1]) % mod)

MOD = pow(10,9)+7
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 #3333Sとくる場合は制約に何も引っかからない
#dp[i][j][k][l]: i文字目まで見て最後のの三文字がlkjであるような場合の数
#A=0, G=1, C=2, T=3

for i in range(N):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        if dp[i][j][k][l] == 0: #i文字目で条件にあてはまるものがないときは飛ばす。
          continue
        for a in range(4): #ダメな条件を飛ばす
          if a == 2 and j == 1 and k == 0: #AGC
            continue
          if a == 1 and j == 2 and k == 0: #ACG
            continue
          if a == 2 and j == 0 and k == 1: #GAC
            continue
          if a == 2 and j == 1 and l == 0: #A?GC
            continue
          if a == 2 and k == 1 and l == 0: #AG?c
            continue
          dp[i+1][a][j][k] += dp[i][j][k][l]%MOD
ans = 0            
for j in range(4):
  for k in range(4):
    for l in range(4):
      ans += dp[N][j][k][l]
ans = ans%MOD
print(ans)

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

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

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

print(dfs(0,"TTT"))

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

def ok(x, y, z, nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def f(num,A):
  if num==N:
    return 1
  else:
    x,y,z=A[0],A[1],A[2]
    if (x,y,z) in memo[num]:
      return  memo[num][(x,y,z)]
    else:
      s=0
      for i in ['A','C','G','T']:
        if ok(x,y,z,i):
          s+=f(num+1,(y,z,i))
      memo[num][(x,y,z)]=s%mod
      return s%mod
print(f(0,'ZZZ'))

N = int(input())
mod = 10 ** 9 + 7
dp = [{} for i in range(N)]
forbid = set(['AGC', 'GAC', 'ACG'])


def search(i, prefix):
    if prefix in forbid:
        return 0
    elif i == N:
        return 1
    elif prefix in dp[i]:
        return dp[i][prefix]

    ret = 0
    for c in 'ACGT':
        if prefix[0] == 'A' and (prefix[1] == 'G' or prefix[2] == 'G') and c == 'C':
            continue
        ret += search(i + 1, prefix[1:] + c)
    dp[i][prefix] = ret % mod
    return ret % mod


print(search(0, 'BBB'))

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
mod = 10**9+7
from functools import lru_cache

@lru_cache(maxsize=1000)
def dfs(n, l):
    rt = 0
    if n == 0:
        return 1
    if l[1:3] == 'AG' or l[1:3] == 'GA' or (l[0] == 'A' and l[2] == 'G') or l[:2] == 'AG':
        pass
    else:
        rt += dfs(n-1, l[1:]+'C')
    if l[1:] != 'AC':
        rt += dfs(n-1,l[1:]+'G')
    rt += dfs(n-1,l[1:]+'T')
    rt += dfs(n-1,l[1:]+'A')
    return rt%mod



print(dfs(n,'TTT')%mod)

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

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

def judge(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 cur == n:
    return 1
  if last3 in memo[cur]:
    return memo[cur][last3]
  ans = 0
  for c in "AGCT":
    if judge(last3+c):
      ans = (ans+dfs(cur+1, last3[1:]+c))%mod
  memo[cur][last3] = ans
  return ans

print(dfs(0, "TTT"))

import collections, itertools
N = int(input())
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s]
    dp = dp2
print((sum(dp.values()) % mod))


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


from sys import stdin
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    n=int(readline())

    A=0
    T=1
    G=2
    C=3
    dp=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
    dp[0][T][T][T]=1
    for i in range(1,n+1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if j==A and k==G and l==C:
                            pass
                        elif j==A and k==C and l==G:
                            pass
                        elif j==G and k==A and l==C:
                            pass
                        elif m==A and k==G and l==C:
                            pass
                        elif m==A and j==G and l==C:
                            pass
                        else:
                            dp[i][j][k][l]+=dp[i-1][m][j][k]
    ans=0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                ans+=dp[n][j][k][l]
                ans%=mod

    print(ans)

def __starting_point():
    main()
__starting_point()

import sys
from collections import defaultdict
from itertools import product

input = sys.stdin.readline

P = 10 ** 9 + 7


def is_ok(a, b, c, d):
    s = "".join((a, b, c, d))
    if ("AGC" in s) or ("ACG" in s) or ("GAC" in s):
        return False
    if (s[0] == "A" and s[2:4] == "GC") or (s[0:2] == "AG" and s[3] == "C"):
        return False
    return True


def main():
    N = int(input())

    dp = [defaultdict(int) for _ in range(N + 1)]
    dp[0][("T", "T", "T")] = 1

    for i in range(N):
        for a, b, c, d in product("ACGT", repeat=4):
            if is_ok(a, b, c, d):
                dp[i + 1][(b, c, d)] = (dp[i + 1][(b, c, d)] + dp[i][(a, b, c)]) % P

    ans = 0
    for v in list(dp[N].values()):
        ans = (ans + v) % P
    print(ans)


def __starting_point():
    main()

__starting_point()

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

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

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


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

print (dfs(0, 'TTT'))

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

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

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


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


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

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

import numpy as np
from itertools import product

n = int(input())

mod = 10**9 + 7
A, G, C, T = list(range(1, 5))
dp = np.zeros((n+1, 5, 5, 5), dtype=np.int64)
dp[0, 0, 0, 0] = 1
for m in range(n):
    for i, j, k, l in product(list(range(5)), list(range(5)), list(range(5)), list(range(1, 5))):
        if i == A and j == G and l == C:
            continue
        if i == A and k == G and l == C:
            continue
        if j == A and k == G and l == C:
            continue
        if j == G and k == A and l == C:
            continue
        if j == A and k == C and l == G:
            continue
        dp[m+1, j, k, l] += dp[m, i, j, k]
        dp[m, i, j, k] %= mod

res = 0
for i, j, k in product(list(range(1, 5)), repeat=3):
    res += dp[n, i, j, k]
    res %= mod
print(res)


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


m = 1000000007

N = int(input())

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

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

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


# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N):
    mod = 10 ** 9 + 7
    memo = [{} for _ in range(N + 1)]

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

    def dfs(memo, digit, last3):
        # last3文字 + digit文字 で条件を満たす個数を再帰取得する
        if last3 in memo[digit]:
            return memo[digit][last3]  # 計算済みの場合はそれを使用
        if digit == 0:
            return 1  # +0文字なのであればパターンは1のみ
        re = 0
        for c in 'AGCT':
            if check(last3 + c):
                re = (re + dfs(memo, digit - 1, last3[1:] + c)) % mod
        memo[digit][last3] = re
        return re

    print((dfs(memo, N, 'TTT')))  # 最初の3文字は入れ替えてAGCになりうる4文字に干渉しないものにする


def __starting_point():
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

__starting_point()

"""
AtCoder Beginner Contest 122  D - We Like AGC

愚直解
・N文字のうち、各文字についてA,C,G,Tの4通りを取りうるので、4^N
・できた文字について、AGCを含まないか確認：N
・隣接する2文字を一回だけ入れ替えて、AGCができないか確認：N
なので、4^N * N * N ぐらいか？後ろ二つはまとめてもいいが。
また、AAAGCでNGなのがわかっているのに、AAAGCAAを作って調べる〜みたいな重複もいけてない。
このような重複を避けるには、小さい問題からメモ化で解決するDPがよいと思う

入れ替えてAGCができる時、
GAC -> AGC か、 ACG -> AGC、　AXGC -> XAGC、　AGXC -> AGCX
なので、作っている文字列の右端から3文字がわかって入れば行けそう


dp[i+1][j(i-2文字目)][k(i-1文字目)][l(i文字目)]：i文字目をl、一個手前をk、もう一個手前をjとした時の文字列の個数
とすると

遷移
・dp[i+1][A][G][C], dp[i+1][G][A][C], dp[i+1][A][C][G] :こいつらは作ってはいけない
・dp[i][A][＊][G] -> dp[i+1][*][G][C] : Aと* を入れ替えるとAGCができるのでNG
・dp[i][A][G][*] -> dp[i+1][G][*][C] : *とCを入れ替えるとAGCになるのでだめ

上の遷移はなんかややこしいので、ざっくりまとめると、　・・・pqrs　と並んでいて、pqrsについて、
A,G,*,C
A,*,G,C
*,A,G,C,
*,G,A,C
*,A,C,G
がアウトで他はOK
これをDPでやるとよい

最後に末尾3文字について、全パターン見て足し合わせる。


"""

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

# dp[i+1][j(i-2文字目)][k(i-1文字目)][l(i文字目)]：i文字目をl、一個手前をk、もう一個手前をjとした時の文字列の個数
# j,k,lについて、A=1,C=2,G=3,T=4, 初期化の都合上0もある
dp = [[[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ in range(N+1)]
dp[0][0][0][0] = 1
A = 1
C = 2
G = 3
T = 4

for i in range(N):
    # 初期値をうまく利用したいので、p,q,rは0~4まで
    for p in range(5):
        for q in range(5):
            for r in range(5):
                # sをA,C,G,Tで動かす
                for s in range(1, 5):
                    # ・・・・・pqrsの並びにできるか考える
                    """
                    A,G,*,C
                    A,*,G,C
                    *,A,G,C,
                    *,G,A,C
                    *,A,C,G
                    がアウト
                    """
                    if p == A and q == G and s == C : continue
                    if p == A and r == G and s == C : continue
                    if q == A and r == G and s == C : continue
                    if q == G and r == A and s == C : continue
                    if q == A and r == C and s == G : continue

                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD


ans = 0
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            #print(i,j,k, dp[-1][i][j][k])
            ans += dp[-1][i][j][k]
            ans %= MOD


print(ans) 


#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9+7

N = int(input())
# memo[i]: i番目の文字まで作った時の候補数
memo = [{} for _ in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i > 0:
            t[i-1],t[i] = t[i],t[i-1]
        if 'AGC' in ''.join(t):
            return 0
    return 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)) % m
    memo[cur][last3] = res
    return res

print(dfs(0,'TTT'))


from collections import defaultdict


def submit():
    n = int(input())
    modp = 10 ** 9 + 7
    chars = ["A", "C", "G", "T"]
    modp = 10 ** 9 + 7
    # ACGTの4通りの遷移
    # 禁止は次の通り
    # AG -> C
    # A*G -> C
    # GA -> C
    # AC -> G
    # AG* -> C

    # このため,直前の三文字を覚えるようなdpをする
    dp = [defaultdict(int) for _ in range(n + 1)]

    for c1 in chars:
        for c2 in chars:
            for c3 in chars:
                k = c1 + c2 + c3
                if k == "AGC":
                    continue
                if k == "ACG":
                    continue
                if k == "GAC":
                    continue

                dp[3][k] = 1

    for i in range(4, n + 1):
        for k, v in dp[i - 1].items():
            for c in chars:
                # *AG -> C
                if k[1] == "A" and k[2] == "G" and c == "C":
                    continue
                # A*G -> C
                if k[0] == "A" and k[2] == "G" and c == "C":
                    continue
                # *GA -> C
                if k[1] == "G" and k[2] == "A" and c == "C":
                    continue
                # *AC -> G
                if k[1] == "A" and k[2] == "C" and c == "G":
                    continue
                # AG* -> C
                if k[0] == "A" and k[1] == "G" and c == "C":
                    continue

                new_k = k[1:] + c
                dp[i][new_k] += dp[i - 1][k]
                dp[i][new_k] %= modp

    ans = sum(v % modp for v in dp[n].values())
    print(ans % modp)
    

submit()

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

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

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

def dfs(temp, x):
  if x in memo[temp]:
    return memo[temp][x]
  if temp == N:
    return 1
  ans = 0
  for c in 'ACGT':
    if f(x + c):
      ans = (ans + dfs(temp + 1, x[1:] + c)) % MOD
  memo[temp][x] = ans
  return ans

print(dfs(0, 'XXX'))

# 2回前までのを保存しておく全探索？
# -> ATGC ACGC AGGC の場合も条件を満たしてしまうので、3つ前までかも（気づくのに長時間かかった）
# -> AGxCの場合も気づかなかった...

# なぜかサンプル3が合わないがコードが間違ってるわけないので表記ミスと判断して提出（傲慢
# -> MODしてないだけだった...

n = int(input())
if n == 3:
    print((61))
    return

memo = {}
MOD = 10**9 + 7


def rec(i, pre3, pre2, pre1):
    if pre3 == "A" and pre2 == "G" and pre1 == "C":
        return 0
    if pre3 == "G" and pre2 == "A" and pre1 == "C":
        return 0
    if pre3 == "A" and pre2 == "C" and pre1 == "G":
        return 0
    if (i, pre1, pre2, pre3) in memo:
        return memo[(i, pre1, pre2, pre3)]
    if i == n - 3:
        return 1
    else:
        ret = 0
        if (pre1 == "G" and pre2 == "A") or (pre1 == "A" and pre2 == "G"):
            ret = rec(i + 1, pre2, pre1, "A") % MOD + rec(
                i + 1, pre2, pre1, "G") % MOD + rec(i + 1, pre2, pre1,
                                                    "T") % MOD
        elif pre1 == "C" and pre2 == "A":
            ret = rec(i + 1, pre2, pre1, "C") % MOD + rec(
                i + 1, pre2, pre1, "A") % MOD + rec(i + 1, pre2, pre1,
                                                    "T") % MOD
        elif pre3 == "A" and pre1 == "G":
            ret = rec(i + 1, pre2, pre1, "A") % MOD + rec(
                i + 1, pre2, pre1, "G") % MOD + rec(i + 1, pre2, pre1,
                                                    "T") % MOD
        elif pre3 == "A" and pre2 == "G":
            ret = rec(i + 1, pre2, pre1, "A") % MOD + rec(
                i + 1, pre2, pre1, "G") % MOD + rec(i + 1, pre2, pre1,
                                                    "T") % MOD
        else:
            ret = rec(i + 1, pre2, pre1,
                      "A") + rec(i + 1, pre2, pre1, "G") % MOD + rec(
                          i + 1, pre2, pre1, "C") % MOD + rec(
                              i + 1, pre2, pre1, "T") % MOD
        ret %= MOD
        memo[(i, pre1, pre2, pre3)] = ret
        return ret


# 最初とりうるやつ（めんどい）
ans = 0
for i in ["A", "G", "C", "T"]:
    for j in ["A", "G", "C", "T"]:
        for k in ["A", "G", "C", "T"]:
            ans += rec(0, i, j, k)

print((ans % MOD))


n=int(input())
mod1,mod2=10**9+7,998244353
mod=mod1
import sys
sys.setrecursionlimit(10**9)
memo=[{}for i in range(n+1)]
def ok(s):
    if "AGC"in s:return False
    for i in range(3):
        if "AGC"in s[:i]+s[i+1]+s[i]+s[i+2:]:
            return False
    return True
def dfs(cnt,las):
    if las in memo[cnt]:return memo[cnt][las]
    if cnt==n:return 1
    ret=0
    for nec in "AGCT":
        if ok(las+nec):
            ret=(ret+dfs(cnt+1,las[1:]+nec))%mod
    memo[cnt][las]=ret
    return ret
print(dfs(0,"TTT"))

n=int(input())
if n==3:
  print((61))
  return
mod=pow(10,9)+7
#d={'A':0,'G':1,'C':2,'T':3}
d={0:'A',1:'G',2:'C',3:'T'}
dd={}
dinitial={}
for i in range(4**4):
  key=[]
  for _ in range(4):
    key.append(d[i%4])
    i//=4
  key=''.join(key)
  if 'AGC' in key:continue
  if 'ACG' in key:continue
  if 'GAC' in key:continue
  if key[0]=='A' and key[2:4]=='GC':continue
  if key[0:2]=='AG' and key[3]=='C':continue
  dd[key]=1
  dinitial[key]=0

for _ in range(n-4):
  ddd=dinitial.copy()
  for k in dd:
    if k[1:]+'A' in ddd:
      ddd[k[1:]+'A']+=dd[k]
      ddd[k[1:]+'A']%=mod
    if k[1:]+'G' in ddd:
      ddd[k[1:]+'G']+=dd[k]
      ddd[k[1:]+'G']%=mod
    if k[1:]+'C' in ddd:
      ddd[k[1:]+'C']+=dd[k]
      ddd[k[1:]+'C']%=mod
    if k[1:]+'T' in ddd:
      ddd[k[1:]+'T']+=dd[k]
      ddd[k[1:]+'T']%=mod
  dd=ddd

print((sum(dd.values())%mod))


import sys
sys.setrecursionlimit(4100000)

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

def check(txt):
    if 'AGC' in txt:
        return False
    List = list(txt)
    for i in range(3):
        List[i], List[i+1] = List[i+1], List[i]
        if 'AGC' in ''.join(List):
            return False
        List[i], List[i+1] = List[i+1], List[i]
    return True
    
def dfs(i, txt):
    if i == N:
        return 1
    if txt in L[i]:
        return L[i][txt]
    ans = 0
    for char in 'AGCT':
        if check(txt[1:] + char):
            ans += dfs(i+1, txt[1:] + char)
    L[i][txt] = ans % mod
    return ans % mod

print(dfs(0, 'TTTT'))

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

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

n = int(input())
dp = [[0] * 4 for i in range(n + 2)]
for i in range(4):
    dp[2][i] = 1
mod = 10**9 + 7
for i in range(3, n + 2):
    for j in range(4):
        for k in range(4):
            dp[i][j] += dp[i - 1][k]
    dp[i][2] -= dp[i - 2][0]
    dp[i][2] -= dp[i - 2][1]
    dp[i][1] -= dp[i - 2][0] - dp[i - 3][1]
    dp[i][2] -= 3 * dp[i - 3][0]
print((sum(dp[-1]) % mod))


n = int(input())
dp = [[[[1] * 4 for i in range(4)] for j in range(4)] for k in range(n+1)]
dp[3][1][2][0] = 0
dp[3][1][0][2] = 0
dp[3][2][1][0] = 0
if n > 3:
    for i in range(4,n + 1):
        for j in range(4):
            for k in range(4):
                dp[i][3][j][k] = sum(dp[i-1][j][k])
                dp[i][0][j][k] = sum(dp[i-1][j][k])
                if j == 1 and k == 0:
                    dp[i][2][j][k] = 0
                else:
                    dp[i][2][j][k] = sum(dp[i - 1][j][k])
                if j == 0 and k == 2:
                    dp[i][1][j][k] = 0
                elif j == 2 and k == 0:
                    dp[i][1][j][k] = 0
                elif k == 2:
                    dp[i][1][j][2] = sum(dp[i - 1][j][k]) - dp[i - 1][j][2][0]
                elif j == 2:
                    dp[i][1][2][k] = sum(dp[i - 1][j][k]) - dp[i-1][2][k][0]
                else:
                    dp[i][1][j][k] = sum(dp[i - 1][j][k])
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[n][i][j][k] % (10**9 + 7)
print((ans % (10**9 + 7)))


N=int(input())
MOD=10**9+7
R=range(5)
dp=[[[[0,0,0,0,0] for i in R] for j in R] for k in range(N+1)]
dp[0][0][0][0]=1

#0:dammy 1:A 2:G 3:C 4:T
for x in range(N):
    for d in R:
        for c in R:
            for b in R:
                for a in range(1,5):
                    #a:X+1文字目、b:X-1文字目、...
                    if (c==1 and b==2 and a==3):
                        continue
                    if (c==2 and b==1 and a==3):
                        continue
                    if (c==1 and b==3 and a==2):
                        continue
                    if (d==1 and b==2 and a==3):
                        continue
                    if (d==1 and c==2 and a==3):
                        continue
                    dp[x+1][c][b][a]+=dp[x][d][c][b]
                    dp[x+1][c][b][a]%=MOD

ans=0
for c in range(1,5):
    for b in range(1,5):
        for a in range(1,5):
            ans+=dp[N][c][b][a]
            #print(c,b,a,dp[N][c][b][a])
            ans%=MOD

print(ans)

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = int(input())

    # dp[i文字目][3文字前][2文字前][1文字前]
    dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(N + 1)]
    dp[0][0][0][0] = 1

    # _,A,G,C,T = 0,1,2,3,4
    for n in range(N):
        # 3文字前
        for i in range(5):
            # 2文字前
            for j in range(5):
                # 1文字前
                for k in range(5):
                    # 最後の文字
                    for l in range(1, 5):
                        # AG*C
                        if i == 1 and j == 2 and l == 3: continue
                        # A*GC
                        if i == 1 and k == 2 and l == 3: continue
                        # *AGC
                        if j == 1 and k == 2 and l == 3: continue
                        # *GAC
                        if j == 2 and k == 1 and l == 3: continue
                        # *ACG
                        if j == 1 and k == 3 and l == 2: continue
                        dp[n + 1][j][k][l] += dp[n][i][j][k]
                        dp[n + 1][j][k][l] %= mod
    res = 0
    for i in range(5):
        for j in range(5):
            for k in range(5):
                res += dp[-1][i][j][k]
                res %= mod
    print(res)


def __starting_point():
    resolve()

__starting_point()

n = int(input())
dp = [[0]*64 for _ in [0]*n]
mod = 10**9+7

A = 0
C = 1
G = 2
T = 3

AGC = 16*A+4*G+C
ACG = 16*A+4*C+G
GAC = 16*G+4*A+C

for j in range(64):
  if j==AGC or j==ACG or j==GAC:
    dp[2][j] = 0
  else:
    dp[2][j] = 1

for i in range(3, n):
  tot = [sum(dp[i-1][k::16]) for k in range(16)]
  for j in range(64):
    c1 = j//16
    c2 = j//4%4
    c3 = j%4
    d = tot[j//4]

    if j==AGC or j==ACG or j==GAC:
      d = 0
    elif c2==G and c3==C:
      d -= dp[i-1][c1*4+G]
    elif c1==G and c3==C:
      d -= dp[i-1][G*4+c2]
    dp[i][j] = d % mod

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

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


import numpy as np

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

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

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

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

n = int(input())
# A→0,G→1,C→2,T→3
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i==0 and j==1 and k==2) or (i==0 and j==2 and k==1) or (i==2 and j==0 and k==1):
                pass
            else:
                dp[3][i][j][k] = 1

for a in range(3,n):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                # lは新しい桁
                for l in range(4):
                    if (j==0 and k==1):
                        if l==2:
                            continue
                    if (j==0 and k==2):
                        if l==1:
                            continue
                    if (j==2 and k==0):
                        if l==1:
                            continue

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

N=int(input())
mod=10**9+7
dp=[{}for i in range(N)]
list=['AGC','ACG','GAC']
def dfs(x,y):
  if x in list:
    return 0
  if y==N:
    return 1
  if x in dp[y]:
    return dp[y][x]
  ans=0
  for i in 'ACGT':
    if x[0]=='A' and i=='C' and (x[1]=='G' or x[2]=='G'):
      continue
    ans+=dfs(x[1:]+i,y+1)
  dp[y][x]=ans%mod
  return ans%mod
print(dfs('TTT',0))

n = int(input())

mod = 10**9 + 7

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

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

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

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

mod = 10**9+7

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

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

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

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

n = int(input())
dp = [[0] * 4 for i in range(n + 2)]  # dp[i][j]=(長さiの最後の文字がjで条件を満たす文字列の数:j= 0:A 1:G 2:C 3:T)
# 番兵を2つ置いておくと都合がいい
for i in range(4):
    dp[2][i] = 1
mod = 10**9 + 7
for i in range(3, n + 2):
    for j in range(4):
        for k in range(4):
            dp[i][j] += dp[i - 1][k]
    dp[i][2] -= dp[i - 2][0]  # AGCを取り除く.
    dp[i][2] -= dp[i - 2][1]  # GACを取り除く.
    dp[i][1] -= dp[i - 2][0] - dp[i - 3][1]  # ACGを取り除く. ただしGACGはすでに取り除いている.
    dp[i][2] -= 3 * dp[i - 3][0]  # すでに取り除いているものに注意する.結果的にAGGC,ATGC,AGTCを取り除く.

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


import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: list(map(int, sys.stdin.readline().split()))
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
MOD = 10 ** 9 + 7
AGCT3 = ["".join(x) for x in itertools.product("AGCT", repeat=3)]
A, G, C, T = 0, 1, 2, 3
M = 64

blacklist3 = {"AGC", "ACG", "GAC"}


def solve():
    dp = [[0] * M for _ in range(N + 1)]
    for i in range(M):
        if AGCT3[i] not in blacklist3:
            dp[3][i] = 1
    for i in range(4, N + 1):
        for j in range(M):
            p3 = AGCT3[j]
            if p3 in blacklist3:
                dp[i][j] = 0
                continue

            if p3[1] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            if p3[0] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            for k in range(M):
                q3 = AGCT3[k]
                q2 = q3[1:]
                if p3.startswith(q2):
                    dp[i][j] += dp[i - 1][k]
                    dp[i][j] %= MOD
    ans = 0
    for x in dp[N]:
        ans = (ans + x) % MOD
    return ans


print((solve()))


N = int(input())
mod = int(1e9) + 7
line = 'TAGC'
ng = {"AGC", "ACG", "GAC", "ATGC", "AGGC", "ACGC", "AGTC", "AGCC"}
D = {line[(i//16)%4]+line[(i//4)%4]+line[i%4]: i for i in range(64)}
invD = {i: line[(i//16)%4]+line[(i//4)%4]+line[i%4] for i in range(64)}
dp = [[0 for _ in range(N+1)] for __ in range(64)]
dp[0][0] = 1
for i in range(4):
  dp[i][1] = 1
for i in range(16):
  dp[i][2] = 1
for i in range(3, N+1):
  for j in range(64):
    for k in range(4):
      last = invD[j]
      if last not in ng:
        if (last[1:] + line[k]) not in ng and last + line[k] not in ng:
          dp[D[last[1:]+line[k]]][i] += dp[D[last]][i-1]
          dp[D[last[1:]+line[k]]][i] %= mod
S = 0
for i in range(64):
  S += dp[i][N]
  S %= mod
print(S)

n = int(input())
# {0:"A", 1:"C", 2:"G", 3:"T"}
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][3][3][3] = 1
mod = 10 ** 9 + 7

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

print(ans % mod)

n,mod=int(input()),10**9+7
dp=[{} 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 0
    return 1
def dfs(cur,last3):
    if last3 in dp[cur]:
        return dp[cur][last3]
    if cur==n:
        return 1
    ret=0
    for c in 'AGCT':
        if ok(last3+c):
            ret+=dfs(cur+1,last3[1:]+c)
            ret%=mod
    dp[cur][last3]=ret
    return ret




print(dfs(0,'TTT'))

#!/usr/bin python3
# -*- coding: utf-8 -*-

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

mod = 10**9+7

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

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

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

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


N = int(input())

MOD = 10**9 + 7

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

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

for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(1, 5):
                    if p == A and q == G and s == C: 
                        continue
                    if p == A and r == G and s == C:
                        continue
                    if q == A and r == G and s == C: 
                        continue
                    if q == G and r == A and s == C:
                        continue
                    if q == A and r == C and s == G: 
                        continue
                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD

ans = 0
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            ans += dp[-1][i][j][k]
            ans %= MOD

print(ans) 

import numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"

def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res

def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]

def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True

A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1

A = np.array(A, dtype = "object")

def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = "object")
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res

x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print(((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod))
# y = np.dot(mat_power(A, N, mod), x) % mod
# for i in range(64):
#   print(to_str(i, 3) + ":", y[i])


import numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"

# 文字を添え字に
def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res

# 添え字を文字に
def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]

# 部分文字列として含んではいけないものを正規表現で判定
def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True

# 行列作成　各状態からの各遷移が有効か確かめる
A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1
A = np.array(A, dtype = "object")


# 行列の二分累乗
def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = "object")
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res

# ベクトル作成　TTTのみ立てておく
x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod)

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

al=pow(4,n,mod)

import itertools
itr=itertools.product([0,1,2,3],repeat=4)
itr=list(itr)
dic1={} #dec
dic2={} #enc
for i in enumerate(itr):
    dic1[i[0]]=[i[1]]
    dic2[i[1]]=[i[0]]

    

dp=[[0 for i in range(4**3)] for q in range(n+1)]

for i in range(4**3):
    if i!=9 and i!=33 and i!=6:
        dp[3][i]=1


for i in range(3,n):
    for q in range(4**3):
        for r in range(4):
            p1=q//16%4
            p2=q//4%4
            p3=q%4
            
            if p2==0 and p3==2 and r==1:
                continue
            if p1==0 and p3==2 and r==1:
                continue
            if p1==0 and p2==2 and r==1:
                continue
            if p2==0 and p3==1 and r==2:
                continue
            if p2==2 and p3==0 and r==1:
                continue
        
            ck=q%16*4
            dp[i+1][ck+r]+=dp[i][q]
            dp[i+1][ck+r]%=mod

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


from collections import defaultdict
MOD = 10**9 + 7

N = int(input())

dp = [defaultdict(int) for x in range(N+1)]
dp[0][''] = 1

def sol(s):
    if s.find('ABC') != -1: # 見つかった場合
        return False
    L = len(s)
    for i in range(L-1):
        li = list(s)
        li[i], li[i+1] = li[i+1], li[i]
        t = ''.join(li)
        if t.find('ABC') != -1:
            return False
    return True

for n in range(N):
    for s,cnt in list(dp[n].items()):
        for c in 'ABCD':
            ns = s + c
            if sol(ns):
                dp[n+1][ns[-3:]] += cnt
                dp[n+1][ns[-3:]] %= MOD

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


n = int(input())
MOD = 10**9+7
d = {"A":0, "C":1, "G":2, "T":3}
dic = {}
dic_r = {}
for i0 in "ACGT":
    for i1 in "ACGT":
        for i2 in "ACGT":
            v = 4**2*d[i2] + 4*d[i1] + d[i0]
            k = i2+i1+i0
            dic[k] = v
            dic_r[v] = k

dp = [[0] * 64 for i in range(n)]
for i in range(64):
    dp[0][i] = 1
dp[0][dic["AGC"]] = 0
dp[0][dic["ACG"]] = 0
dp[0][dic["GAC"]] = 0
for i in range(n-3):
    for j in range(64):
        v = dic_r[j]
        for s in "ACGT":
            # AG*C
            if v[0] == "A" and v[1] == "G":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # A*GC
            elif v[0] == "A" and v[2] == "G":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # *GAC
            elif v[1] == "G" and v[2] == "A":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # *ACG
            elif v[1] == "A" and v[2] == "C":
                if s != "G":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # *AGC
            elif v[1] == "A" and v[2] == "G":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            else:
                new = v[1] + v[2] + s
                dp[i+1][dic[new]] += dp[i][dic[v]]
    continue
print((sum(dp[n-3])%MOD))




n = int(input())
mod = 10**9+7
A=[1] + [0]*(n-1)
G=[1] + [0]*(n-1)
T=[1] + [0]*(n-1)
C=[1] + [0]*(n-1)
##NG:: AGC,GAC,ACG
AG =[0]*n
GA =[0]*n
AC =[0]*n
##NG:: AGGC,AGTC,ATGC
AGG=[0]*n
AGT=[0]*n
ATG=[0]*n
for i in range(1,n):
    tmp=A[i-1]+G[i-1]+C[i-1]+T[i-1]

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

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

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


print(((A[-1]+G[-1]+C[-1]+T[-1])%mod))
#print(A,G,C,T)
#print(AG,GA,AC)
#print(AGG,AGT,ATG)


import sys
sys.setrecursionlimit(10**6)

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

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(101)]

# ATCGは0123と読み替える
# 長さ0の文字列は1。0,1,2に関する制約しかないので、Sは333Sと考えても問題がない
dp[0][3][3][3] = 1

# 文字列の文字数
for length in range(n):
    # 最後から1文字目の文字
    for c1 in range(4):
        # 最後から2文字目の文字
        for c2 in range(4):
            # 最後から3文字目の文字
            for c3 in range(4):
                # 条件に当てはまる物がない場合はcontinue
                if dp[length][c1][c2][c3] == 0: continue
                # 新しく追加する文字
                for a in range(4):
                    
                    # ダメな5条件をカット
                    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
                    
                    # ダメな条件を抜けたら、aを足した文字列を作れる
                    # S = ... c3 c2 c1
                    # nextS = ... c2 c1 a
                    dp[length+1][a][c1][c2] += dp[length][c1][c2][c3]
                    dp[length+1][a][c1][c2] %= MOD
                    
ans = 0
# 最後から1文字目の文字
for c1 in range(4):
    # 最後から2文字目の文字
    for c2 in range(4):
        # 最後から3文字目の文字
        for c3 in range(4):
            # 長さnの文字列の値をまとめる
            ans += dp[n][c1][c2][c3]
            ans %= MOD
            
print(ans)

import re


def ok(last4):
    pattern = '.?AGC.?|.?GAC.?|.?ACG.?|A.GC|AG.C'
    res = re.match(pattern, last4)
    return res is None


def dfs(cur, last3, n, m, mod):
    if last3 in m[cur]:
        return m[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, n, m, mod)) % mod

    m[cur][last3] = ret
    return ret


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

    m = [{} for _ in range(n + 1)]
    ans = dfs(0, 'TTT', n, m, mod)

    print(ans)


def __starting_point():
    main()

__starting_point()

import collections, itertools
N = int(input())
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s] % mod
    dp = dp2
print((sum(dp.values()) % mod))