CodeEff/ECCO huggingface dataset:
# Original solution
N = int(eval(input()))

MOD = 10**9 + 7

# dp[s][i][j][k] = str[s:s+3]が(i,j,k)となる個数の数え上げ
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]

# 初期条件
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==0 and j==1 and k==2: continue #AGC
            if i==0 and j==2 and k==1: continue #ACG
            if i==1 and j==0 and k==2: continue #GAC
            dp[0][i][j][k] = 1

# 先頭から末尾に向けてループ
for i in range(N-3):
    # 確定している文字列 (ppp,pp,p)
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                # 次の文字 (n)
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue #AGC
                    if pp==0 and p==2 and n==1: continue #ACG
                    if pp==1 and p==0 and n==2: continue #GAC
                    if ppp==0 and p==1 and n==2: continue #A?GC
                    if ppp==0 and pp==1 and n==2: continue #AG?C
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD

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

# Optimized solution
N = int(eval(input()))

MOD = 10 ** 9 + 7

# dp[n][i][j][k]: str[n:n+3]で(i,j,k)となる個数
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N - 2)]

# 初期条件
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i == 0 and j == 1 and k == 2: # ACG
                continue
            if i == 0 and j == 2 and k == 1: # AGC
                continue
            if i == 2 and j == 0 and k == 1: # GAC
                continue
            dp[0][i][j][k] = 1

# 配るDP
for n in range(N - 3):
    for i in range(4):
        for j in range(4):
            for k in range(4):

                # c: 次の文字
                for c in range(4):
                    if j == 0 and k == 1 and c == 2: # ?ACG
                        continue
                    if j == 0 and k == 2 and c == 1: # ?AGC
                        continue
                    if j == 2 and k == 0 and c == 1: # ?GAC
                        continue
                    if i == 0 and k == 2 and c == 1: # A?GC
                        continue
                    if i == 0 and j == 2 and c == 1: # AG?C
                        continue

                    dp[n+1][j][k][c] = (dp[n+1][j][k][c] + dp[n][i][j][k]) % MOD

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

print(ans)
# Original solution
# -*- coding: utf-8 -*-

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

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

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

N=INT()

# NGパターン一覧
patterns = [
    # 任意の0か1文字
    re.compile(r'^(.?)AGC(.?)$'),
    re.compile(r'^(.?)GAC(.?)$'),
    re.compile(r'^(.?)ACG(.?)$'),
    # 任意の1文字
    re.compile(r'^A.GC$'),
    re.compile(r'^AG.C$'),
]

# dp[i][j] := 全部でi文字の時、最後の3文字がjとなる文字列の数
dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]
# 3文字での初期値
for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1
    else:
        dp[3][key]=0

for i in range(4, N+1):
    for key in keys:
        for nxt in 'ACGT':
            # NGパターンのいずれにもマッチしないものだけ遷移させる
            if not any([ptn.match(key+nxt) for ptn in patterns]):
                dp[i][key[1:]+nxt]=(dp[i][key[1:]+nxt]+dp[i-1][key])%MOD
print(((sum(dp[N].values()))%MOD))


# Optimized solution
# -*- coding: utf-8 -*-

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

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

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

N=INT()

# NGパターン一覧
patterns = [
    # 任意の0か1文字
    re.compile(r'^(.?)AGC(.?)$'),
    re.compile(r'^(.?)GAC(.?)$'),
    re.compile(r'^(.?)ACG(.?)$'),
    # 任意の1文字
    re.compile(r'^A.GC$'),
    re.compile(r'^AG.C$'),
]

# dp[i][j] := 全部でi文字の時、最後の3文字がjとなる文字列の数
dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]
# 3文字での初期値
for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1

keys = [''.join(key) for key in product('ACGT', repeat=4)]
for i in range(4, N+1):
    for key in keys:
        # NGパターンのいずれにもマッチしないものだけ遷移させる
        if not any([ptn.match(key) for ptn in patterns]):
            cur,nxt=key[:3],key[1:]
            dp[i][nxt]=(dp[i][nxt]+dp[i-1][cur])%MOD
print(((sum(dp[N].values()))%MOD))
# Original solution
N, MOD = int(eval(input())), 10 ** 9 + 7
memo = [{} for _ in range(101)]

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).find('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')))



# Optimized solution
N = int(eval(input()))
MOD = 10 ** 9 + 7

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

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

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

answer = dfs(0, 'TTT')
print(answer)
# Original solution
# coding: utf-8
import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()

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

@lru_cache(None)
def dfs(i, last3):
    if i == N:
        return 1
    ret = 0
    for la in 'AGCT':
        if ok(last3+la):
            ret += dfs(i+1, last3[1:]+la)
    return ret % MOD

answer = dfs(0, 'TTT')
print((answer % MOD))


# Optimized solution
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

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

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

answer = dfs(0, 'TTT')
print((answer % MOD))
# Original solution
#x=int(input())
n=int(eval(input()))
m=102
chars=['A','T','C','G']
mo=10**9+7
d3=set()
d4=set()
for i in chars:
    for j in chars:
        for k in chars:
            d3.add(i+j+k)
            for l in chars:
                d4.add(i+j+k+l)
        
kinsoku4=set()
kinsoku3=['AGC','ACG','GAC']

for y in chars:
    kinsoku4.add('AG'+y+'C')
    kinsoku4.add('A'+y+'GC')
    for z in kinsoku3:
        kinsoku4.add(y+z)
        kinsoku4.add(z+y)


dp=[dict() for i in range(m)]
cnt=[0]*m
for i in d4:
    if i not in kinsoku4:
        dp[4][i]=1
    

t=101
for i in range(4,t):
    for ch in chars:
        for p in list(dp[i-1].keys()):
            if p[1:4]+ch not in kinsoku4:
                if p[1:4]+ch in dp[i]:
                    dp[i][p[1:4]+ch]+=dp[i-1][p]%mo
                else:
                    dp[i][p[1:4]+ch]=dp[i-1][p]%mo
for i in range(t):
    for x in d4:
        if x not in kinsoku4 and x in dp[i]:
            cnt[i]+=dp[i][x]%mo
    cnt[i]%=mo

#print(len(kinsoku4),kinsoku4)
#print(dp)

#for x in cnt:
    #print(x%mo)

if n==3:
    ans=61
    print(ans)
else:
    print((cnt[n]))




# Optimized solution
n=int(eval(input()))
m=102
chars=['A','T','C','G']
mo=10**9+7
d4=set()
for i in chars:
    for j in chars:
        for k in chars:
            for l in chars:
                d4.add(i+j+k+l)
        
kinsoku4=set()
kinsoku3=['AGC','ACG','GAC']

for y in chars:
    kinsoku4.add('AG'+y+'C')
    kinsoku4.add('A'+y+'GC')
    for z in kinsoku3:
        kinsoku4.add(y+z)
        kinsoku4.add(z+y)

dp=[dict() for i in range(m)]
cnt=[0]*m
for i in d4:
    if i not in kinsoku4:
        dp[4][i]=1

t=1+n
for i in range(4,t):
    for ch in chars:
        for p in list(dp[i-1].keys()):
            if p[1:4]+ch not in kinsoku4:
                if p[1:4]+ch in dp[i]:
                    dp[i][p[1:4]+ch]+=dp[i-1][p]%mo
                else:
                    dp[i][p[1:4]+ch]=dp[i-1][p]%mo
for i in range(t):
    for x in d4:
        if x not in kinsoku4 and x in dp[i]:
            cnt[i]+=dp[i][x]%mo
    cnt[i]%=mo

if n==3:
    ans=61
    print(ans)
else:
    print((cnt[n]))
# Original solution
def main():
    n = int(eval(input()))
    MOD = 10 ** 9 + 7
    note = [{} 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 note[cur]:
            return note[cur][last3]
        if cur == n:
            return 1
        ret = 0
        for c in 'ACGT':
            if ok(last3 + c):
                ret += dfs(cur + 1, last3[1:] + c)
                ret %= MOD
        note[cur][last3] = ret
        return ret

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


main()


# Optimized solution
# from https://atcoder.jp/contests/abc122/submissions/4932940


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

    dpa = [0, 0, 1]
    dpc = [0, 0, 1]
    dpg = [0, 0, 1]
    dpt = [0, 0, 1]
    for i in range(2, n + 2):
        total = dpa[i] + dpc[i] + dpg[i] + dpt[i]
        if i == n + 1:
            break
        dpa.append(total)
        dpc.append(total - dpa[i-1] - dpg[i-1] - 3 * dpa[i-2])
        dpg.append(total - dpa[i-1] + dpg[i-2])
        dpt.append(total)
    print((total % MOD))


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

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

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

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

# Optimized solution
N = int(eval(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], t[i - 1] = t[i - 1], t[i]
        if "".join(t).count("AGC") >= 1:
            return False
    return True

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

print((dfs(0, "TTT") % MOD))
# Original solution

mod = 1000000007
N = int(eval(input()))

dp = [ [[[0 for c3 in range(4)]  for c2 in range(4)]  for c1 in range(4)] for n in range(N+1)]

# 全部TのときはOK
dp[0][3][3][3] = 1

# 文字の数
for n in range(N):
  # 後ろから1文字目
  for c1 in range(4):
    # 後ろから2文字目
    for c2 in range(4):
      # 後ろから3文字目
      for c3 in range(4):
        # 該当するものがないとき
        if dp[n][c1][c2][c3] == 0: continue

        # 新しく追加する文字
        for a in range(4):
          # AGCに当てはまる文字
          if(c2 == 0 and c1 == 1 and a == 2): continue
          if(c2 == 0 and c1 == 2 and a == 1): continue
          if(c2 == 1 and c1 == 0 and a == 2): continue
          if(c3 == 0 and c1 == 1 and a == 2): continue
          if(c3 == 0 and c2 == 1 and a == 2): continue

          dp[n+1][a][c1][c2] += dp[n][c1][c2][c3]
          dp[n+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):
      ans += dp[N][c1][c2][c3]
      ans %= mod

print(ans)

# Optimized solution
# DPをつかった解放を全然思いつけなかった
# 解説動画がわかりやすい

mod = 1000000007
N = int(eval(input()))

dp = [ [[[0 for c3 in range(4)]  for c2 in range(4)]  for c1 in range(4)] for n in range(N+1)]

# 全部TのときはOK
dp[0][3][3][3] = 1

# 文字の数
for n in range(N):
  # 後ろから1文字目
  for c1 in range(4):
    # 後ろから2文字目
    for c2 in range(4):
      # 後ろから3文字目
      for c3 in range(4):
        # 該当するものがないとき
        if dp[n][c1][c2][c3] == 0: continue

        # 新しく追加する文字
        for a in range(4):
          # AGCに当てはまる文字
          if(c2 == 0 and c1 == 1 and a == 2): continue
          if(c2 == 0 and c1 == 2 and a == 1): continue
          if(c2 == 1 and c1 == 0 and a == 2): continue
          if(c3 == 0 and c1 == 1 and a == 2): continue
          if(c3 == 0 and c2 == 1 and a == 2): continue

          dp[n+1][a][c1][c2] += dp[n][c1][c2][c3]

ans = 0
# 後ろから1文字目
for c1 in range(4):
  # 後ろから2文字目
  for c2 in range(4):
    # 後ろから3文字目
    for c3 in range(4):
      ans += dp[N][c1][c2][c3]

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

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

# Optimized solution
print(((388130742,597534442,616680192,329869205,170591295,333099663,133009077,738390145,866398347,718889563,252858375,847205021,915711339,123820509,940737264,371653459,323137024,353770801,206282374,847501730,25328739,842176273,569725155,781042769,427196161,570246669,191483611,673385295,324759692,245601370,975058685,406959393,515140586,305799096,981760191,986519078,414054379,149602322,221791721,792638194,696683714,725438992,702530485,51018086,751629411,971550783,664630886,256852905,775465589,799008836,113468411,39816123,501575626,124885216,998121103,181836645,639213333,123883652,785892908,763737161,534833116,978442997,88638656,604356692,409213624,68697295,649970414,855462856,783022045,23314687,531294469,996291083,549054109,639056669,858533109,159693437,604119499,737209731,44657419,51688048,580025381,776803305,261943303,733354121,794717734,478366600,127504505,33985227,9058467,2414454,643550,171531,45719,12185,3247,865,230,61)[2-int(eval(input()))]))
# Original solution
n=int(eval(input()))
A,C,G,T,M,R=0,1,2,3,10**9+7,list(range(4))
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][T][T][T]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(G,A,C)!=(k,l,m)!=(A,C,G)!=(k,l,m)!=(A,G,C)!=(j,l,m)!=(A,G,C)!=(j,k,m):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print((sum(c for a in dp[n]for b in a for c in b)%M))

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

# Optimized solution
n=int(eval(input()))
R=list(range(4))
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][3][3][3]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(2,0,1)!=(k,l,m)!=(0,1,2)!=(k,l,m)!=(0,2,1)!=(j,l,m)!=(0,2,1)!=(j,k,m):dp[i][k][l][m]+=dp[i-1][j][k][l]
print((sum(c for a in dp[n]for b in a for c in b)%(10**9+7)))
# Original solution
import re,functools as f
@f.lru_cache(None)
def d(n,b):return n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7)
print((d(int(eval(input())),'TTT')))

# Optimized solution
import re,functools as f;d=f.lru_cache(None)(lambda n,b:n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7));print((d(int(eval(input())),'TTT')))
# Original solution
import re,functools as f;d=f.lru_cache(999)(lambda n,b:n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7));print((d(int(eval(input())),'TTT')))

# Optimized solution
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,(g*4-b-c-d-a*3)%(10**9+7);'*int(eval(input())));print(g)
# Original solution
N = int(eval(input()))
if N==3:
    print((61))
    exit()

MOD = 10**9+7
dp = [[0]*64 for i in range(N-2)]

A,C,G,T = 0,1,2,3
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==A and j==G and k==C: continue
            if i==A and j==C and k==G: continue
            if i==G and j==A and k==C: continue
            dp[0][i*16 + j*4+ k] = 1

for i in range(N-3):
    for j in range(64):
        a,b = divmod(j,16)
        b,c = divmod(b,4)
        for d in range(4):
            if b==A and c==G and d==C: continue
            if b==A and c==C and d==G: continue
            if b==G and c==A and d==C: continue
            if a==A and b==G and d==C: continue
            if a==A and c==G and d==C: continue
            dp[i+1][b*16+c*4+d] += dp[i][j]
            dp[i+1][b*16+c*4+d] %= MOD
print((sum(dp[-1]) % MOD))

# Optimized solution
N = int(eval(input()))
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==0 and j==1 and k==2: continue #AGC
            if i==0 and j==2 and k==1: continue #ACG
            if i==1 and j==0 and k==2: continue #GAC
            dp[0][i][j][k] = 1
MOD = 10**9+7
for i in range(N-3):
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue #AGC
                    if pp==0 and p==2 and n==1: continue #ACG
                    if pp==1 and p==0 and n==2: continue #GAC
                    if ppp==0 and p==1 and n==2: continue #A?GC
                    if ppp==0 and pp==1 and n==2: continue #AG?C
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD
ans = sum(sum(sum(a) for a in b) for b in dp[-1])
print((ans%MOD))
# Original solution
n = int(eval(input()))

MOD = 10 ** 9 + 7

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

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

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

for i in range(3, n):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                dp[i][b][c][0] = (dp[i][b][c][0] + dp[i-1][a][b][c]) % MOD
                dp[i][b][c][3] = (dp[i][b][c][3] + dp[i-1][a][b][c]) % MOD
                if not (b == 0 and c == 2):
                    dp[i][b][c][1] = (dp[i][b][c][1] + dp[i-1][a][b][c]) % MOD
                if not ((b == 0 and c == 1) or (b == 1 and c == 0) or (a == 0 and (b == 1 or c == 1))):
                    dp[i][b][c][2] = (dp[i][b][c][2] + dp[i-1][a][b][c]) % MOD

#print(dp)

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

print(ans)

# Optimized solution
n = int(eval(input()))

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

print((ans[n]))