AtCoder Beginner Contest 122 - We Like AGC

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.

Source: atcoder | Difficulty: MEDIUM


Solutions:
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))


N = int(input())
MOD = 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 '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())
(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())
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
	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'))


n = int(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):
	dpa.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
	dpc.append(dpa[i] - dpg[i - 1] + dpc[i] + dpg[i] - dpa[i - 1] - 2 * dpa[i - 2] + dpt[i] - dpa[i - 2])
	dpg.append(dpa[i] + dpc[i] - dpa[i - 1] + dpg[i - 2] + dpg[i] + dpt[i])
	dpt.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
print((dpa[n + 1] + dpg[n + 1] + dpc[n + 1] + dpt[n + 1]) % MOD)


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

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

def dfs(i, last3):
	if last3 in memo[i]:
		return memo[i][last3]
	if i == n:
		return 1
	res = 0
	for c in 'ACGT':
		if judge(last3 + c):
			res = (res + dfs(i + 1, last3[1:] + c)) % mod
	memo[i][last3] = res
	return res
print(dfs(0, 'TTT'))


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:
			tmp = t[i]
			t[i] = t[i - 1]
			t[i - 1] = tmp
		if ''.join(t).count('AGC') >= 1:
			return False
	return True

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


N = int(input())
s = ['A', 'C', 'G', 'T']
invs = ['AGC', 'ACG', 'GAC']
d = {}
for c1 in s:
	for c2 in s:
		for c3 in s:
			d[c1 + c2 + c3] = 1 if c1 + c2 + c3 not in invs else 0
dn = {}
for _ in range(N - 3):
	for c1 in s:
		for c2 in s:
			for c3 in s:
				cnt = 0
				for c0 in s:
					if c0 + c2 + c3 != 'AGC' and c0 + c1 + c3 != 'AGC':
						cnt += d[c0 + c1 + c2]
				dn[c1 + c2 + c3] = cnt % 1000000007 if c1 + c2 + c3 not in invs else 0
	(dn, d) = (d, dn)
print(sum(d.values()) % 1000000007)


import itertools
N = int(input())
MOD = 10 ** 9 + 7
ACGT = ['A', 'C', 'G', 'T']
dp = [[[[0 for l in range(4)] for k in range(4)] for j in range(4)] for i in range(N + 1)]
dp[0][-1][-1][1] = 1
for (i, p, q, r, s) in itertools.product(range(N), range(4), range(4), range(4), 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
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 '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())
memo = [{} for _ in range(n + 1)]

def ok(last4):
	if 'AGC' in last4:
		return False
	if 'ACG' in last4:
		return False
	if 'GAC' in last4:
		return False
	if last4[0] == 'A' and last4[2:] == 'GC':
		return False
	if last4[:2] == 'AG' and last4[3] == 'C':
		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 += dfs(cur + 1, last3[1:] + c)
	memo[cur][last3] = ret
	return ret
print(dfs(0, 'TTT') % 1000000007)


A = [0, 1, 4]
G = [0, 1, 4]
C = [0, 1, 4]
T = [0, 1, 4]
AG = [0, 0, 1]
GA = [0, 0, 1]
AC = [0, 0, 1]
AT = [0, 0, 1]
AGG = [0, 0, 0]
ATG = [0, 0, 0]
AGT = [0, 0, 0]
for i in range(2, 100):
	A.append(A[i] + G[i] + C[i] + T[i])
	G.append(A[i] + G[i] + C[i] + T[i] - AC[i])
	C.append(A[i] + G[i] + C[i] + T[i] - AG[i] - GA[i] - AGG[i] - ATG[i] - AGT[i])
	T.append(A[i] + G[i] + C[i] + T[i])
	AG.append(A[i])
	GA.append(G[i])
	AC.append(A[i] - GA[i])
	AT.append(A[i])
	AGG.append(AG[i])
	ATG.append(AT[i])
	AGT.append(AG[i])
N = int(input())
print((A[N] + G[N] + C[N] + T[N]) % (10 ** 9 + 7))


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 re
import functools
N = int(input())
MOD = 10 ** 9 + 7

@functools.lru_cache(maxsize=None)
def dfs(cur, last3):
	if cur == N:
		return 1
	ret = 0
	for c in 'ACGT':
		if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
			ret += dfs(cur + 1, last3[1:] + c)
	return ret % MOD
print(dfs(0, 'TTT'))


import re
N = int(input())
memo_dict = [{} for i in range(N + 1)]

def ok(last4):
	if re.match('.*AGC|.*ACG|A.GC|AG.C|.*GAC', last4):
		return True
	else:
		return False

def dfs(ind, last3):
	if last3 in memo_dict[ind]:
		return memo_dict[ind][last3]
	if ind == N:
		return 1
	cnt = 0
	for c in 'ATGC':
		if not ok(last3 + c):
			cnt += dfs(ind + 1, last3[1:] + c)
			cnt %= 1000000000.0 + 7
	memo_dict[ind][last3] = cnt
	return cnt
print(int(dfs(0, 'TTT')))


n = int(input())
x = 10 ** 9 + 7
sa = [1, 4, 16]
sg = [1, 4, 15]
sc = [1, 4, 14]
st = [1, 4, 16]
for i in range(3, n):
	sa.append(sa[i - 1] + sg[i - 1] + sc[i - 1] + st[i - 1])
	sg.append(sa[i - 1] + sg[i - 1] + (sc[i - 1] - sa[i - 2] + sg[i - 3]) + st[i - 1])
	sc.append(sa[i - 1] - sg[i - 2] + (sg[i - 1] - sa[i - 2] - sa[i - 3] - sa[i - 3]) + sc[i - 1] + (st[i - 1] - sa[i - 3]))
	st.append(sa[i - 1] + sg[i - 1] + sc[i - 1] + st[i - 1])
n = n - 1
print((sa[n] + sg[n] + sc[n] + st[n]) % x)


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

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

def dfs(cur, S):
	if S in memo[cur]:
		return memo[cur][S]
	if cur == N:
		return 1
	count = 0
	for c in 'ACGT':
		if valid(S + c):
			count = (count + dfs(cur + 1, S[1:] + c)) % mod
	memo[cur][S] = count
	return count
print(dfs(0, 'TTT'))


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 functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
MOD = 10 ** 9 + 7

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

@lru_cache(maxsize=None)
def search(n, prev):
	if n == 0:
		return 1
	ret = 0
	for s in ['A', 'G', 'C', 'T']:
		t = (prev + s)[1:]
		if isOk(t):
			ret += search(n - 1, t)
			ret %= MOD
	return ret
print(search(N, 'ZZZZ'))


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

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

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


import re
n = int(input())
MOD = 10 ** 9 + 7
string = 'ACGT'
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('(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())


from collections import defaultdict
MOD = 10 ** 9 + 7
N = int(input())
charactors = ['A', 'G', 'C', 'T']
dp = [defaultdict(int) for _ in range(N + 1)]
dp[0]['ZZZ'] = 1

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


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

def is_agc(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 True
	return False

def dfs(cur, last3):
	if last3 in memo[cur]:
		return memo[cur][last3]
	if cur == N:
		return 1
	ret = 0
	for char in 'ATGC':
		if not is_agc(last3 + char):
			ret = (ret + dfs(cur + 1, last3[1:] + char)) % 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)


N = int(input())
ng = ['agc', 'aagc', 'acgc', 'aggc', 'atgc', 'agac', 'agcc', 'aggc', 'agtc', 'acg', 'gac']
x = {'a': 1, 'g': 1, 'c': 1, 't': 1}
for _ in range(1, N):
	y = dict()
	for (let, num) in x.items():
		for a in ['a', 'c', 'g', 't']:
			if let[-3:] + a in ng or (let[-3:] + a)[-3:] in ng:
				continue
			elif let[-3:] + a in y.keys():
				y[let[-3:] + a] += num
			else:
				y[let[-3:] + a] = num
	x = y
print(sum(x.values()) % (10 ** 9 + 7))


data = int(input())
M = 10 ** 9 + 7
dp = {b: 1 for b in 'ACGT'}
for i in range(data - 1):
	dp_next = {}
	for j in dp:
		for k in 'AGCT':
			elem = j[-3:] + k
			if elem[-3:] in ('AGC', 'GAC', 'ACG') or elem in ('AGGC', 'ATGC', 'ACGC', 'AGTC', 'AGGC'):
				continue
			else:
				dp_next.setdefault(elem, 0)
				dp_next[elem] += dp[j]
	dp = dp_next
print(sum(dp.values()) % M)


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


N = int(input())
chars = 'AGCT'
dp = {}
for c1 in chars:
	for c2 in chars:
		for c3 in chars:
			dp[c1 + c2 + c3] = 1
dp['AGC'] = dp['ACG'] = dp['GAC'] = 0

def isValid(s):
	return not (s[1:] == 'AGC' or s[1:] == 'ACG' or s[1:] == 'GAC' or (s[0] == 'A' and s[3] == 'C' and ('G' in s[1:3])))
for i in range(N - 3):
	dp_new = {k: 0 for k in dp}
	for k in dp:
		for c in chars:
			if isValid(k + c):
				dp_new[k[1:] + c] += dp[k]
	dp = dp_new
print(sum([v for (k, v) in dp.items()]) % 1000000007)


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


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)


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


from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
MOD = 10 ** 9 + 7
S = ['A', 'G', 'C', 'T']
M = set(['AGC', 'GAC', 'ACG'])
for s in S:
	M.add(s + 'AGC')
	M.add(s + 'GAC')
	M.add(s + 'ACG')
	M.add('A' + s + 'GC')
	M.add('AG' + s + 'C')

@lru_cache(maxsize=None)
def search(prev, length):
	if length >= N:
		return 1
	ret = 0
	for s in S:
		T = prev + s
		if not T in M:
			T = T[::-1][:3][::-1]
			ret += search(T, length + 1)
	return ret % MOD
ans = search('', 0)
print(ans)


from itertools import product
n = int(input())
mod = 10 ** 9 + 7
dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(n + 1)]
dp[0][0][0][0] = 1
for t in range(n):
	for (i, j, k, l) in product(range(5), repeat=4):
		if not (l == 0 or (j == 1) & (k == 2) & (l == 3) or (i == 1) & (j == 2) & (l == 3) or (j == 1) & (k == 3) & (l == 2) or (j == 2) & (k == 1) & (l == 3) or (i == 1) & (k == 2) & (l == 3)):
			dp[t + 1][j][k][l] += dp[t][i][j][k] % mod
ans = sum((dp[-1][i][j][k] % mod for (i, j, k) in product(range(1, 5), repeat=3))) % mod
print(ans)


from collections import defaultdict as dd
n = int(input())
(mod, x, y, ans) = (10 ** 9 + 7, {'TTT': 1}, dd(int), 0)

def f(s):
	if s[1:] == 'AG' or s[1:] == 'GA' or s[:2] == 'AG' or (s[0] == 'A' and s[2] == 'G'):
		return True
	else:
		return False

def make(s):
	global y
	for i in 'ATGC':
		if s[1:] == 'AC' and i == 'G' or (f(s) and i == 'C'):
			pass
		else:
			y[s[1:] + i] = (y[s[1:] + i] + x[s]) % mod
for i in range(n):
	for j in x.keys():
		make(j)
	(x, y) = (y, dd(int))
for i in x.values():
	ans = (ans + i) % mod
print(ans)


from collections import defaultdict

def submit():
	n = int(input())
	modp = 10 ** 9 + 7
	chars = ['A', 'C', 'G', 'T']
	modp = 10 ** 9 + 7
	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:
				if k[1] == 'A' and k[2] == 'G' and (c == 'C'):
					continue
				if k[0] == 'A' and k[2] == 'G' and (c == 'C'):
					continue
				if k[1] == 'G' and k[2] == 'A' and (c == 'C'):
					continue
				if k[1] == 'A' and k[2] == 'C' and (c == 'G'):
					continue
				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()


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)
__starting_point()


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)]
dp[0][3][3][3] = 1
for length in range(n):
	for c1 in range(4):
		for c2 in range(4):
			for c3 in range(4):
				if dp[length][c1][c2][c3] == 0:
					continue
				for a in range(4):
					if a == 2 and c1 == 1 and (c2 == 0):
						continue
					if a == 2 and c1 == 0 and (c2 == 1):
						continue
					if a == 1 and c1 == 2 and (c2 == 0):
						continue
					if a == 2 and c1 == 1 and (c3 == 0):
						continue
					if a == 2 and c2 == 1 and (c3 == 0):
						continue
					dp[length + 1][a][c1][c2] += dp[length][c1][c2][c3]
					dp[length + 1][a][c1][c2] %= MOD
ans = 0
for c1 in range(4):
	for c2 in range(4):
		for c3 in range(4):
			ans += dp[n][c1][c2][c3]
			ans %= MOD
print(ans)


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


n = int(input())
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))


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)


import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random

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

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

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)

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

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)

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

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

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)


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

def judge(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(i, last3):
	if last3 in memo[i]:
		return memo[i][last3]
	if i == N:
		return 1
	ret = 0
	for c in 'ACGT':
		if judge(last3 + c):
			ret = (ret + dfs(i + 1, last3[1:] + c)) % mod
	memo[i][last3] = ret
	return ret
print(dfs(0, 'TTT'))


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)


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


import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
mod = 1000000007

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

@lru_cache(maxsize=None)
def dfs(cur, last3):
	if cur == 0:
		return 1
	ret = 0
	for c in 'ACGT':
		if judge(last3 + c):
			ret += dfs(cur - 1, last3[1:] + c)
			ret %= mod
	return ret
n = int(input())
print(dfs(n, 'TTT'))


from functools import lru_cache
from itertools import product
N = int(input())
T = [''.join(t) for t in product(('A', 'C', 'G', 'T'), repeat=3)]

def acg(s):
	return any(['ACG' in s[:i] + s[i + 1:i + 2] + s[i] + s[i + 2:] for i in range(len(s))])

@lru_cache(maxsize=None)
def f(N, s):
	if N == 3 and acg(s):
		return 0
	elif N == 3 and (not acg(s)):
		return 1
	else:
		return sum((f(N - 1, c + s[:2]) for c in ('A', 'C', 'G', 'T') if not acg(c + s)))
ans = sum((f(N, s) for s in T))
print(ans % 1000000007)


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())
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] % mod
	dp = dp2
print(sum(dp.values()) % mod)


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):
		for k in range(4):
			for l 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
				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()


import sys
sys.setrecursionlimit(1000)
n = int(input())
mod = 1000000007
memo = {}

def doit(n, a, b, c):
	if n == 0:
		return 1
	key = (n, a, b, c)
	if not key in memo:
		ret = (doit(n - 1, b, c, 'A') + doit(n - 1, b, c, 'T')) % mod
		if b != 'A' or c != 'C':
			ret = (ret + doit(n - 1, b, c, 'G')) % mod
		if (b != 'A' or c != 'G') and (b != 'G' or c != 'A') and (a != 'A' or c != 'G') and (a != 'A' or b != 'G'):
			ret = (ret + doit(n - 1, b, c, 'C')) % mod
		memo[key] = ret
	return memo[key]
print(doit(n, '', '', ''))


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 = ['AGC', 'ACG', 'GAC', 'A.GC', '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)


N = int(input())
MOD = 10 ** 9 + 7
A = [1] * 64
A[6] = A[9] = A[33] = 0
for _ in range(N - 3):
	B = [0] * 64
	for p in range(256):
		i = p >> 2
		j = p & 63
		b = i == 6 or i == 9 or i == 33 or (j == 6) or (j == 9) or (j == 33) or (p & 207 == 9) or (p & 243 == 33)
		if not b:
			B[j] = (B[j] + A[i]) % MOD
	A[:] = B[:]
res = 0
for a in A:
	res = (res + a) % MOD
print(res)


N = int(input().strip())
M = pow(10, 9) + 7
a = 1
g = 1
ag = 0
agg = 0
agt = 0
atg = 0
ac = 0
at = 0
aa = 0
ga = 0
al = 4
nal = 0
for i in range(N - 1):
	nal = al * 4 % M
	nal = (nal + M - (ag + ac + ga + agg + agt + atg)) % M
	agg = ag
	agt = ag
	atg = at
	ag = a
	aa = a
	at = a
	nac = (a + M - ga) % M
	ga = g
	a = al
	g = (al + M - ac) % M
	ac = nac
	al = nal
print(al)


n = int(input())
dp = [[0] * 16 for i in range(n)]
for j in range(16):
	if j in [1, 6, 9]:
		dp[1][j] = 1
	else:
		dp[1][j] = 1
for i in range(2, n):
	for j in range(16):
		k = j // 4
		dp[i][j] = dp[i - 1][k] + dp[i - 1][k + 4] + dp[i - 1][k + 8] + dp[i - 1][k + 12]
		if j == 1:
			dp[i][j] -= dp[i - 1][8]
		elif j == 6:
			dp[i][j] -= dp[i - 1][1]
		elif j == 9:
			dp[i][j] -= dp[i - 1][2] + dp[i - 2][2] + dp[i - 2][3]
		elif j == 13:
			dp[i][j] -= dp[i - 2][2]
		else:
			continue
count = 0
for j in range(16):
	count += dp[n - 1][j]
print(count % 1000000007)


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)


n = int(input())
(A, C, G, T, M, R) = (0, 1, 2, 3, 10 ** 9 + 7, range(4))
dp = [[[[0] * 4 for 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)


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

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

def dfs(d, last3):
	if d < 0:
		return 1
	if not (d, last3) in memo:
		res = 0
		for c in 'ACGT':
			last4 = last3 + c
			if ok(last4):
				res = (res + dfs(d - 1, last4[-3:])) % MOD
		memo[d, last3] = res
	return memo[d, last3]

def solve(n):
	return dfs(n - 1, '###')
n = int(input())
print(solve(n))


N = int(input())
M = 10 ** 9 + 7
E = 'ACGT'
from collections import defaultdict
ngp = ['AGC?', 'GAC?', 'ACG?', '?AGC', '?GAC', '?ACG', 'A?GC', 'AG?C']
ng = set(['AGC', 'GAC', 'ACG'])
for x in ngp:
	for c in E:
		ng.add(x.replace('?', c))
rs = {'': 1}
for i in range(N):
	nrs = defaultdict(int)
	for (k, v) in rs.items():
		for e in E:
			nk = (k + e)[-4:]
			if not nk in ng:
				nrs[nk[-3:]] += v
	rs = nrs
result = sum(nrs.values()) % M
print(result)


dame = ['AAGC', 'AACG', 'AGAC', 'AGAC', 'AGGC', 'AGGC', 'AGTC', 'ATGC', 'GAGC', 'GGAC', 'CAGC', 'CACG', 'CGAC', 'TAGC', 'TACG', 'TGAC']
memo = {'TTT': 1}
n = int(input())
for i in range(n):
	nmemo = {}
	for c in ['A', 'G', 'C', 'T']:
		for (mk, mv) in memo.items():
			nk = mk + c
			if nk not in dame:
				nk = nk[1:]
				if nk in nmemo:
					nmemo[nk] += mv
				else:
					nmemo[nk] = mv
	memo = nmemo
print(sum(memo.values()) % (10 ** 9 + 7))


from collections import defaultdict
N = int(input())
MOD = 10 ** 9 + 7
nglist = ['?AGC', 'AGC?', 'A?GC', 'AG?C', 'GAC?', '?GAC', 'ACG?', '?ACG']
ng = {}
for t in 'AGCT':
	for n in nglist:
		ng[n.replace('?', t)] = 1
dp = {'TTT': 1}
for i in range(N):
	ans = 0
	_dp = defaultdict(int)
	for (k, v) in dp.items():
		for t in 'AGCT':
			s = k + t
			if s not in ng:
				_dp[s[1:]] += v
				ans = (ans + v) % MOD
	dp = _dp
	if i == N - 1:
		print(ans)


from collections import defaultdict
n = int(input())
m = 10 ** 9 + 7
dp = [defaultdict(int) for i in range(n + 1)]
dp[0][''] = 1

def check(s):
	if 'AGC' in s:
		return False
	for i in range(len(s) - 1):
		l = list(s)
		(l[i], l[i + 1]) = (l[i + 1], l[i])
		t = ''.join(l)
		if 'AGC' in t:
			return False
	return True
for i in range(n):
	for (k, v) in dp[i].items():
		for x in 'AGCT':
			y = k[-3:] + x
			if check(y):
				dp[i + 1][y] += v
print(sum(dp[n].values()) % m)


N = int(input())
d = {}
mod = 10 ** 9 + 7
from itertools import product
import re
for t in product('ATGC', repeat=3):
	s = ''.join(t)
	d[s] = [0] * (N - 2)
	d[s][0] = 0 if s in ['AGC', 'ACG', 'GAC'] else 1
p = re.compile('.AGC|.ACG|.GAC|A.GC|AG.C')
for i in range(N - 3):
	for t in product('ATGC', repeat=3):
		for c in 'ATGC':
			s = ''.join(t) + c
			if p.search(s) == None:
				d[s[1:]][i + 1] = (d[s[1:]][i + 1] + d[s[:-1]][i]) % mod
print(sum([i[-1] for i in d.values()]) % mod)


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

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

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


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


N = int(input())
mod = int(1000000000.0) + 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)


from functools import lru_cache
N = int(input())
mod = 10 ** 9 + 7

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

@lru_cache(maxsize=None)
def dfp(i, seq):
	ret = 0
	if i == N:
		return 1
	for s in ['A', 'G', 'C', 'T']:
		if check(seq + s):
			ret = (ret + dfp(i + 1, seq[1:] + s)) % mod
	return ret
print(dfp(0, 'TTT'))


N = int(input())
ng = ['agc', 'aagc', 'acgc', 'aggc', 'atgc', 'agac', 'agcc', 'aggc', 'agtc', 'acg', 'gac']
c = 0
x = {'a': 1, 'g': 1, 'c': 1, 't': 1}
for _ in range(N - 1):
	y = {}
	for (k, v) in x.items():
		n = k[-3:]
		for s in ['a', 'c', 'g', 't']:
			if n + s in ng or (n + s)[-3:] in ng:
				continue
			if n + s in y.keys():
				y[n + s] += v
			else:
				y[n + s] = v
	x = y
print(sum(x.values()) % 1000000007)


from collections import Counter
mod = 10 ** 9 + 7

def check(s):
	ban = ['AGC', 'ACG', 'GAC', 'AGGC', 'ATGC', 'AGTC']
	for b in ban:
		if b in s:
			return False
	return True
n = int(input())
dp = [Counter() for i in range(n + 1)]
dp[0]['RAN'] = 1
for i in range(n):
	for (key, value) in dp[i].items():
		for c in 'ACTG':
			if check(key + c):
				dp[i + 1][key[1:] + c] += value % mod
print(sum(dp[n].values()) % mod)


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

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

def dfs(cur, last3):
	if last3 in D[cur]:
		return D[cur][last3]
	if cur == N:
		return 1
	res = 0
	for c in 'ACGT':
		if check(last3 + c):
			res = (res + dfs(cur + 1, last3[1:] + c)) % mod
	D[cur][last3] = res
	return res
print(dfs(0, '000'))


from collections import defaultdict
MOD = 10 ** 9 + 7
N = int(input())
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)


mod = 10 ** 9 + 7
n = int(input())
dp = [[0] * 64 for _ in range(n + 1)]
dp[0][0] = 1
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())
mod = 10 ** 9 + 7

def check(s):
	for i in range(4):
		l = list(s)
		if i > 0:
			(l[i - 1], l[i]) = (l[i], l[i - 1])
		if ''.join(l).count('AGC'):
			return False
	else:
		return True
memo = [dict() for _ in range(N)]

def dfp(i, seq):
	if i == N:
		return 1
	if seq in memo[i]:
		return memo[i][seq]
	ret = 0
	for s in ['A', 'G', 'C', 'T']:
		if check(seq + s):
			ret = (ret + dfp(i + 1, seq[1:] + s)) % mod
	memo[i][seq] = ret
	return ret
print(dfp(0, 'TTT'))


def main():
	N = int(input())
	mod = 10 ** 9 + 7
	v = {'TTTT': 1}
	for _ in range(N):
		u = {}
		for (c, k) in v.items():
			c = c[1:]
			for i in 'ACGT':
				t = c + i
				if 'AGC' in t or 'GAC' in t or 'ACG' in t or (t[0] == 'A' and t[2:] == 'GC') or (t[:2] == 'AG' and t[3] == 'C'):
					continue
				u[t] = (u.get(t, 0) + k) % mod
		v = u
	print(sum(v.values()) % mod)
main()


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


from collections import Counter
MOD = 10 ** 9 + 7
N = int(input())
dp = [Counter() for i in range(N + 1)]
dp[0]['TTT'] = 1

def ok(last4):
	bad = ['AGC', 'ACG', 'GAC', 'AGGC', 'ATGC', 'AGTC']
	for b in bad:
		if b in last4:
			return False
	return True
for i in range(N):
	for (key, value) in dp[i].items():
		for c in 'AGCT':
			if ok(key + c):
				dp[i + 1][key[1:] + c] += value % MOD
print(sum(dp[N].values()) % MOD)


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 = 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
for x in range(N):
	for d in R:
		for c in R:
			for b in R:
				for a in range(1, 5):
					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]
			ans %= MOD
print(ans)


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


from functools import lru_cache
N = int(input())
MOD = 10 ** 9 + 7

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

@lru_cache(maxsize=1000)
def dfs(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
	return ret
print(dfs(0, 'TTT'))


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)


def main():
	n = int(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()


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


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

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

def dfs(d, L3):
	if L3 in memo[d]:
		return memo[d][L3]
	if d >= n:
		return 1
	ret = 0
	for L in list('ACGT'):
		L4 = L3 + L
		if check(L4):
			ret += dfs(d + 1, L4[1:])
		memo[d][L3] = ret
	return ret % p
print(dfs(0, 'TTT'))


N = int(input())
DENOM = 10 ** 9 + 7
memo = [{} for i in range(N + 1)]
BASE = 'ACGT'
AGC = 'AGC'

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

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


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


from functools import lru_cache

def check(s):
	bads = ['AGC', 'ACG', 'GAC'] + [b.format(_s) for b in ['AG{}C', 'A{}GC'] for _s in 'ACGT']
	return not any(map(lambda x: x in s, bads))

def solve(string):
	n = int(string)

	@lru_cache(n * 4 ** 3)
	def dfs(pos, last3):
		if pos == n:
			return 1
		ans = 0
		for _s in 'ACGT':
			ans += dfs(pos + 1, last3[1:] + _s) if check(last3 + _s) else 0
		return ans % (10 ** 9 + 7)
	return str(dfs(0, 'TTT'))
print(solve(input()))


n = int(input())
MOD = 1000000000.0 + 7
memo = [{} for _ in range(n + 1)]

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

def sol(cur, s):
	if s in memo[cur]:
		return memo[cur][s]
	if cur == n:
		return 1
	ret = 0
	for c in 'AGCT':
		if ok(s + c):
			ret = int(ret + sol(cur + 1, s[1:] + c)) % MOD
	memo[cur][s] = int(ret)
	return int(ret)
print(sol(0, 'TTT'))


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)


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

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

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


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


n = int(input())
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 = int(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)


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


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


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


(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 ['A', 'C', 'G', 'T']:
		if ok(last3 + c):
			ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
	memo[cur][last3] = ret
	return ret
print(dfs(0, 'TTT'))


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):
		if last3 in memo[digit]:
			return memo[digit][last3]
		if digit == 0:
			return 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'))

def __starting_point():
	N = int(input())
	solve(N)
__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())


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

def C(last4):
	if last4[:3] == 'AGC' or last4[1:] == 'AGC':
		return False
	for i in range(3):
		tmp = list(last4)
		(tmp[i], tmp[i + 1]) = (tmp[i + 1], tmp[i])
		if ''.join(tmp).count('AGC') > 0:
			return False
	return True
a[0]['TTT'] = 1
for i in range(1, n + 1):
	for (k, v) in a[i - 1].items():
		for c in 'ACGT':
			if C(k + c):
				if k[1:] + c in a[i]:
					a[i][k[1:] + c] += v
				else:
					a[i][k[1:] + c] = v
print(sum(a[n].values()) % 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)


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

def ok(sec4):
	for i in range(4):
		tem = list(sec4)
		if i >= 1:
			(tem[i - 1], tem[i]) = (tem[i], tem[i - 1])
		tem2 = ''.join(tem)
		if tem2[:3] == 'AGC' or tem2[1:] == 'AGC':
			return False
	return True

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


N = int(input())
MOD = 10 ** 9 + 7
dp = {b: 1 for b in 'ACGT'}
for _ in range(N - 1):
	dp_new = {}
	for k in dp:
		for b in 'ACGT':
			new = k[-3:] + b
			if new[-3:] in ('AGC', 'GAC', 'ACG') or new in ('AGGC', 'ATGC', 'ACGC', 'AGTC', 'AGGC'):
				continue
			else:
				dp_new.setdefault(new, 0)
				dp_new[new] += dp[k]
	dp = dp_new
print(sum(dp.values()) % MOD)


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	dp = [[0] * 4 if i != 3 else [1] * 4 for i in range(N + 3)]
	MOD = int(1000000000.0) + 7
	for i in range(4, N + 3):
		sum_pre = sum(dp[i - 1]) % MOD
		dp[i][0] = sum_pre
		dp[i][1] = (sum_pre - dp[i - 2][0] - dp[i - 2][2] - dp[i - 3][0] * 3) % MOD
		dp[i][2] = (sum_pre - dp[i - 2][0] + dp[i - 3][2]) % MOD
		dp[i][3] = sum_pre
	print(sum(dp[-1]) % MOD)
main()


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

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 not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
			ret += dfs(cur + 1, last3[1:] + c)
	ret = ret % MOD
	memo[cur][last3] = ret
	return ret
print(dfs(0, 'TTT'))


n = int(input())
s = ['A', 'T', 'G', 'C']
ban = ['AGC', 'ACG', 'GAC']
ban4 = ['ATGC', 'AGTC', 'AGGC']
last3 = [{}, {}]
zl = {}
for i in s:
	for j in s:
		for k in s:
			if i + j + k not in ban:
				last3[0][i + j + k] = 1
				zl[i + j + k] = 0
last3[1] = zl.copy()
for k in range(3, n):
	for i in last3[0]:
		for j in s:
			l = i + j
			if not (l in ban4 or l[1:] in ban):
				last3[1][l[1:]] += last3[0][i]
	last3[0] = last3[1]
	last3[1] = zl.copy()
print(sum(last3[0].values()) % (10 ** 9 + 7))


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)


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
dp = [[0] * 4 for _ in range(N)]
dp[0] = [1, 1, 1, 1]
dp[1] = [4, 4, 4, 4]
for i in range(2, N):
	if i == 2:
		dp[i][0] = dp[i - 1][0] * 4
		dp[i][1] = dp[i - 1][1] * 4 - 2
		dp[i][2] = dp[i - 1][2] * 4 - 1
		dp[i][3] = dp[i - 1][3] * 4
	else:
		dp[i][0] = sum(dp[i - 1])
		dp[i][1] = sum(dp[i - 1]) - dp[i - 2][0] - dp[i - 2][2] - dp[i - 3][0] * 3
		dp[i][2] = sum(dp[i - 1]) - dp[i - 2][0] + dp[i - 3][2]
		dp[i][3] = sum(dp[i - 1])
print(sum(dp[N - 1]) % mod)


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)


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())
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())
a = 3
b = 4
c = 4
d = 1
e = 1
f = 1
g = 4
h = 9
i = 12
j = 22
for x in range(3, n):
	anew = i
	bnew = c + d + e + h
	cnew = b + i
	dnew = c
	enew = g
	fnew = c
	gnew = b + i
	hnew = d + e + f + h + j
	inew = a + b + f + g + i + j
	jnew = a * 2 + d + e + f + (g + h + j) * 2
	a = anew
	b = bnew
	c = cnew
	d = dnew
	e = enew
	f = fnew
	g = gnew
	h = hnew
	i = inew
	j = jnew
Sum = a + b + c + d + e + f + g + h + i + j
print(Sum % (10 ** 9 + 7))


N = int(input())
mod = 10 ** 9 + 7
(a, f) = (1, 1)
l = 2
(b, c, d, e, g, h, i, j, k) = (0, 0, 0, 0, 0, 0, 0, 0, 0)
for p in range(N - 1):
	A = (d + e + i + l) % mod
	B = (a + g) % mod
	C = (b + j) % mod
	D = (b + j) % mod
	E = (a + h) % mod
	F = (c + d + f + k + l) % mod
	G = (b + c + f + j + k) % mod
	H = (a + g + h) % mod
	I = (a + g + h) % mod
	J = h % mod
	K = i % mod
	L = (c + d + 2 * e + 2 * f + 2 * i + k + 2 * l) % mod
	(a, b, c, d, e, f, g, h, i, j, k, l) = (A, B, C, D, E, F, G, H, I, J, K, L)
print((a + b + c + d + e + f + g + h + i + j + k + l) % mod)


from itertools import product
N = int(input())
MOD = 10 ** 9 + 7
D = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 3)]
D[0][3][3][3] = 1
for n in range(1, N + 1):
	for (i, j, k, l) in product(range(4), repeat=4):
		if (i, j, l) == (2, 1, 0) or (i, k, l) == (2, 1, 0) or (i, j, k) == (1, 2, 0) or ((i, j, k) == (2, 0, 1)) or ((i, j, k) == (2, 1, 0)):
			continue
		D[n][i][j][k] += D[n - 1][j][k][l] % MOD
res = 0
for (i, j, k) in product(range(4), repeat=3):
	res += D[N][i][j][k]
	res %= MOD
print(res)


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())
m = 10 ** 9 + 7
a = [1, 4, 16]
g = [1, 4, 15]
c = [1, 4, 14]
t = [1, 4, 16]
for i in range(3, n):
	a.append((a[i - 1] + g[i - 1] + c[i - 1] + t[i - 1]) % m)
	t.append((a[i - 1] + g[i - 1] + c[i - 1] + t[i - 1]) % m)
	g.append((a[i - 1] + g[i - 1] + (c[i - 1] - a[i - 2] + g[i - 3]) + t[i - 1]) % m)
	c.append((a[i - 1] - g[i - 2] + (g[i - 1] - a[i - 2] - 2 * a[i - 3]) + c[i - 1] + (t[i - 1] - a[i - 3])) % m)
n = n - 1
ans = a[n] + g[n] + c[n] + t[n]
print(ans % m)


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


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

def dfs(index, last3):
	if last3 in memo[index]:
		return memo[index][last3]
	if index == N:
		return 1
	c_next = 'AT'
	if last3[1:] != 'AC':
		c_next += 'G'
	if ('AG' in last3) == False:
		if last3[1:] != 'GA':
			if last3[0] + last3[2] != 'AG':
				c_next += 'C'
	count = 0
	for c in c_next:
		count += dfs(index + 1, last3[1:] + c)
		count %= MOD
	memo[index][last3] = count
	return count
print(dfs(0, 'TTT'))


from collections import defaultdict
N = int(input())
dp = [defaultdict(int) for _ in range(N + 1)]
MOD = 10 ** 9 + 7
dp[0]['TTT'] = 1

def ok(last4):
	for i in range(4):
		l = list(last4)
		if i >= 1:
			(l[i - 1], l[i]) = (l[i], l[i - 1])
		if 'AGC' in ''.join(l):
			return False
	return True
for n in range(N):
	for (s, cnt) in dp[n].items():
		for c in 'AGCT':
			ns = s + c
			if ok(ns):
				dp[n + 1][ns[-3:]] = (dp[n + 1][ns[-3:]] + cnt) % MOD
print(sum(dp[N].values()) % MOD)


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

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

def dfs(c, l):
	if l in memo[c]:
		return memo[c][l]
	if c == n:
		return 1
	ret = 0
	for b in 'AGCT':
		if ppp(l + b):
			ret = (ret + dfs(c + 1, l[1:] + b)) % m
	memo[c][l] = ret
	return ret
print(dfs(0, 'TTT'))


from collections import Counter
mod = 1000000007
ng3 = ('AGC', 'ACG', 'GAC')
ng4 = ('AAGC', 'ACGC', 'AGGC', 'ATGC', 'AGAC', 'AGCC', 'AGGC', 'AGTC')

def isok(s):
	if s[-3:] in ng3:
		return False
	if s[-4:] in ng4:
		return False
	return True
N = int(input())
dp = [Counter() for _ in range(N + 1)]
dp[0] = {'': 1}
for n in range(1, N + 1):
	for (s, v) in dp[n - 1].items():
		for c in 'ACGT':
			if isok(s + c):
				dp[n][s[-3:] + c] += v
print(sum(dp[N].values()) % mod)


n = int(input())
seeds = 'ATCG'

def ng(currents):
	v = 'AGC' in currents
	for k in range(max(1, len(currents) - 3), len(currents)):
		v = v or 'AGC' in (currents[:k - 1] + currents[k] + currents[k - 1] + currents[k + 1:])[-4:]
	return v
memo = {}

def f(index, currents):
	key = '%d:%s' % (index, currents[-4:])
	if key not in memo:
		if ng(currents):
			memo[key] = 0
		else:
			memo[key] = 1 if index == n else sum([f(index + 1, currents + s) for s in seeds])
	return memo[key]
print(f(0, '') % int(1000000000.0 + 7))


Mod = 10 ** 9 + 7
f3 = ['AGC', 'GAC', 'ACG']
f4 = ['AGAC', 'AGGC', 'AGCC', 'AGTC'] + ['AAGC', 'AGGC', 'ACGC', 'ATGC']
q = ['A', 'G', 'C', 'T']
d = {}
e = {}
for x in q:
	for y in q:
		for z in q:
			s = x + y + z
			if not s in f3:
				d[s] = 1
				e[s] = 0
n = int(input())
for i in range(n - 3):
	for s in e.keys():
		for c in q:
			t = s + c
			if t[1:] in f3 or t in f4:
				continue
			e[t[1:]] = (e[t[1:]] + d[s]) % Mod
	for s in e.keys():
		d[s] = e[s]
		e[s] = 0
print(sum(d.values()) % Mod)


N = int(input())
dp = {b: 1 for b in 'ACGT'}
for _ in range(N - 1):
	dp_new = {}
	for k in dp:
		for b in 'ACGT':
			n = k[-3:] + b
			if n[-3:] in ('AGC', 'ACG', 'GAC') or n in ('ACGC', 'AGGC', 'ATGC', 'AGCC', 'AGGC', 'AGTC'):
				continue
			elif n in dp_new:
				dp_new[n] += dp[k]
			else:
				dp_new[n] = dp[k]
	dp = dp_new
print(sum(dp.values()) % (10 ** 9 + 7))


N = int(input())
dp = [[0] * 64 for i in range(N - 2)]
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)):
				continue
			dp[i + 1][idx] += dp[i][j]
print(sum(dp[-1]) % mod)


mod = 10 ** 9 + 7
n = int(input())
caps = ['A', 'G', 'C', 'T']
agct = []
for a in caps:
	for b in caps:
		for c in caps:
			if a + b + c not in ['AGC', 'GAC', 'ACG']:
				agct.append(a + b + c)
ngs = set(['AGC', 'GAC', 'ACG', 'AGGC', 'ATGC', 'AAGC', 'AGAC', 'AGTC'])
dic = {}
for trio in agct:
	dic[trio] = 1
for _ in range(n - 3):
	dic2 = {x: 0 for x in agct}
	for trio in agct:
		for cap in caps:
			quad = trio + cap
			if not quad in ngs and (not quad[1:] in ngs):
				dic2[quad[1:]] += dic[trio]
	dic = dic2
print(sum(dic.values()) % mod)


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

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

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


def ok(last4):
	ret = True
	if last4 in ['ATGC', 'AGGC', 'AGTC']:
		ret = False
	elif True in [s in last4 for s in ['AGC', 'ACG', 'GAC']]:
		ret = False
	return ret
N = int(input())
mod = 10 ** 9 + 7
memo = [{} for i in range(N + 1)]

def dfs(current, last3):
	if last3 in memo[current]:
		return memo[current][last3]
	if current == N:
		return 1
	ret = 0
	for c in 'ATGC':
		if ok(last3 + c):
			ret += dfs(current + 1, last3[1:] + c)
			ret %= mod
	memo[current][last3] = ret
	return ret
print(dfs(0, 'TTT'))


n = int(input())
(A, G, C, T, mod, ans) = (0, 1, 2, 3, pow(10, 9) + 7, 0)
dp = [[[[0] * 4 for k in range(4)] for j in range(4)] for i 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 (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 - 1][j][k][l]
						dp[i][k][l][m] %= mod
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 = int(input())
m = 10 ** 9 + 7
dp = [{} for _ in range(n + 1)]

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

def dfs(cur, last3):
	if last3 in dp[cur]:
		return dp[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)
			ret %= m
		dp[cur][last3] = ret
	return ret
print(dfs(0, '___'))


import numpy as np
N = int(input())
dp = np.zeros((N + 1, 5, 5, 5), dtype=np.int64)
p = 10 ** 9 + 7
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 == 3 and (l == 2):
						continue
					if j == 3 and k == 1 and (l == 2):
						continue
					if j == 1 and k == 2 and (l == 3):
						continue
					if i == 1 and k == 3 and (l == 2):
						continue
					if i == 1 and j == 3 and (l == 2):
						continue
					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)


n = int(input())
if n == 3:
	print(61)
	return
mod = pow(10, 9) + 7
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)


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 = {}
dic2 = {}
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)


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

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

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


from itertools import product
n = int(input())
i = 3
ans = 61
dpm = {''.join(k): 1 for k in product('ACGT', repeat=3)}
for k in ('AGC', 'ACG', 'GAC'):
	dpm[k] = 0
MOD = 1000000007
while i < n:
	ndpm = {k: 0 for k in dpm}
	for k in dpm:
		for c in 'ACGT':
			ns = k + c
			if ns[-3:] in ('AGC', 'ACG', 'GAC') or (ns[0] == 'A' and ns[-2:] == 'GC') or (ns[0:2] == 'AG' and ns[-1] == 'C'):
				continue
			ndpm[ns[-3:]] += dpm[k] % MOD
	dpm = ndpm
	i += 1
print(sum(dpm.values()) % MOD)


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)


from collections import defaultdict
n = int(input())
cs = 'ATGC'
ng = ['AGC', 'GAC', 'ACG', 'AGGC', 'ATGC', 'ACGC', 'AGAC', 'AGTC']
mod = 10 ** 9 + 7
d = defaultdict(int)
for c1 in cs:
	for c2 in cs:
		for c3 in cs:
			s = c1 + c2 + c3
			if s not in ng:
				d[s] += 1
for i in range(3, n):
	nd = defaultdict(int)
	for key in d.keys():
		for c in cs:
			cn = key[1:3] + c
			cn4 = key + c
			if cn not in ng and cn4 not in ng:
				nd[cn] = (nd[cn] + d[key]) % mod
	d = nd
print(sum([d[key] for key in d]) % mod)


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

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

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


N = int(input())
black1 = ['AGC', 'GAC', 'ACG']
black2 = ['AAGC', 'ACGC', 'AGGC', 'ATGC', 'AGAC', 'AGCC', 'AGGC', 'AGTC']
memo = [{} for _ in range(N + 1)]

def func(cur, S):
	if S[-3:] in black1:
		return 0
	if S[-4:] in black2:
		return 0
	if S[-3:] in memo[cur]:
		return memo[cur][S[-3:]]
	else:
		if cur == N:
			return 1
		ret = 0
		for s in 'ACGT':
			ret = ret + func(cur + 1, S + s)
		memo[cur][S[-3:]] = ret
		return ret
print(func(0, '____') % (10 ** 9 + 7))


n = int(input())
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):
				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
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)


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):
		for k in range(4):
			for l 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
				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())
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())
t = [0] * (n + 1)
a = [0] * (n + 1)
g = [0] * (n + 1)
ac = [0] * (n + 1)
t[0] = 1
t[1] = 4
t[2] = 16
a[1] = 1
a[2] = 4
g[1] = 1
g[2] = 4
ac[2] = 1
for i in range(3, n + 1):
	t[i] = t[i - 1] * 4 - a[i - 2] - ac[i - 1] - g[i - 2] - a[i - 3] * 3
	a[i] = t[i - 1]
	g[i] = t[i - 1] - ac[i - 1]
	ac[i] = t[i - 2] - g[i - 2]
print(t[n] % (10 ** 9 + 7))


n = int(input())
mask = 63
mod = 10 ** 9 + 7
dp = [[0] * 4 ** 3 for _ in range(n + 1)]
dp[0][63] = 1
for i in range(n):
	for bit in range(4 ** 3):
		for x in range(4):
			nb = bit << 2 & 63 | x
			f = nb == 6 or nb == 9 or nb == 33
			f |= bit & 51 == 2 and x == 1
			f |= bit & 60 == 8 and x == 1
			if f:
				continue
			dp[i + 1][nb] += dp[i][bit]
			dp[i + 1][nb] %= mod
print(sum(dp[-1]) % mod)


N = int(input())
mod = 10 ** 9 + 7
if N < 3:
	print(0)
else:
	dp = [1] * 64
	dp[6] = dp[9] = dp[18] = 0
	for _ in range(N - 3):
		dp_ = [0] * 64
		for i in range(64):
			for j in range(4):
				if j == 2 and i in [1, 4, 5, 7, 13]:
					continue
				ni = (i * 4 + j) % 64
				dp_[ni] += dp[i]
				dp_[ni] %= mod
		dp = dp_
		dp[6] = dp[9] = dp[18] = 0
	print(sum(dp) % mod)


n = int(input())
(A, C, G, T, M) = (0, 1, 2, 3, 10 ** 9 + 7)
r = range
dp = [[[[0] * 4 for 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)


Mod = 10 ** 9 + 7
p = ['XAGC', 'XGAC', 'XACG'] + ['AGCX', 'GACX', 'ACGX'] + ['AGXC', 'AXGC']
q = ['A', 'G', 'C', 'T']
f = []
for s in p:
	for c in q:
		f.append(s.replace('X', c))
r = ['AGC', 'GAC', 'ACG']
d = {}
e = {}
for x in q:
	for y in q:
		for z in q:
			s = x + y + z
			if not s in r:
				d[s] = 1
				e[s] = 0
n = int(input())
for i in range(n - 3):
	for s in e.keys():
		for c in q:
			t = s + c
			if t in f:
				continue
			e[t[1:]] = (e[t[1:]] + d[s]) % Mod
	for s in e.keys():
		d[s] = e[s]
		e[s] = 0
print(sum(d.values()) % Mod)


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

def isOk(last4):
	for i in range(4):
		t = list(last4)
		if i < 3:
			(t[i], t[i + 1]) = (t[i + 1], t[i])
		if ''.join(t).count('AGC') > 0:
			return False
	return True

def dfs(cur, last3):
	if last3 in memo[cur]:
		return memo[cur][last3]
	if cur == N:
		return 1
	ret = 0
	for c in 'ACGT':
		if isOk(last3 + c):
			ret = (dfs(cur + 1, last3[1:] + c) + ret) % (10 ** 9 + 7)
	memo[cur][last3] = ret
	return ret
print(dfs(0, 'TTT'))


import sys
readline = sys.stdin.readline
N = int(readline())
DIV = 10 ** 9 + 7
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
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
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)


import sys
sys.setrecursionlimit(10000000)
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)


(N, m) = (int(input()), 10 ** 9 + 7)
from collections import defaultdict
memo = [defaultdict(int) for i in range(N + 1)]

def ok(last4):
	if 'AGC' in last4:
		return False
	for i in range(3):
		t = list(last4)
		(t[i], t[i + 1]) = (t[i + 1], t[i])
		if 'AGC' in ''.join(t):
			return False
	return True
memo[0]['TTT'] = 1
for i in range(1, N + 1):
	for last3 in memo[i - 1].keys():
		v = memo[i - 1][last3] % m
		tmp = 0
		for c in ['A', 'G', 'T', 'C']:
			if ok(last3 + c):
				memo[i][last3[1:] + c] += v
print(sum(memo[N].values()) % m)


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

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


def solve(string):
	n = int(string)
	dp = [[0] * 4 for _ in range(n)]
	dp[0] = [1] * 4
	for i in range(1, n):
		base = sum(dp[i - 1])
		for j in range(4):
			dp[i][j] = base
		if i >= 2:
			dp[i][1] -= dp[i - 2][0] + dp[i - 2][2]
			dp[i][2] -= dp[i - 2][0]
		if i >= 3:
			dp[i][1] -= dp[i - 3][0] * 3
			dp[i][2] += dp[i - 3][2]
	return str(sum(dp[n - 1]) % (10 ** 9 + 7))
print(solve(input()))


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 = [{} 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'))


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)


import re, functools as f
d = f.lru_cache(None)(lambda n, b: n < 1 or 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(input()), 'TTT'))


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

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

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


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)


import re
N = int(input())
memo = dict()

def is_agc(text):
	if re.match('(.agc|.acg|.gac|a.gc|ag.c)', text):
		return True
	return False

def dfs(s, m):
	if (s, m) in memo:
		return memo[s, m]
	if m == N:
		return 1
	count = 0
	for c in 'acgt':
		t = s + c
		if is_agc(t):
			continue
		count += dfs(t[-3:], m + 1)
	memo[s, m] = count % (10 ** 9 + 7)
	return memo[s, m]
print(dfs('ttt', 0))


def solve():
	MOD = 10 ** 9 + 7
	N = int(input())
	dp = [[0 for _ in range(4)] for _ in range(N + 1)]
	dp[1] = [1, 1, 1, 1]
	for i in range(2, N + 1):
		for j in range(4):
			dp[i][j] += sum(dp[i - 1])
			dp[i][j] %= MOD
		dp[i][1] -= dp[i - 2][0] + dp[i - 2][2]
		dp[i][2] -= dp[i - 2][0]
		if 3 <= i:
			dp[i][1] -= dp[i - 3][0] * 3
			dp[i][2] += dp[i - 3][2]
	ans = sum(dp[N]) % MOD
	print(ans)
solve()


N = int(input())
t = [1, 4, 16]
a = [0, 1, 4]
g = [0, 1, 4]
c = [0, 0, 1]
for i in range(3, N + 1):
	t.append(t[i - 1] * 4 - a[i - 2] - c[i - 1] - g[i - 2] - a[i - 3] * 3)
	a.append(t[i - 1])
	g.append(t[i - 1] - c[i - 1])
	c.append(t[i - 2] - g[i - 2])
print(t[N] % (10 ** 9 + 7))


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

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

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


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)
AG = [0] * n
GA = [0] * n
AC = [0] * n
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]
print((A[-1] + G[-1] + C[-1] + T[-1]) % mod)


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)


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


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

def d(s):
	if 'AGC' in s:
		return False
	for i in range(3):
		l = list(s)
		(l[i], l[i + 1]) = (l[i + 1], l[i])
		if 'AGC' in ''.join(l):
			return False
	return True
m = [{} for i in range(n + 1)]

def f(num, s):
	if s in m[num]:
		return m[num][s]
	if num == n:
		return 1
	ans = 0
	for c in 'ACGT':
		if d(s + c):
			ans = (ans + f(num + 1, s[1:3] + c)) % mod
	m[num][s] = ans
	return ans
print(f(0, 'PPP'))


MOD = 10 ** 9 + 7
N = int(input())
STT = [[1, 0, 2, 0], [1, 3, 4, 5], [6, 0, 2, 0], [1, 0, 10, 0], [6, 10, 7, 8], [1, 0, 9, 0], [1, 10, 4, 5], [6, 10, 2, 0], [1, 10, 2, 0], [6, 10, 2, 0]]
dp = [[0] * 11 for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for st in range(10):
		for ch in range(4):
			dp[i + 1][STT[st][ch]] += dp[i][st]
			dp[i + 1][STT[st][ch]] %= MOD
print(sum(dp[-1][:-1]) % MOD)


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

def check(string):
	if re.match('.*(AGC|GAC|ACG|A.?GC|AG.?C).*', string):
		return False
	return True

def dfs(string='', depth=0):
	if depth == n:
		return 1
	if string in memo[depth]:
		return memo[depth][string]
	cnt = 0
	for i in 'AGCT':
		next_string = string + i
		if check(next_string):
			cnt += dfs(string[-3:] + i, depth + 1)
			cnt %= MOD
	memo[depth][string] = cnt
	return cnt
print(dfs())


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

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

def a(p, q):
	if q in m[p]:
		return m[p][q]
	if p == n:
		return 1
	r = 0
	for i in 'AGCT':
		if f(q + i):
			r = (r + a(p + 1, q[1:] + i)) % w
	m[p][q] = r
	return r
print(a(0, 'WHY'))


from collections import defaultdict
n = int(input())
MOD = 10 ** 9 + 7
s = 'ATGC'
t = ['AGC', 'ACG', 'GAC']
d = [defaultdict(int), {x + y + z: 1 for x in s for y in s for z in s if x + y + z not in t}]
for i in range(4, n + 1):
	a = i % 2
	b = (i - 1) % 2
	d[a] = defaultdict(int)
	for k in d[b]:
		for c in s:
			if 'AGC' not in [k[1:] + c, k[0] + k[2] + c, k[2] + k[1] + c, k[1] + c + k[2], k[0] + k[1] + c]:
				d[a][k[1:] + c] += d[b][k]
				d[a][k[1:] + c] %= MOD
print(sum(d[n % 2].values()) % MOD)


mod = 10 ** 9 + 7
n = int(input())
(A, T, G, C) = ([0] * (n + 1), [0] * (n + 1), [0] * (n + 1), [0] * (n + 1))
(A[1], A[2], A[3]) = (1, 4, 16)
(T[1], T[2], T[3]) = (1, 4, 16)
(C[1], C[2], C[3]) = (1, 4, 14)
(G[1], G[2], G[3]) = (1, 4, 15)
S = [0] * (n + 1)
(S[1], S[2], S[3]) = (4, 16, 61)
for i in range(4, n + 1):
	(A[i], T[i]) = (S[i - 1], S[i - 1])
	C[i] = S[i - 1] - (A[i - 2] + G[i - 2] + A[i - 3] * 3)
	G[i] = S[i - 1] - (A[i - 2] - G[i - 3])
	S[i] = (A[i] + T[i] + C[i] + G[i]) % mod
print(S[-1])


N = int(input())
C = 10 ** 9 + 7
n = 5
num = max(N + 1, 6)
L = [0 for i in range(num)]
X = [0 for i in range(num)]
Y = [0 for i in range(num)]
Z = [0 for i in range(num)]
W = [0 for i in range(num)]
G = [0 for i in range(num)]
L[3] = 61
L[4] = 230
X[3] = 3
X[4] = 12
Y[3] = 4
Y[4] = 16
Z[3] = 4
Z[4] = 15
W[3] = 3
W[4] = 12
W[5] = 48
G[3] = 15
G[4] = 58
while n <= N:
	L[n] = 4 * L[n - 1] - (X[n - 1] + Y[n - 1] + Z[n - 1] + W[n - 1])
	G[n] = L[n - 1] - X[n - 1]
	X[n] = L[n - 2] - G[n - 2]
	Y[n] = L[n - 2]
	Z[n] = L[n - 2] - X[n - 2]
	if n > 5:
		W[n] = L[n - 3] * 3
	n += 1
print(L[N] % C)


import itertools
import functools
L = 'ATGC'
MOD = 10 ** 9 + 7

@functools.lru_cache(maxsize=None)
def rec(s, k):
	if s.count('AGC'):
		return 0
	for i in range(3):
		t = list(s)
		(t[i], t[i + 1]) = (t[i + 1], t[i])
		if ''.join(t).count('AGC'):
			return 0
	if k == 0:
		return 1
	ret = 0
	for x in L:
		ret = (ret + rec(x + s[:3], k - 1)) % MOD
	return ret
N = int(input())
if N == 3:
	print(61)
else:
	ret = 0
	for s in itertools.product(L, repeat=4):
		ret = (ret + rec(''.join(s), N - 4)) % MOD
	print(ret)


n = int(input())
R = range(4)
dp = [[[[0] * 4 for 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))


MOD = 10 ** 9 + 7
N = int(input())
ATCG = 'ATCG'
memo = {}

def dfs(i, last):
	if i == N:
		return 1
	key = (i, last)
	if key in memo:
		return memo[key]
	p = None
	l2 = last[-2:]
	if l2 == 'AC':
		p = 'G'
	elif l2 == 'AG':
		p = 'C'
	elif l2 == 'GA':
		p = 'C'
	elif last == 'AGG' or last == 'ATG' or last == 'AGT':
		p = 'C'
	res = 0
	for c in ATCG:
		if c == p:
			continue
		res += dfs(i + 1, last[1:] + c)
	memo[key] = res = res % MOD
	return res
print(dfs(0, '***'))


import re, copy
import itertools
N = int(input())
pat = '(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)
memo = {}
for s in itertools.product('ATGC', repeat=3):
	if not repattern.search(''.join(s)):
		memo[''.join(s)] = 1
for _ in range(3, N):
	new_memo = {}
	for (k, v) in memo.items():
		for c in 'ATGC':
			if not repattern.search(k + c):
				new_memo[(k + c)[-3:]] = new_memo.get((k + c)[-3:], 0) + v
	memo = new_memo
print(sum(memo.values()) % (10 ** 9 + 7))


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


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 = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(N + 1)]
	A = 1
	G = 2
	C = 3
	T = 4
	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()


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

def resolve():
	N = int(input())
	dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(N + 1)]
	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 i == 1 and j == 2 and (l == 3):
							continue
						if i == 1 and k == 2 and (l == 3):
							continue
						if j == 1 and k == 2 and (l == 3):
							continue
						if j == 2 and k == 1 and (l == 3):
							continue
						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()