from itertools import product

from collections import defaultdict

MOD = 10**9 + 7

N = int(eval(input()))

# XAGC, XGAC, AXGC, AGXC, XACG: prohibited

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

cur = defaultdict(lambda: 1)

cur[(A,G,C)] = cur[(G,A,C)] = cur[(A,C,G)] = 0

for _ in range(3,N):

    prev = cur

    cur = defaultdict(int)

    for (i,j,k,l) in product(list(range(4)),repeat=4):

        if ((j,k,l)==(A,G,C) or (j,k,l)==(G,A,C) or (i,k,l)==(A,G,C) or

            (i,j,l)==(A,G,C) or (j,k,l)==(A,C,G)):

            continue

        else:

            cur[(j,k,l)] += prev[(i,j,k)]

    for ijk in product(list(range(4)),repeat=3):

        cur[ijk] %= MOD



ans = sum(cur.values()) % MOD

if N <= 3:

    print(([1,4,16,61][N]))

else:

    print(ans)
from itertools import product

from collections import defaultdict

MOD = 10**9 + 7

N = int(eval(input()))

D, L = 4, 3

AGC = list(range(L))

ATGC = list(range(D))

cur = defaultdict(lambda: 1)

# XAGC, XGAC, AXGC, AGXC, XACG: prohibited

flip = lambda x, n: x[:n] + [x[n+1],x[n]] + x[n+2:]

prohibited1 = [tuple(AGC)] + [tuple(flip(AGC,i)) for i in range(L-1)]

prohibited2 = ({(X,) + p for p in prohibited1 for X in ATGC} | 

             {tuple(flip([X]+AGC,0)) for X in ATGC} |

             {tuple(flip(AGC+[X],L-1)) for X in ATGC})

for p in prohibited1:

    cur[p] = 0

for _ in range(L,N):

    prev = cur

    cur = defaultdict(int)

    for recent in product(ATGC, repeat=L+1):

        if recent in prohibited2:

            continue

        else:

            cur[recent[1:]] += prev[recent[:-1]]

    for latest in product(ATGC, repeat=L):

        cur[latest] %= MOD



ans = sum(cur.values()) % MOD

if N < L:

    print((D**N))

elif N == L:

    print((D**L - len(prohibited1)))

else:

    print(ans)
from itertools import product
from collections import defaultdict

MOD = 10**9 + 7
N = int(eval(input()))
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
A = 0
C = 1
G = 2
T = 3
cur = defaultdict(lambda: 1)
cur[(A, G, C)] = cur[(G, A, C)] = cur[(A, C, G)] = 0
for _ in range(3, N):
    prev = cur
    cur = defaultdict(int)
    for (i, j, k, l) in product(list(range(4)), repeat=4):
        if (
            (j, k, l) == (A, G, C)
            or (j, k, l) == (G, A, C)
            or (i, k, l) == (A, G, C)
            or (i, j, l) == (A, G, C)
            or (j, k, l) == (A, C, G)
        ):
            continue
        else:
            cur[(j, k, l)] += prev[(i, j, k)]
    for ijk in product(list(range(4)), repeat=3):
        cur[ijk] %= MOD
ans = sum(cur.values()) % MOD
if N <= 3:
    print(([1, 4, 16, 61][N]))
else:
    print(ans)

from itertools import product
from collections import defaultdict

MOD = 10**9 + 7
N = int(eval(input()))
D, L = 4, 3
AGC = list(range(L))
ATGC = list(range(D))
cur = defaultdict(lambda: 1)
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
flip = lambda x, n: x[:n] + [x[n + 1], x[n]] + x[n + 2 :]
prohibited1 = [tuple(AGC)] + [tuple(flip(AGC, i)) for i in range(L - 1)]
prohibited2 = (
    {(X,) + p for p in prohibited1 for X in ATGC}
    | {tuple(flip([X] + AGC, 0)) for X in ATGC}
    | {tuple(flip(AGC + [X], L - 1)) for X in ATGC}
)
for p in prohibited1:
    cur[p] = 0
for _ in range(L, N):
    prev = cur
    cur = defaultdict(int)
    for recent in product(ATGC, repeat=L + 1):
        if recent in prohibited2:
            continue
        else:
            cur[recent[1:]] += prev[recent[:-1]]
    for latest in product(ATGC, repeat=L):
        cur[latest] %= MOD
ans = sum(cur.values()) % MOD
if N < L:
    print((D**N))
elif N == L:
    print((D**L - len(prohibited1)))
else:
    print(ans)

+D, L = 4, 3 +AGC = list(range(L)) +ATGC = list(range(D)) +cur = defaultdict(lambda: 1) -A = 0 -C = 1 -G = 2 -T = 3 -cur = defaultdict(lambda: 1) -cur[(A, G, C)] = cur[(G, A, C)] = cur[(A, C, G)] = 0 -for _ in range(3, N): +flip = lambda x, n: x[:n] + [x[n + 1], x[n]] + x[n + 2 :] +prohibited1 = [tuple(AGC)] + [tuple(flip(AGC, i)) for i in range(L - 1)] +prohibited2 = ( +    {(X,) + p for p in prohibited1 for X in ATGC} +    | {tuple(flip([X] + AGC, 0)) for X in ATGC} +    | {tuple(flip(AGC + [X], L - 1)) for X in ATGC} +) +for p in prohibited1: +    cur[p] = 0 +for _ in range(L, N): -    for (i, j, k, l) in product(list(range(4)), repeat=4): -        if ( -            (j, k, l) == (A, G, C) -            or (j, k, l) == (G, A, C) -            or (i, k, l) == (A, G, C) -            or (i, j, l) == (A, G, C) -            or (j, k, l) == (A, C, G) -        ): +    for recent in product(ATGC, repeat=L + 1): +        if recent in prohibited2: -            cur[(j, k, l)] += prev[(i, j, k)] -    for ijk in product(list(range(4)), repeat=3): -        cur[ijk] %= MOD +            cur[recent[1:]] += prev[recent[:-1]] +    for latest in product(ATGC, repeat=L): +        cur[latest] %= MOD -if N <= 3: -    print(([1, 4, 16, 61][N])) +if N < L: +    print((D**N)) +elif N == L: +    print((D**L - len(prohibited1)))