Given are an integer N and four characters c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}}, and c_{\mathrm{BB}}.
Here, it is guaranteed that each of those four characters is A or B.
Snuke has a string s, which is initially AB.
Let |s| denote the length of s.
Snuke can do the four kinds of operations below zero or more times in any order:
 - Choose i such that 1 \leq i < |s|, s_{i} = A, s_{i+1} = A and insert c_{\mathrm{AA}} between the i-th and (i+1)-th characters of s.
 - Choose i such that 1 \leq i < |s|, s_{i} = A, s_{i+1} = B and insert c_{\mathrm{AB}} between the i-th and (i+1)-th characters of s.
 - Choose i such that 1 \leq i < |s|, s_{i} = B, s_{i+1} = A and insert c_{\mathrm{BA}} between the i-th and (i+1)-th characters of s.
 - Choose i such that 1 \leq i < |s|, s_{i} = B, s_{i+1} = B and insert c_{\mathrm{BB}} between the i-th and (i+1)-th characters of s.
Find the number, modulo (10^9+7), of strings that can be s when Snuke has done the operations so that the length of s becomes N.

-----Constraints-----
 - 2 \leq N \leq 1000
 - Each of c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}}, and c_{\mathrm{BB}} is A or B.

-----Input-----
Input is given from Standard Input in the following format:
N
c_{\mathrm{AA}}
c_{\mathrm{AB}}
c_{\mathrm{BA}}
c_{\mathrm{BB}}

-----Output-----
Print the number, modulo (10^9+7), of strings that can be s when Snuke has done the operations so that the length of s becomes N.

-----Sample Input-----
4
A
B
B
A

-----Sample Output-----
2

 - There are two strings that can be s when Snuke is done: ABAB and ABBB.

Difficulty: HARD

Starter code:

Solutions:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().rstrip().split()

def S():
	return sys.stdin.readline().rstrip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
n = I()
c1 = S()
c2 = S()
c3 = S()
c4 = S()
if n <= 3:
	print(1)
	return
if c2 == 'A':
	if c1 == 'A':
		print(1)
	else:
		dp = [[0] * 2 for _ in range(n - 3)]
		dp[0][0] = 1
		dp[0][1] = 1
		for i in range(1, n - 3):
			dp[i][0] = sum(dp[i - 1]) % mod
			dp[i][1] = dp[i - 1][0]
		if c3 == 'A':
			print(sum(dp[-1]) % mod)
		else:
			print(pow(2, n - 3, mod))
elif c4 == 'B':
	print(1)
else:
	dp = [[0] * 2 for _ in range(n - 3)]
	dp[0][0] = 1
	dp[0][1] = 1
	for i in range(1, n - 3):
		dp[i][0] = sum(dp[i - 1]) % mod
		dp[i][1] = dp[i - 1][0]
	if c3 == 'B':
		print(sum(dp[-1]) % mod)
	else:
		print(pow(2, n - 3, mod))


N = int(input())
c1 = str(input())
c2 = str(input())
c3 = str(input())
c4 = str(input())
c = c1 + c2 + c3 + c4
if c in ['AAAA', 'AAAB', 'AABA', 'AABB', 'ABAB', 'BBAB', 'ABBB', 'BBBB']:
	print(1)
if c in ['ABAA', 'BABA', 'BABB', 'BBAA']:
	if N == 2 or N == 3:
		print(1)
	else:
		ans = 1
		for dummy in range(N - 3):
			ans *= 2
			ans = ans % (10 ** 9 + 7)
		print(ans)
if c in ['BAAA', 'BAAB', 'ABBA', 'BBBA']:
	ans = [1, 1]
	if N == 2 or N == 3:
		print(1)
	else:
		for dummy in range(N - 3):
			ans += [(ans[-1] + ans[-2]) % (10 ** 9 + 7)]
		print(ans[-1])


N = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
MOD = 10 ** 9 + 7
if N <= 3:
	print(1)
	return
if aa == ab == 'A' or ab == bb == 'B':
	print(1)
	return
if aa + ab + ba == 'BAB' or ab + ba + bb == 'BAA':
	print(pow(2, N - 3, MOD))
	return
pp = p = n = 1
for i in range(N - 3):
	pp = p
	p = n
	n = (pp + p) % MOD
print(n)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
(caa, cab, cba, cbb) = [input() for _ in range(4)]
M = 10 ** 9 + 7
done = False

def swap(w):
	if w == 'A':
		return 'B'
	else:
		return 'A'
if cab == 'B':
	(caa, cab, cba, cbb) = (swap(caa), swap(cab), swap(cba), swap(cbb))
	done = True
if not done and caa == 'A' or (done and cbb == 'A'):
	ans = 1
elif n == 2:
	ans = 1
elif cba == 'B':
	ans = pow(2, n - 3, M)
else:

	def sub(n):
		dp0 = [0] * (n - 2)
		dp1 = [0] * (n - 2)
		dp1[0] = 1
		for i in range(1, n - 2):
			dp0[i] = dp1[i - 1]
			dp1[i] = dp1[i - 1] + dp0[i - 1]
			dp0[i] %= M
			dp1[i] %= M
		ans = dp0[n - 3] + dp1[n - 3]
		ans %= M
		return ans
	ans = sub(n) % M
print(ans % M)


U = 1010
mod = 10 ** 9 + 7
fact = [1] * (U + 1)
fact_inv = [1] * (U + 1)
for i in range(1, U + 1):
	fact[i] = fact[i - 1] * i % mod
fact_inv[U] = pow(fact[U], mod - 2, mod)
for i in range(U, 0, -1):
	fact_inv[i - 1] = fact_inv[i] * i % mod

def perm(n, k):
	if k < 0 or k > n:
		return 0
	z = fact[n]
	z *= fact_inv[n - k]
	z %= mod
	return z

def comb(n, k):
	if k < 0 or k > n:
		return 0
	z = fact[n]
	z *= fact_inv[k]
	z *= fact_inv[n - k]
	z %= mod
	return z

def poly_mul(P, Q):
	n = len(P)
	(d, c) = Q[0]
	if d:
		c = 0
	else:
		Q = Q[1:]
	for i in range(n - 1, -1, -1):
		P[i] *= c
		P[i] %= mod
		for (j, b) in Q:
			if j > i:
				break
			P[i] += P[i - j] * b
			P[i] %= mod

def poly_div(P, Q):
	n = len(P)
	(d, c) = Q[0]
	Q = Q[1:]
	inv = pow(c, mod - 2, mod)
	for i in range(n):
		for (j, b) in Q:
			if j > i:
				break
			P[i] -= P[i - j] * b
			P[i] %= mod
		P[i] *= inv
		P[i] %= mod
n = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
if aa == 'A' and ab == 'A':
	print(1)
	return
if bb == 'B' and ab == 'B':
	print(1)
	return
ans = 0
if ab == 'A' and ba == 'A' or (ab == 'B' and ba == 'B'):
	for i in range(n):
		for j in range(n):
			if i + j != n - 1:
				continue
			ans += comb(i - 1, j)
			ans %= mod
else:
	F = [0] * 1010
	F[1] = 1
	F[2] = -1
	poly_div(F, ((0, 1), (1, -2)))
	ans = F[n - 1]
ans %= mod
print(ans)


def inv_mod(a, p=10 ** 9 + 7):
	p = abs(p)
	a %= p
	stack = []
	p0 = p
	while a > 1:
		(d, a, p) = (p // a, p % a, a)
		stack.append(d)
	(x, y) = (1, 0)
	while stack:
		d = stack.pop()
		(x, y) = (y - d * x, x)
	return x % p0
MOD = 10 ** 9 + 7
inpl = lambda : list(map(int, input().split()))
N = int(input())
a = ord(input()) - ord('A')
b = ord(input()) - ord('A')
c = ord(input()) - ord('A')
d = ord(input()) - ord('A')
if N == 2 or N == 3:
	print(1)
	return
if b == 0:
	(a, b, c, d) = (1 - d, 1 - b, 1 - c, 1 - a)
if d == 1:
	print(1)
elif c == 0:
	print(pow(2, N - 3, MOD))
else:
	n = N - 3
	cur = 1
	ans = cur
	for k in range((n + 1) // 2):
		cur *= (n - 2 * k) * (n - 2 * k + 1) * inv_mod(k + 1) * inv_mod(n - k + 1)
		cur %= MOD
		ans += cur
		ans %= MOD
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.readline().rstrip().encode()

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
inf = 10 ** 16
md = 10 ** 9 + 7
from functools import lru_cache

@lru_cache(maxsize=None)
def f(a):
	if a == 1 or a == 0:
		return 1
	return (f(a - 1) + f(a - 2)) % md

def solve():
	if n < 4:
		return 1
	if ab == 'A':
		if aa == 'A':
			return 1
		if ba == 'A':
			return f(n - 2)
		return pow(2, n - 3, md)
	else:
		if bb == 'B':
			return 1
		if ba == 'B':
			return f(n - 2)
		return pow(2, n - 3, md)
n = II()
aa = SI()
ab = SI()
ba = SI()
bb = SI()
print(solve())


MOD = 10 ** 9 + 7

def solve(n, c_aa, c_ab, c_ba, c_bb):
	if n <= 3:
		return 1
	if c_ab == 'B':
		if c_bb == 'A':
			c_aa = 'B'
		else:
			c_aa = 'A'
		if c_ba == 'A':
			c_ba = 'B'
		else:
			c_ba = 'A'
	if c_aa == 'A':
		return 1
	if c_ba == 'A':
		dp = [[0, 0] for _ in range(n - 2)]
		dp[0][0] = 1
		for i in range(1, n - 2):
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
			dp[i][1] = dp[i - 1][0]
		return (dp[-1][0] + dp[-1][1]) % MOD
	return pow(2, n - 3, MOD)

def main():
	n = int(input())
	c_aa = input()
	c_ab = input()
	c_ba = input()
	c_bb = input()
	res = solve(n, c_aa, c_ab, c_ba, c_bb)
	print(res)

def test():
	assert solve(4, 'A', 'B', 'B', 'A') == 2
	assert solve(1000, 'B', 'B', 'B', 'B') == 1

def __starting_point():
	test()
	main()
__starting_point()


mod = 10 ** 9 + 7
n = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
if ab == 'A' and aa == 'A':
	print(1)
	return
if ab == 'B' and bb == 'B':
	print(1)
	return
if ab == 'A' and ba == 'A' or (ab == 'B' and ba == 'B'):
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(n - 1):
		for j in range(2, n + 1):
			if j + i > n:
				break
			dp[i + j] += dp[i]
			dp[i + j] %= mod
	print(dp[n])
	return
if True:
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(n - 1):
		for j in range(2, n + 1):
			if j + i > n:
				break
			dp[i + j] += dp[i] * (j - 1)
			dp[i + j] %= mod
	ans = 0
	for i in range(n - 1):
		ans += dp[i]
		ans %= mod
	print(ans)


mod = 10 ** 9 + 7

def fibo(n):
	if n == 1:
		return 1
	if n == 2:
		return 2
	f1 = 1
	f2 = 2
	for _ in range(n - 2):
		(f1, f2) = (f2, f1 + f2)
		f2 %= mod
	return f2

def main():
	n = int(input())
	Caa = input()
	Cab = input()
	Cba = input()
	Cbb = input()
	if n == 2 or n == 3:
		return 1
	if Cab == 'A':
		if Caa == 'A':
			return 1
		if Cba == 'A':
			return fibo(n - 2)
		return pow(2, n - 3, mod)
	elif Cab == 'B':
		if Cbb == 'B':
			return 1
		elif Cba == 'B':
			return fibo(n - 2)
		return pow(2, n - 3, mod)
print(main())


import sys
n = int(input())
caa = input()
cab = input()
cba = input()
cbb = input()
MOD = 10 ** 9 + 7
if n == 2:
	print(1)
	return
dpa = [0] * n
dpb = [0] * n
dpa[0] = 1
for i in range(1, n - 1):
	dpa[i] = (dpa[i - 1] + dpb[i - 1]) % MOD
	dpb[i] = dpa[i - 1]
ans = dpa[n - 2]
if cab == 'A':
	if caa == 'A':
		print(1)
	elif cba == 'B':
		print(pow(2, n - 3, MOD))
	else:
		print(ans)
elif cbb == 'B':
	print(1)
elif cba == 'A':
	print(pow(2, n - 3, MOD))
else:
	print(ans)


mod = 10 ** 9 + 7
n = int(input())
(a, b, c, d) = [input() for i in range(4)]
l = ['B', 'A']
if b == 'A':
	b = l[not b == 'A']
	c = l[not c == 'A']
	(a, d) = (l[not d == 'A'], l[not a == 'A'])
if n < 4:
	print(1)
elif d == 'B':
	print(1)
elif c == 'A':
	print(pow(2, n - 3, mod))
else:
	l = [1, 1]
	for i in range(n):
		l.append((l[-1] + l[-2]) % mod)
	print(l[n - 2])


P = 10 ** 9 + 7
N = int(input())
AA = input()
AB = input()
BA = input()
BB = input()
TT = [0] * (N + 1)
TT[0] = 1
TT[1] = 1
for i in range(2, N + 1):
	TT[i] = TT[i - 1] * i % P
if AB == 'A' and AA == 'A':
	print(1)
elif AB == 'B' and BB == 'B':
	print(1)
elif N <= 3:
	print(1)
elif AB == 'A' and AA == 'B':
	if BA == 'A':
		ans = 0
		for i in range(N // 2):
			ans += TT[N - 2 - i] * pow(TT[N - 2 - 2 * i], P - 2, P) % P * pow(TT[i], P - 2, P) % P
			ans %= P
		print(ans)
	else:
		print(pow(2, N - 3, P))
elif AB == 'B' and BB == 'A':
	if BA == 'B':
		ans = 0
		for i in range(N // 2):
			ans += TT[N - 2 - i] * pow(TT[N - 2 - 2 * i], P - 2, P) % P * pow(TT[i], P - 2, P) % P
			ans %= P
		print(ans)
	else:
		print(pow(2, N - 3, P))


from math import factorial
n = int(input())
AA = input()
AB = input()
BA = input()
BB = input()
mod = pow(10, 9) + 7
if n == 2 or n == 3:
	print(1)
	return
if AB == 'B':
	if BB == 'B':
		print(1)
	elif BA == 'B':
		count = 0
		n -= 2
		m = 0
		while n >= 0:
			count += factorial(n + m) // (factorial(n) * factorial(m))
			count %= mod
			n -= 2
			m += 1
		print(count)
	else:
		print(pow(2, n - 3, mod))
elif AA == 'A':
	print(1)
elif BA == 'A':
	count = 0
	n -= 2
	m = 0
	while n >= 0:
		count += factorial(n + m) // (factorial(n) * factorial(m))
		count %= mod
		n -= 2
		m += 1
	print(count)
else:
	print(pow(2, n - 3, mod))


mod = 10 ** 9 + 7

def main():
	n = int(input())
	caa = input()
	cab = input()
	cba = input()
	cbb = input()
	if n <= 3:
		print(1)
		return
	if cab == caa == 'A' or cab == cbb == 'B':
		print(1)
		return
	if cab == cba:
		dp = [0] * n
		dp[1] = 1
		for i in range(n - 2):
			dp[i + 2] = (dp[i] + dp[i + 1]) % mod
		print(dp[n - 1])
		return
	print(pow(2, n - 3, mod))
main()


import sys
from sys import stdin
mod = 10 ** 9 + 7
N = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
dp = [1, 0]
for i in range(N - 3):
	ndp = [0, 0]
	ndp[0] = (dp[0] + dp[1]) % mod
	ndp[1] = dp[0]
	dp = ndp
ANSC = sum(dp) % mod
if N == 2:
	print(1)
	return
if ab == 'A':
	if aa == 'A':
		print(1)
		return
	elif ba == 'B':
		print(pow(2, N - 3, mod))
		return
	else:
		print(ANSC)
		return
elif bb == 'B':
	print(1)
	return
elif ba == 'A':
	print(pow(2, N - 3, mod))
	return
else:
	print(ANSC)
	return


Q = 10 ** 9 + 7

def calc(N):
	(x, y) = (1, 1)
	t = 2
	while t < N:
		(x, y) = (y, (x + y) % Q)
		t += 1
	return x

def main():
	N = int(input())
	CAA = input()
	CAB = input()
	CBA = input()
	CBB = input()
	if N == 2:
		print(1)
		return
	S = CAA + CAB + CBA + CBB
	A = 'A'
	B = 'B'
	Power = ['ABAA', 'BABA', 'BABB', 'BBAA']
	Fibo = ['ABBA', 'BAAA', 'BBBA', 'BAAB']
	if S in Power:
		print(pow(2, N - 3, Q))
	elif S in Fibo:
		print(calc(N))
	else:
		print(1)

def __starting_point():
	main()
__starting_point()


n = int(input())
c = [input() for i in range(4)]
if n == 2 or n == 3:
	print(1)
	return
mod = 10 ** 9 + 7
if c[1] == 'A' and c[0] == 'A':
	print(1)
	return
if c[1] == 'B' and c[3] == 'B':
	print(1)
	return
if c[1] == 'A' and c[2] == 'B':
	print(pow(2, n - 3, mod))
	return
if c[1] == 'B' and c[2] == 'A':
	print(pow(2, n - 3, mod))
	return
dp = [1, 1]
for i in range(n):
	dp.append((dp[-1] + dp[-2]) % mod)
print(dp[n - 2])


n = int(input())
c = [input() for _ in range(4)]
mod = pow(10, 9) + 7
d = dict()
d['AA'] = c[0]
d['AB'] = c[1]
d['BA'] = c[2]
d['BB'] = c[3]
now = set()
now.add('AB')
dp = [1] * max(n + 1, 4)
for i in range(1, 4):
	x = list(now)
	now0 = set()
	for y in x:
		for j in range(i):
			z = list(y)
			z.insert(j + 1, d[z[j] + z[j + 1]])
			now0.add(''.join(z))
	dp[i] = len(list(now0))
	now = now0
if dp[3] == 3:
	for i in range(4, max(n + 1, 4)):
		dp[i] = dp[i - 1] + dp[i - 2]
		dp[i] %= mod
if dp[3] == 4:
	for i in range(4, max(n + 1, 4)):
		dp[i] = 2 * dp[i - 1]
		dp[i] %= mod
ans = dp[n - 2]
print(ans)


def Factorial(x, mod):
	res = 1
	for i in range(1, x + 1):
		res *= i
		res %= mod
	return res

def Fib(N, mod):
	L = [0] * N
	L[0] = 1
	L[1] = 1
	for i in range(2, N):
		L[i] = (L[i - 1] + L[i - 2]) % mod
	return L[-1]

def main():
	debug = False
	import sys
	mod = 10 ** 9 + 7
	if debug:
		N = 5
		I = input()
		Caa = I[0]
		Cab = I[1]
		Cba = I[2]
		Cbb = I[3]
	else:
		N = int(sys.stdin.readline())
		Caa = sys.stdin.readline().strip()
		Cab = sys.stdin.readline().strip()
		Cba = sys.stdin.readline().strip()
		Cbb = sys.stdin.readline().strip()
	Cs = Caa + Cab + Cba + Cbb
	if debug:
		dic = {'AA': Caa, 'AB': Cab, 'BA': Cba, 'BB': Cbb}
		s = 'AB'

		def dfs(s):
			if len(s) == N:
				st.add(s)
				return
			for i in range(len(s) - 1):
				dfs(s[:i + 1] + dic[s[i:i + 2]] + s[i + 1:])
		st = set()
		dfs(s)
		print(len(st))
	if N == 2:
		return 1
	if Cab == 'A' and Caa == 'A':
		return 1
	if Cab == 'B' and Cbb == 'B':
		return 1
	if Cs in ['ABBA', 'BAAA', 'BAAB', 'BBBA']:
		return Fib(N - 1, mod)
	if Cs in ['ABAA', 'BABA', 'BABB', 'BBAA']:
		return pow(2, N - 3, mod)
print(main())


(N,) = list(map(int, input().split()))
X = dict()
X['AA'] = input().strip()
X['AB'] = input().strip()
X['BA'] = input().strip()
X['BB'] = input().strip()
ss = set(['AB'])
R = [1]
for i in range(4):
	nss = set()
	for t in ss:
		for j in range(i + 1):
			nt = t[:j + 1] + X[t[j:j + 2]] + t[j + 1:]
			nss.add(nt)
	ss = nss
	R.append(len(ss))
MOD = 10 ** 9 + 7
if N - 2 < 5:
	print(R[N - 2])
elif R[-3] + R[-2] == R[-1]:
	for _ in range(N - 2 - 4):
		R.append((R[-1] + R[-2]) % MOD)
	print(R[-1])
elif R[-2] == R[-1]:
	print(R[-1])
elif R[-2] * 2 == R[-1]:
	for _ in range(N - 2 - 4):
		R.append(R[-1] * 2 % MOD)
	print(R[-1])


import sys
input = sys.stdin.readline
n = int(input())
caa = input().rstrip()
cab = input().rstrip()
cba = input().rstrip()
cbb = input().rstrip()
INF = 10 ** 9 + 7

def modinv(a, m):
	b = m
	(x, lastx) = (0, 1)
	(y, lasty) = (1, 0)
	while not b == 0:
		q = a // b
		(a, b) = (b, a % b)
		(x, lastx) = (lastx - q * x, x)
		(y, lasty) = (lasty - q * y, y)
	return lastx % m
if n == 2:
	print(1)
	return
if cab == 'A' and caa == 'A':
	ans = 1
if cab == 'B' and cbb == 'B':
	ans = 1
if cab == 'A' and caa == 'B':
	if cba == 'B':
		ans = pow(2, n - 3, INF)
	else:
		ans = 0
		x = 0
		c = 1
		while n - 2 - x >= x:
			ans = (ans + c) % INF
			c = c * (n - 3 - 2 * x) * (n - 2 - 2 * x) * modinv(x + 1, INF) * modinv(n - 2 - x, INF)
			c = c % INF
			x += 1
if cab == 'B' and cbb == 'A':
	if cba == 'A':
		ans = pow(2, n - 3, INF)
	else:
		ans = 0
		x = 0
		c = 1
		while n - 2 - x >= x:
			ans = (ans + c) % INF
			c = c * (n - 3 - 2 * x) * (n - 2 - 2 * x) * modinv(x + 1, INF) * modinv(n - 2 - x, INF)
			c = c % INF
			x += 1
print(ans)


import sys
from math import factorial
MOD = 10 ** 9 + 7

def combInit(n):
	fact = [1]
	finv = [1]
	for i in range(1, n + 1):
		fact.append(fact[i - 1] * i % MOD)
		finv.append(pow(fact[i], MOD - 2, MOD))
	return [fact, finv]

def comb(n, k, f):
	if n < k:
		return 0
	elif n < 0 or k < 0:
		return 0
	else:
		return f[0][n] * (f[1][k] * f[1][n - k] % MOD) % MOD
N = int(input())
caa = input()
cab = input()
cba = input()
cbb = input()
f = combInit(1000)
if N <= 3:
	print(1)
	return
if cab == 'A':
	if caa == 'A':
		res = 1
	elif caa == 'B':
		if cba == 'A':
			res = 1
			for i in range(1, (N - 2) // 2 + 1):
				nt = N - 2 - i
				t = comb(nt, i, f)
				res = (res + t) % MOD
		elif cba == 'B':
			res = pow(2, N - 3, MOD)
elif cab == 'B':
	if cbb == 'B':
		res = 1
	elif cbb == 'A':
		if cba == 'B':
			res = 1
			for i in range(1, (N - 2) // 2 + 1):
				nt = N - 2 - i
				t = comb(nt, i, f)
				res = (res + t) % MOD
		elif cba == 'A':
			res = pow(2, N - 3, MOD)
print('{}'.format(res))


class comb:
	F = [1, 1]
	Fi = [1, 1]
	I = [0, 1]

	def __init__(self, num, mod):
		self.MOD = mod
		for i in range(2, num + 1):
			self.F.append(self.F[-1] * i % mod)
			self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
			self.Fi.append(self.Fi[-1] * self.I[i] % mod)

	def com(self, n, k):
		if n < k:
			return 0
		if n < 0 or k < 0:
			return 0
		return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD
N = int(input())
caa = input()
cab = input()
cba = input()
cbb = input()
MOD = 10 ** 9 + 7
if cab == 'A' and caa == 'A' or (cab == 'B' and cbb == 'B'):
	print(1)
	return
com = comb(N, MOD)
if cab == cba:
	ans = 0
	for n in range((N - 2) // 2 + 1):
		m = N - 2 - n
		if m < n:
			continue
		ans = (ans + com.com(m, n)) % MOD
	print(ans)
	return
if N <= 3:
	print(1)
else:
	ans = pow(2, N - 3, MOD)
	print(ans)


n = int(input())
C = [0 if input() == 'A' else 1 for _ in range(4)]
mod = 10 ** 9 + 7
l = 10 ** 5
fac = [1] * l
facr = [1] * l
for i in range(l - 1):
	fac[i + 1] = fac[i] * (i + 1) % mod
facr[l - 1] = pow(fac[l - 1], mod - 2, mod)
for i in range(1, l)[::-1]:
	facr[i - 1] = facr[i] * i % mod

def combi(N: int, K: int) -> int:
	if N < K:
		return 0
	return fac[N] * facr[N - K] % mod * facr[K] % mod
if n == 3 or n == 2:
	print(1)
	return
if C[1] == 1 and C[3] == 1:
	print(1)
	return
if C[1] == 0 and C[0] == 0:
	print(1)
	return
if C[1] == C[2] == 1 and C[3] == 0:
	ans = 0
	for i in range(1, n // 2 + 1):
		ans += combi(n - i - 1, i - 1)
		ans %= mod
	print(ans)
	return
if C[0] == 1 and C[1] == C[2] == 0:
	ans = 0
	for i in range(1, n // 2 + 1):
		ans += combi(n - i - 1, i - 1)
		ans %= mod
	print(ans)
	return
if C[0] == C[2] == 1 and C[1] == 0:
	print(pow(2, n - 3, mod))
	return
if C[1] == 1 and C[2] == C[3] == 0:
	print(pow(2, n - 3, mod))
	return


n = int(input())
aa = input().lower()
ab = input().lower()
ba = input().lower()
bb = input().lower()
mod = 10 ** 9 + 7
if n < 4:
	print(1)
	return
if ab == 'b':
	if bb == 'b':
		print(1)
	elif ba == 'a':
		print(pow(2, n - 3, mod))
	else:
		dp_a = dp_b = 1
		for _ in range(n - 4):
			(dp_a, dp_b) = (dp_b, (dp_a + dp_b) % mod)
		print((dp_a + dp_b) % mod)
elif aa == 'a':
	print(1)
elif ba == 'b':
	print(pow(2, n - 3, mod))
else:
	dp_a = dp_b = 1
	for _ in range(n - 4):
		(dp_a, dp_b) = (dp_b, (dp_a + dp_b) % mod)
	print((dp_a + dp_b) % mod)


n = int(input())
c = [input() for _ in range(4)]
mod = 10 ** 9 + 7
const = [['A', 'A', 'A', 'A'], ['A', 'A', 'A', 'B'], ['A', 'A', 'B', 'A'], ['A', 'A', 'B', 'B'], ['A', 'B', 'A', 'B'], ['A', 'B', 'B', 'B'], ['B', 'B', 'A', 'B'], ['B', 'B', 'B', 'B']]
if c in const:
	print(1)
	return
exps = [['A', 'B', 'A', 'A'], ['B', 'A', 'B', 'A'], ['B', 'A', 'B', 'B'], ['B', 'B', 'A', 'A']]
if c in exps:
	print(pow(2, max(n - 3, 0), mod))
	return

def fib(n, acm1=1, acm2=1):
	if not n:
		return acm2
	return fib(n - 1, acm2, acm1 + acm2)
print(fib(max(n - 3, 0)) % mod)


import copy
N = int(input())

def power_func(a, n, p):
	bi = str(format(n, 'b'))
	res = 1
	for i in range(len(bi)):
		res = res * res % p
		if bi[i] == '1':
			res = res * a % p
	return res
mod = 10 ** 9 + 7
c = [0] * 4
for i in range(4):
	c[i] = str(input())
if c[0] == 'A' and c[1] == 'A':
	ans = 1
elif c[1] == 'B' and c[3] == 'B':
	ans = 1
elif c in [['B', 'A', 'A', 'A'], ['B', 'A', 'A', 'B'], ['A', 'B', 'B', 'A'], ['B', 'B', 'B', 'A']]:
	if N == 2 or N == 3:
		ans = 1
	else:
		N -= 3
		one = 1
		two = 1
		while N != 0:
			x = one
			one += two
			one %= mod
			two = x
			N -= 1
		ans = one
elif N == 2 or N == 3:
	ans = 1
else:
	ans = power_func(2, N - 3, mod)
print(ans)


MOD = 10 ** 9 + 7

def main():
	n = int(input())
	c = {}
	c['AA'] = input()
	c['AB'] = input()
	c['BA'] = input()
	c['BB'] = input()
	if n <= 3:
		print(1)
	elif c['AB'] == 'A':
		if c['AA'] == 'A':
			print(1)
		elif c['BA'] == 'A':
			dp = [[0] * 2 for _ in range(n - 2)]
			dp[0][0] = 1
			for i in range(1, n - 2):
				dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
				dp[i][1] = dp[i - 1][0]
			print((dp[-1][0] + dp[-1][1]) % MOD)
		else:
			print(pow(2, n - 3, MOD))
	elif c['BB'] == 'B':
		print(1)
	elif c['BA'] == 'B':
		dp = [[0] * 2 for _ in range(n - 2)]
		dp[0][0] = 1
		for i in range(1, n - 2):
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
			dp[i][1] = dp[i - 1][0]
		print((dp[-1][0] + dp[-1][1]) % MOD)
	else:
		print(pow(2, n - 3, MOD))

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(2 * 10 ** 5 + 1)
input = lambda : sys.stdin.readline().strip()
n = int(input())
a = input()
b = input()
c = input()
d = input()
mod = 10 ** 9 + 7
e = 1
f = 1
for i in range(n - 3):
	g = (e + f) % mod
	e = f
	f = g
if n <= 3:
	print(1)
elif b == 'B':
	if d == 'B':
		print(1)
	elif c == 'A':
		print(pow(2, n - 3, mod))
	else:
		print(f)
elif a == 'A':
	print(1)
elif c == 'B':
	print(pow(2, n - 3, mod))
else:
	print(f)


(N, *S) = open(0).read().split()
N = int(N)
S = ''.join(S)
mod = 10 ** 9 + 7
if N == 2:
	print(1)
elif S in ['ABAA', 'BABA', 'BABB', 'BBAA']:
	print(pow(2, N - 3, mod))
elif S in ['ABBA', 'BAAA', 'BAAB', 'BBBA']:
	a = b = 1
	for _ in range(N - 3):
		(a, b) = (b, a + b)
		a %= mod
		b %= mod
	print(b)
else:
	print(1)


n = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
MOD = 10 ** 9 + 7
if n == 2:
	print(1)
	return
if ab == 'A':
	if aa == 'A':
		print(1)
		return
	elif ba == 'A':
		dp = [[0] * 2 for _ in range(n + 1)]
		dp[0][0] = 1
		for i in range(n):
			dp[i + 1][0] = (dp[i][0] + dp[i][1]) % MOD
			dp[i + 1][1] = dp[i][0] % MOD
		print((dp[n - 3][0] + dp[n - 3][1]) % MOD)
		return
	else:
		ans = pow(2, n - 3, MOD)
		print(ans)
		return
elif bb == 'B':
	print(1)
	return
elif ba == 'B':
	dp = [[0] * 2 for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		dp[i + 1][0] = (dp[i][0] + dp[i][1]) % MOD
		dp[i + 1][1] = dp[i][0] % MOD
	print((dp[n - 3][0] + dp[n - 3][1]) % MOD)
	return
else:
	ans = pow(2, n - 3, MOD)
	print(ans)
	return


n = int(input())
caa = input()
cab = input()
cba = input()
cbb = input()
mod = 10 ** 9 + 7
group1 = [('A', 'A', 'A', 'A'), ('A', 'A', 'A', 'B'), ('A', 'A', 'B', 'A'), ('A', 'A', 'B', 'B'), ('A', 'B', 'A', 'B'), ('A', 'B', 'B', 'B'), ('B', 'B', 'A', 'B'), ('B', 'B', 'B', 'B')]
group2 = [('A', 'B', 'A', 'A'), ('B', 'A', 'B', 'A'), ('B', 'A', 'B', 'B'), ('B', 'B', 'A', 'A')]
group3 = [('A', 'B', 'B', 'A'), ('B', 'A', 'A', 'A'), ('B', 'A', 'A', 'B'), ('B', 'B', 'B', 'A')]
if (caa, cab, cba, cbb) in group1:
	print(1)
elif (caa, cab, cba, cbb) in group2:
	ans = 1
	for i in range(n - 3):
		ans *= 2
		ans %= mod
	print(ans)
else:
	a1 = -1
	a2 = 1
	for i in range(n):
		a3 = a1 + a2
		a3 %= mod
		a1 = a2
		a2 = a3
	else:
		ans = a3
	print(ans)


MOD = 10 ** 9 + 7

def calc(n):
	dp = [[0] * 2 for _ in range(n)]
	dp[0][0] = 1
	dp[0][1] = 1
	for i in range(n - 1):
		dp[i + 1][0] = (dp[i][0] + dp[i][1]) % MOD
		dp[i + 1][1] = dp[i][0] % MOD
	return (dp[n - 1][0] + dp[n - 1][1]) % MOD

def calc2(n):
	if n == 1:
		return 2
	dp = [[0] * 4 for _ in range(n)]
	dp[1][0] = 1
	dp[1][1] = 1
	dp[1][2] = 1
	dp[1][3] = 1
	for i in range(1, n - 1):
		dp[i + 1][0] = (dp[i][0] + dp[i][2]) % MOD
		dp[i + 1][1] = (dp[i][0] + dp[i][2]) % MOD
		dp[i + 1][2] = (dp[i][1] + dp[i][3]) % MOD
		dp[i + 1][3] = dp[i][1] % MOD
	return sum(dp[n - 1]) % MOD

def rev(s):
	if s == 'A':
		return 'B'
	else:
		return 'A'
n = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
if n == 2:
	print(1)
	return
if n == 3:
	print(1)
	return
if ab == 'A':
	if aa == 'A':
		print(1)
	elif ba == 'A':
		ans = calc(n - 3)
		print(ans)
	elif bb == 'A':
		ans = pow(2, n - 3, MOD)
		print(ans % MOD)
	else:
		ans = pow(2, n - 3, MOD)
		print(ans % MOD)
elif bb == 'B':
	print(1)
elif ba == 'B':
	ans = calc(n - 3)
	print(ans)
elif aa == 'B':
	ans = pow(2, n - 3, MOD)
	print(ans % MOD)
else:
	ans = pow(2, n - 3, MOD)
	print(ans % MOD)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	aa = input().rstrip('\n')
	ab = input().rstrip('\n')
	ba = input().rstrip('\n')
	bb = input().rstrip('\n')
	if N <= 3:
		print(1)
		return
	if ab == 'A':
		if aa == 'A':
			print(1)
		elif ba == 'A':
			dp_a = [0] * N
			dp_b = [0] * N
			dp_a[0] = 1
			for i in range(1, N - 1):
				dp_a[i] = (dp_a[i - 1] + dp_b[i - 1]) % mod
				dp_b[i] = dp_a[i - 1]
			print(dp_a[N - 2])
		else:
			print(pow(2, N - 3, mod))
	elif bb == 'B':
		print(1)
	elif ba == 'B':
		dp_a = [0] * N
		dp_b = [0] * N
		dp_a[0] = 1
		for i in range(1, N - 1):
			dp_a[i] = (dp_a[i - 1] + dp_b[i - 1]) % mod
			dp_b[i] = dp_a[i - 1]
		print(dp_a[N - 2])
	else:
		print(pow(2, N - 3, mod))

def __starting_point():
	main()
__starting_point()


import sys

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

def main():
	n = int(input())
	CAA = input()
	CAB = input()
	CBA = input()
	CBB = input()
	dp = [0] * (n + 1)
	dp[2] = 1
	mod = 10 ** 9 + 7
	for i in range(3, n + 1):
		if CAB == 'A':
			if CAA == 'A':
				dp[i] = dp[i - 1]
			elif CAB == 'B' or CBA == 'B':
				dp[i] = sum(dp[:i]) % mod
			else:
				dp[i] = dp[i - 1] + dp[i - 2]
				dp[i] %= mod
		elif CBB == 'B':
			dp[i] = dp[i - 1]
		elif CAB == 'A' or CBA == 'A':
			dp[i] = sum(dp[:i]) % mod
		else:
			dp[i] = dp[i - 1] + dp[i - 2]
			dp[i] %= mod
	print(dp[n])

def __starting_point():
	main()
__starting_point()


N = int(input())
cAA = input()
cAB = input()
cBA = input()
cBB = input()
mod = 10 ** 9 + 7

def ans(value):
	print(value)
	return

def dp():
	nA = 1
	nB = 0
	for i in range(N - 3):
		(nA, nB) = ((nA + nB) % mod, nA)
	return (nA + nB) % mod
if N <= 3:
	ans(1)
if cAA == 'A' and cBB == 'B':
	ans(1)
if cAA == cBB:
	if cAA == cAB:
		ans(1)
	if cAB == cBA:
		ans(dp())
	ans(pow(2, N - 3, mod))
if cAB == cBA:
	ans(dp())
ans(pow(2, N - 3, mod))


N = int(input())
(AA, AB, BA, BB) = [input() == 'A' for _ in range(4)]
MOD = 10 ** 9 + 7
if AB:
	AB = not AB
	BA = not BA
	(AA, BB) = (not BB, not AA)
if N <= 3:
	ans = 1
elif BB == False:
	ans = 1
elif BA == True:
	ans = pow(2, N - 3, MOD)
else:
	(a, b) = (1, 0)
	for i in range(N - 1):
		(a, b) = (b, (a + b) % MOD)
	ans = b
print(ans)


MOD = 10 ** 9 + 7
n = int(input())
(a, b, c, d) = [0 if input() == 'A' else 1 for _ in range(4)]
if (a, b, c, d) in ((0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 0, 1), (1, 1, 1, 1)):
	print(1)
elif (a, b, c, d) in ((0, 1, 0, 0), (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0)):
	if n == 2:
		print(1)
	else:
		print(pow(2, n - 3, MOD))
else:
	(a, b) = (1, 1)
	for i in range(n - 2):
		(a, b) = (b, (a + b) % MOD)
	print(a)


N = int(input())
lis = [input() for _ in range(4)]
if N == 2:
	print(1)
	return
dp1 = [0] * (N + 1)
dp1[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, N + 1):
	for j in range(i - 1):
		dp1[i] += dp1[j]
		dp1[i] %= MOD
if lis[1] == 'A':
	if lis[0] == 'A':
		ans = 1
	elif lis[2] == 'A':
		ans = dp1[-1]
	else:
		ans = pow(2, N - 3, MOD)
elif lis[3] == 'B':
	ans = 1
elif lis[2] == 'B':
	ans = dp1[-1]
else:
	ans = pow(2, N - 3, MOD)
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
N = int(input())
Caa = int(input().rstrip() != 'A')
Cab = int(input().rstrip() != 'A')
Cba = int(input().rstrip() != 'A')
Cbb = int(input().rstrip() != 'A')
C = Caa * 8 + Cab * 4 + Cba * 2 + Cbb
ptns = [1, 1, 1, 1, 4, 1, 3, 1, 3, 3, 4, 4, 4, 1, 3, 1]
ans3s = [1, 1, 1]
for i in range(N + 10):
	ans = ans3s[-2] + ans3s[-1]
	ans3s.append(ans % MOD)
ans4s = [1, 1, 1]
for i in range(N + 10):
	ans = ans4s[-1] * 2
	ans4s.append(ans % MOD)
ptn = ptns[C]
if ptn == 1:
	ans = 1
elif ptn == 3:
	ans = ans3s[N - 1]
else:
	ans = ans4s[N - 1]
print(ans % MOD)


MOD = 10 ** 9 + 7
n = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
if ab == 'A' and aa == 'A':
	print(1)
elif ab == 'B' and bb == 'B':
	print(1)
elif ab == 'A' and aa == 'B':
	if ba == 'B':
		print(pow(2, max(n - 3, 0), MOD))
	else:
		res = [1, 1]
		for _ in range(max(n - 3, 0)):
			res.append((res[-1] + res[-2]) % MOD)
		print(res[-1])
elif ba == 'A':
	print(pow(2, max(n - 3, 0), MOD))
else:
	res = [1, 1]
	for _ in range(max(n - 3, 0)):
		res.append((res[-1] + res[-2]) % MOD)
	print(res[-1])


import sys
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
AA = input().strip()
AB = input().strip()
BA = input().strip()
BB = input().strip()
if (AA, AB, BA, BB) in {('A', 'A', 'A', 'A'), ('A', 'A', 'A', 'B'), ('A', 'A', 'B', 'A'), ('A', 'A', 'B', 'B'), ('A', 'B', 'A', 'B'), ('A', 'B', 'B', 'B'), ('B', 'B', 'A', 'B'), ('B', 'B', 'B', 'B')}:
	print(1)
elif (AA, AB, BA, BB) in {('A', 'B', 'A', 'A'), ('B', 'A', 'B', 'A'), ('B', 'A', 'B', 'B'), ('B', 'B', 'A', 'A')}:
	ANS = [0, 0, 1, 1, 2]
	for i in range(1000):
		ANS.append(ANS[-1] * 2 % mod)
	print(ANS[N])
elif (AA, AB, BA, BB) in {('A', 'B', 'B', 'A'), ('B', 'A', 'A', 'A'), ('B', 'A', 'A', 'B'), ('B', 'B', 'B', 'A')}:
	ANS = [0, 0, 1, 1, 2, 3, 5]
	for i in range(1000):
		ANS.append((ANS[-1] + ANS[-2]) % mod)
	print(ANS[N])


def main():
	MOD = 10 ** 9 + 7
	N = int(input())
	CAA = input()
	CAB = input()
	CBA = input()
	CBB = input()
	if N == 2:
		print(1)
		return
	fibs = [1, 2]
	for _ in range(N):
		fibs.append((fibs[-1] + fibs[-2]) % MOD)
	if CAB == 'A' and CAA == 'A' or (CAB == 'B' and CBB == 'B'):
		print(1)
	elif CAA == 'B' and CAB == CBA == 'A' or (CBB == 'A' and CAB == CBA == 'B'):
		print(fibs[N - 3])
	else:
		print(pow(2, N - 3, MOD))
main()


mod = 10 ** 9 + 7
n = int(input())
a = input()
b = input()
c = input()
d = input()
x = a + b + c + d
if x == 'BABB' or x == 'BBAA' or x == 'BABA' or (x == 'ABAA'):
	c = max(n - 3, 0)
	ans = pow(2, c, mod)
	print(ans)
elif x == 'BBBA' or x == 'ABBA' or x == 'BAAB' or (x == 'BAAA'):
	f = [1, 1]
	for j in range(n - 3):
		x = (f[-1] + f[-2]) % mod
		f.append(x)
	print(f[n - 2])
else:
	print(1)


def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(map(int, input().split()))
mod = 10 ** 9 + 7
N = I()
L = []
for _ in range(4):
	c = input()
	L.append(c)
if N <= 3:
	print(1)
	return
if L[1] == 'A' and L[0] == 'A':
	print(1)
	return
if L[1] == 'B' and L[3] == 'B':
	print(1)
	return
POW = [1]
for _ in range(N):
	p = POW[-1]
	p = p * 2 % mod
	POW.append(p)
F = [1, 1]
for _ in range(N):
	f = (F[-1] + F[-2]) % mod
	F.append(f)
if L[1] == 'A':
	if L[2] == 'B':
		print(POW[N - 3])
		return
	else:
		print(F[N - 2])
		return
elif L[2] == 'A':
	print(POW[N - 3])
	return
else:
	print(F[N - 2])
	return


MOD = 10 ** 9 + 7
a = ['AAAA', 'BBBB', 'AAAB', 'AABA', 'AABB', 'ABAB', 'ABBB', 'BBAB']
b = ['ABAA', 'BABA', 'BABB', 'BBAA']
c = ['ABBA', 'BAAA', 'BAAB', 'BBBA']
N = int(input())
c = ''.join([input() for _ in range(4)])
if c in a or N == 2:
	print(1)
elif c in b:
	print(pow(2, N - 3, MOD))
else:
	dp = [0] * N
	(dp[0], dp[1]) = (1, 1)
	for i in range(2, N):
		dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
	print(dp[N - 2])


n = int(input())
c_aa = input()
c_ab = input()
c_ba = input()
c_bb = input()
mod = 10 ** 9 + 7
if n == 2:
	print(1)
	return
num = 0
for (ci, i) in zip([c_aa, c_ab, c_ba, c_bb], [0, 1, 2, 3]):
	if ci == 'B':
		num += 2 ** i
if num in [1, 6, 7, 9]:
	dp = [0] * (n + 1)
	dp[2] = 1
	for i in range(3, n + 1):
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	print(dp[-1])
	return
elif num in [2, 3, 5, 13]:
	ans = pow(2, n - 3, mod)
	print(ans)
	return
print(1)


def f(n, table):
	s = {'ab'}
	tmp = set()
	for _ in range(n - 2):
		for ss in s:
			for i in range(len(ss) - 1):
				tmp.add(ss[:i + 1] + table[ss[i:i + 2]] + ss[i + 1:])
		(s, tmp) = (tmp, set())
	return len(s)
from functools import lru_cache
M = 1000000007

def fib(n):
	ret = [1, 1]
	cur = 1
	for i in range(n):
		ret.append(ret[cur] + ret[cur - 1])
		cur += 1
	return ret[n] % M

def t(n):
	return 2 ** n % M
ab = 'ab'
n = int(input().strip())
table = []
for _ in range(4):
	table.append(input().strip().lower())
table = dict(list(zip(['aa', 'ab', 'ba', 'bb'], table)))
fn = f(5, table)
if fn == 1:
	print(1)
elif fn == 3:
	print(fib(n - 2))
elif n == 2:
	print(1)
else:
	print(t(n - 3))


mod = 10 ** 9 + 7

def fibonacci(n):
	x1 = 1
	x2 = 1
	for _ in range(n - 1):
		nx1 = x2 % mod
		nx2 = (x1 + x2) % mod
		x1 = nx1
		x2 = nx2
	return x2
N = int(input())
s = ''
for i in range(4):
	s += input()
if N == 2:
	print(1)
elif s[1] == 'B' and s[3] == 'B':
	print(1)
elif s[0] == 'A' and s[1] == 'A':
	print(1)
elif s == 'ABBA' or s == 'BAAA' or s == 'BAAB' or (s == 'BBBA'):
	print(fibonacci(N - 2))
else:
	print(pow(2, N - 3, mod))


N = int(input())
X = 0
mod = int(1000000000.0) + 7
for i in range(4):
	X <<= 1
	X += ord(input()) - 65
F1 = {0, 1, 2, 3, 5, 7, 13, 15}
FF = {6, 8, 9, 14}
FB = {4, 10, 11, 12}
if X in F1:
	print(1)
elif X in FF:
	(a, b) = (1, 1)
	for i in range(N - 2):
		(a, b) = (b, a + b)
		b %= mod
	print(a % mod)
elif X in FB:
	t = N - 3
	b = 1
	while t > 0:
		b *= 2
		b %= mod
		t -= 1
	print(b)


N = int(input())
c = ''.join((input() for _ in range(4)))
M = 10 ** 9 + 7
if c in ('AAAA', 'AAAB', 'AABA', 'AABB', 'ABAB', 'ABBB', 'BBAB', 'BBBB'):
	print(1)
if c in ('ABAA', 'BABA', 'BABB', 'BBAA'):
	print(pow(2, max(0, N - 3), M))
if c in ('ABBA', 'BAAA', 'BAAB', 'BBBA'):
	F = [1, 1]
	while len(F) <= N:
		F += [(F[-1] + F[-2]) % M]
	print(F[N - 2])


from collections import Counter, defaultdict
import sys
import math
from functools import cmp_to_key
from itertools import permutations
sys.setrecursionlimit(10 ** 6)
mod = 1000000007
inf = int(1e+18)

def solve(n, caa, cab, cba, cbb):
	s_list = {'AB'}
	for i in range(n - 2):
		tmp = set()
		for s in s_list:
			for i in range(len(s) - 1):
				if s[i:i + 2] == 'AA':
					tmp.add(s[:i + 2] + caa + s[i + 2:])
				if s[i:i + 2] == 'AB':
					tmp.add(s[:i + 2] + cab + s[i + 2:])
				if s[i:i + 2] == 'BA':
					tmp.add(s[:i + 2] + cba + s[i + 2:])
				if s[i:i + 2] == 'BB':
					tmp.add(s[:i + 2] + cbb + s[i + 2:])
		s_list = tmp
	print('{}\t{}'.format(n, len(s_list)))

def main():
	n = int(input())
	(caa, cab, cba, cbb) = (input(), input(), input(), input())
	if n <= 3:
		print(1)
		return
	if cab == 'A':
		if caa == 'B':
			if cba == cab:
				p = 1
				pp = 1
				for i in range(3, n):
					v = (p + pp) % mod
					(pp, p) = (p, v)
				print(p)
			else:
				print(pow(2, n - 3, mod))
		else:
			print(1)
	elif cbb == 'A':
		if cba == cab:
			p = 1
			pp = 1
			for i in range(3, n):
				v = (p + pp) % mod
				(pp, p) = (p, v)
			print(p)
		else:
			print(pow(2, n - 3, mod))
	else:
		print(1)
main()


def main(n, caa, cab, cba, cbb):
	if n < 4:
		return 1
	ary = [caa, cab, cba, cbb]
	t = 'AB'
	mod = 10 ** 9 + 7
	if ary[0] == 'A' and ary[1] == 'A':
		return 1
	if ary[1] == 'B' and ary[3] == 'B':
		return 1
	elif ary == ['A', 'B', 'A', 'A']:
		return pow(2, n - 3, mod)
	elif ary == ['A', 'B', 'B', 'A']:
		dpa = [0] * (n - 2)
		dpb = [0] * (n - 2)
		dpa[0] = 0
		dpb[0] = 1
		for i in range(n - 3):
			dpa[i + 1] += dpb[i]
			dpb[i + 1] += dpa[i] + dpb[i]
			dpa[i + 1] %= mod
			dpb[i + 1] %= mod
		return (dpa[-1] + dpb[-1]) % mod
	elif ary == ['B', 'A', 'A', 'A']:
		dpa = [0] * (n - 2)
		dpb = [0] * (n - 2)
		dpa[0] = 1
		dpb[0] = 1
		for i in range(n - 3):
			dpa[i + 1] += dpa[i] + dpb[i]
			dpb[i + 1] += dpa[i]
			dpa[i + 1] %= mod
			dpb[i + 1] %= mod
		return dpa[-1]
	elif ary == ['B', 'A', 'A', 'B']:
		dpa = [0] * (n - 2)
		dpb = [0] * (n - 2)
		dpa[0] = 1
		dpb[0] = 1
		for i in range(n - 3):
			dpa[i + 1] += dpa[i] + dpb[i]
			dpb[i + 1] += dpa[i]
			dpa[i + 1] %= mod
			dpb[i + 1] %= mod
		return dpa[-1]
	elif ary == ['B', 'A', 'B', 'A']:
		return pow(2, n - 3, mod)
	elif ary == ['B', 'A', 'B', 'B']:
		return pow(2, n - 3, mod)
	elif ary == ['B', 'B', 'A', 'A']:
		return pow(2, n - 3, mod)
	elif ary == ['B', 'B', 'B', 'A']:
		dpa = [0] * (n - 2)
		dpb = [0] * (n - 2)
		dpa[0] = 0
		dpb[0] = 1
		for i in range(n - 3):
			dpa[i + 1] += dpb[i]
			dpb[i + 1] += dpa[i] + dpb[i]
			dpa[i + 1] %= mod
			dpb[i + 1] %= mod
		return (dpa[-1] + dpb[-1]) % mod
	else:
		return ary[5]
n = int(input())
caa = input()
cab = input()
cba = input()
cbb = input()
print(main(n, caa, cab, cba, cbb))


N = int(input())

def f(c):
	return 'B' if c == 'A' else 'A'
MOD = 10 ** 9 + 7
cs = [input() for _ in range(4)]
(caa, cab, cba, cbb) = cs
if N == 2 or N == 3:
	print(1)
	return
dpokanai = [0] * (N - 2)
dpoku = [0] * (N - 2)
dpokanai[0] = 1
for i in range(N - 3):
	dpokanai[i + 1] = dpokanai[i] + dpoku[i]
	dpoku[i + 1] = dpokanai[i]
if cab == 'A':
	if caa == 'B':
		if cba == 'B':
			print(pow(2, N - 3, MOD))
		else:
			print((dpokanai[-1] + dpoku[-1]) % MOD)
	else:
		print(1)
if cab == 'B':
	if cbb == 'A':
		if cba == 'A':
			print(pow(2, N - 3, MOD))
		else:
			print((dpokanai[-1] + dpoku[-1]) % MOD)
	else:
		print(1)


import sys
readline = sys.stdin.readline
N = int(readline())
caa = readline().strip() == 'A'
cab = readline().strip() == 'A'
cba = readline().strip() == 'A'
cbb = readline().strip() == 'A'
MOD = 10 ** 9 + 7
if not cab:
	(caa, cbb) = (cbb ^ 1, caa ^ 1)
	cab ^= 1
	cba ^= 1
if N == 2:
	print(1)
elif N == 3:
	print(1)
elif caa:
	print(1)
else:
	if cba:
		dp = [0] * (N - 2)
		dp1 = [0] * (N - 2)
		dp[0] = 1
		dp1[0] = 0
		for i in range(1, N - 2):
			dp[i] = (dp[i - 1] + dp1[i - 1]) % MOD
			dp1[i] = dp[i - 1]
		ans = (dp[N - 3] + dp1[N - 3]) % MOD
	else:
		ans = pow(2, N - 3, MOD)
	print(ans)


mod = 10 ** 9 + 7
n = int(input())
if n == 2 or n == 3:
	print(1)
	return
caa = input()
cab = input()
cba = input()
cbb = input()
fact = [1]
for i in range(1, 3001):
	fact.append(fact[-1] * i % mod)
revfact = [pow(fact[-1], mod - 2, mod)]
for i in range(3000, 0, -1):
	revfact.append(revfact[-1] * i % mod)
revfact = revfact[::-1]

def comb(n, r):
	return fact[n] * revfact[r] * revfact[n - r] % mod
if cab == 'A' and cba == 'A':
	if caa == 'A':
		print(1)
	else:
		ans = 0
		for cnta in range(1, n):
			sukima = cnta - 1
			cntb = n - 1 - cnta
			if cntb > sukima:
				continue
			else:
				ans += comb(sukima, cntb)
		print(ans % mod)
elif cab == 'A' and cba == 'B':
	if caa == 'A':
		print(1)
	else:
		print(pow(2, n - 3, mod))
elif cab == 'B' and cba == 'A':
	if cbb == 'B':
		print(1)
	else:
		print(pow(2, n - 3, mod))
elif cab == 'B' and cba == 'B':
	if cbb == 'B':
		print(1)
	else:
		ans = 0
		for cntb in range(1, n):
			sukima = cntb - 1
			cnta = n - 1 - cntb
			if cnta > sukima:
				continue
			else:
				ans += comb(sukima, cnta)
		print(ans % mod)


n = int(input())
t = {'A': 0, 'B': 1}
aa = t[input()]
ab = t[input()]
ba = t[input()]
bb = t[input()]
max_n = n + 10
mod = 10 ** 9 + 7
frac = [1]
for i in range(1, max_n + 1):
	frac.append(frac[-1] * i % mod)
inv = [1, 1]
inv_frac = [1, 1]
for i in range(2, max_n):
	inv.append((mod - inv[mod % i] * (mod // i)) % mod)
	inv_frac.append(inv_frac[-1] * inv[-1] % mod)

def perm(m, n):
	if m < n:
		return 0
	if m == 1:
		return 1
	return frac[m] * inv_frac[m - n] % mod

def comb(m, n):
	if m < n:
		return 0
	if m == 1:
		return 1
	return frac[m] * inv_frac[n] * inv_frac[m - n] % mod
if ab == 1:
	ab = 1 - ab
	ba = 1 - ba
	(aa, bb) = (1 - bb, 1 - aa)
if aa == 0:
	print(1)
elif ba == 1:
	if n <= 3:
		print(1)
	else:
		print(pow(2, n - 3, mod))
else:
	c = 0
	for i in range(1, n // 2 + 1):
		c = (c + comb(n - i - 1, i - 1)) % mod
	print(c)


import sys
import copy
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def fibo(x):
	MOD = 10 ** 9 + 7
	dp = [0] * (x + 10)
	dp[3] = 1
	dp[4] = 2
	for i in range(5, x + 1):
		dp[i] = dp[i - 1] + dp[i - 2]
		dp[i] %= MOD
	return dp[x]

def main():
	N = int(input())
	CAA = input().strip()
	CAB = input().strip()
	CBA = input().strip()
	CBB = input().strip()
	MOD = 10 ** 9 + 7
	if N == 2:
		print(1)
		return
	if CAA == 'A' and CAB == 'A' and (CBA == 'A') and (CBB == 'A'):
		print(1)
	elif CAA == 'A' and CAB == 'A' and (CBA == 'A') and (CBB == 'B'):
		print(1)
	elif CAA == 'A' and CAB == 'A' and (CBA == 'B') and (CBB == 'A'):
		print(1)
	elif CAA == 'A' and CAB == 'A' and (CBA == 'B') and (CBB == 'B'):
		print(1)
	elif CAA == 'A' and CAB == 'B' and (CBA == 'A') and (CBB == 'A'):
		print(pow(2, N - 3, MOD))
	elif CAA == 'A' and CAB == 'B' and (CBA == 'A') and (CBB == 'B'):
		print(1)
	elif CAA == 'A' and CAB == 'B' and (CBA == 'B') and (CBB == 'A'):
		print(fibo(N))
	elif CAA == 'A' and CAB == 'B' and (CBA == 'B') and (CBB == 'B'):
		print(1)
	elif CAA == 'B' and CAB == 'A' and (CBA == 'A') and (CBB == 'A'):
		print(fibo(N))
	elif CAA == 'B' and CAB == 'A' and (CBA == 'A') and (CBB == 'B'):
		print(fibo(N))
	elif CAA == 'B' and CAB == 'A' and (CBA == 'B') and (CBB == 'A'):
		print(pow(2, N - 3, MOD))
	elif CAA == 'B' and CAB == 'A' and (CBA == 'B') and (CBB == 'B'):
		print(pow(2, N - 3, MOD))
	elif CAA == 'B' and CAB == 'B' and (CBA == 'A') and (CBB == 'A'):
		print(pow(2, N - 3, MOD))
	elif CAA == 'B' and CAB == 'B' and (CBA == 'A') and (CBB == 'B'):
		print(1)
	elif CAA == 'B' and CAB == 'B' and (CBA == 'B') and (CBB == 'A'):
		print(fibo(N))
	elif CAA == 'B' and CAB == 'B' and (CBA == 'B') and (CBB == 'B'):
		print(1)

def __starting_point():
	main()
__starting_point()


n = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
mod = 10 ** 9 + 7

def solve(n, aa, ab, ba, bb):
	if n <= 3:
		print(1)
		return
	if ab == aa == 'A':
		print(1)
	elif ab == bb == 'B':
		print(1)
	elif ab == 'A' and aa == 'B':
		if ba == 'B':
			print(pow(2, n - 3, mod))
		else:
			dp = [[0] * 2 for i in range(n + 1)]
			dp[0][0] = 1
			dp[0][1] = 1
			for i in range(n):
				dp[i + 1][0] = (dp[i + 1][0] + dp[i][1]) % mod
				dp[i + 1][1] = (dp[i + 1][1] + dp[i][0] + dp[i][1]) % mod
			ans = (dp[n - 4][0] + dp[n - 4][1]) % mod
			print(ans)
	elif ab == 'B' and bb == 'A':
		if ba == 'A':
			print(pow(2, n - 3, mod))
		else:
			dp = [[0] * 2 for i in range(n + 1)]
			dp[0][0] = 1
			dp[0][1] = 1
			for i in range(n):
				dp[i + 1][0] = (dp[i + 1][0] + dp[i][1]) % mod
				dp[i + 1][1] = (dp[i + 1][1] + dp[i][0] + dp[i][1]) % mod
			ans = (dp[n - 4][0] + dp[n - 4][1]) % mod
			print(ans)
	else:
		pass
		print('ptn5')
solve(n, aa, ab, ba, bb)


import sys
input = sys.stdin.readline

def ot(s):
	return 'A' if s == 'B' else 'B'
mod = 10 ** 9 + 7
N = int(input())
Ss = [input().rstrip() for _ in range(4)]

def solve(caa, cab, cba, cbb):
	if caa == cab or N <= 3:
		return 1
	if cba == 'A':
		dp = [[0, 0] for _ in range(N + 1)]
		dp[0][1] = 1
		for n in range(N):
			dp[n + 1][0] = (dp[n][0] + dp[n][1]) % mod
			dp[n + 1][1] = dp[n][0]
		return dp[N][1]
	else:
		return pow(2, N - 3, mod)
if Ss[1] == 'B':
	Ss = [ot(Ss[3]), 'A', ot(Ss[2]), ot(Ss[0])]
print(solve(Ss[0], Ss[1], Ss[2], Ss[3]))


def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % mod
mod = 10 ** 9 + 7
N = 2 * 10 ** 5
g1 = [1] * (N + 1)
g2 = [1] * (N + 1)
inverse = [1] * (N + 1)
for i in range(2, N + 1):
	g1[i] = g1[i - 1] * i % mod
	inverse[i] = -inverse[mod % i] * (mod // i) % mod
	g2[i] = g2[i - 1] * inverse[i] % mod
inverse[0] = 0
N = int(input())
aa = input()
ab = input()
ba = input()
bb = input()
if ab == 'A':
	if aa == 'A':
		print(1)
	elif ba == 'A':
		res = 0
		for k in range(1, N // 2 + 1):
			tmp = N - 1 - (2 * k - 1)
			res += cmb(tmp + k - 1, k - 1, mod)
			res %= mod
		print(res)
	else:
		res = 0
		for k in range(1, N // 2 + 1):
			tmp = N - 1 - (2 * k - 1)
			res += cmb(tmp + 2 * k - 2, 2 * k - 2, mod)
			res %= mod
		print(res)
elif bb == 'B':
	print(1)
elif ba == 'B':
	res = 0
	for k in range(1, N // 2 + 1):
		tmp = N - 1 - (2 * k - 1)
		res += cmb(tmp + k - 1, k - 1, mod)
		res %= mod
	print(res)
else:
	res = 0
	for k in range(1, N // 2 + 1):
		tmp = N - 1 - (2 * k - 1)
		res += cmb(tmp + 2 * k - 2, 2 * k - 2, mod)
		res %= mod
	print(res)


from collections import defaultdict, Counter
mod = 10 ** 9 + 7
N = int(input())
(aa, ab, ba, bb) = (input(), input(), input(), input())
dic = {}
(dic['A', 'A'], dic['A', 'B'], dic['B', 'A'], dic['B', 'B']) = (aa, ab, ba, bb)
dp = {'AB'}
if N <= 3:
	print(1)
else:
	for _ in range(3):
		dp2 = set()
		for s in dp:
			for (i, (a, b)) in enumerate(zip(s, s[1:]), 1):
				dp2.add(s[:i] + dic[a, b] + s[i:])
		dp = dp2
	if len(dp) == 1:
		print(1)
	elif len(dp) == 3:
		(x, y) = (1, 1)
		for _ in range(N - 3):
			(x, y) = (y, (x + y) % mod)
		print(y)
	else:
		print(pow(2, N - 3, mod))


N = int(input())
c_AA = input()
c_AB = input()
c_BA = input()
c_BB = input()
MOD = 10 ** 9 + 7

def fibonacchi(n, mod):
	dp = []
	for i in range(0, n):
		if i == 0 or i == 1:
			dp.append(1)
		else:
			dp.append((dp[i - 2] + dp[i - 1]) % mod)
	return dp[-1]
if N == 2 or N == 3:
	print(1)
elif c_AB == 'B':
	if c_BB == 'B':
		print(1)
	elif c_BA == 'A':
		print(pow(2, N - 3, MOD))
	else:
		print(fibonacchi(N - 1, MOD))
elif c_AA == 'A':
	print(1)
elif c_BA == 'A':
	print(fibonacchi(N - 1, MOD))
else:
	print(pow(2, N - 3, MOD))


mod = 10 ** 9 + 7
N = int(input())
C = {}
C['AA'] = input()
C['AB'] = input()
C['BA'] = input()
C['BB'] = input()
F = [1, 1]
for i in range(N):
	F.append((F[-1] + F[-2]) % mod)
if N <= 3:
	print(1)
elif C['AB'] == 'B':
	if C['BB'] == 'B':
		print(1)
	elif C['BA'] == 'A':
		print(pow(2, N - 3, mod))
	else:
		print(F[N - 2])
elif C['AA'] == 'A':
	print(1)
elif C['BA'] == 'B':
	print(pow(2, N - 3, mod))
else:
	print(F[N - 2])


import sys
input = sys.stdin.readline
N = int(input())
aa = input()[:-1]
ab = input()[:-1]
ba = input()[:-1]
bb = input()[:-1]
mod = 10 ** 9 + 7
if N <= 3:
	print(1)
	return
if ab == 'A':
	if aa == 'A':
		print(1)
		return
	elif ba == 'B':
		print(pow(2, N - 3, mod))
		return
	else:
		table = [0] * (N + 1)
		table[2] = 1
		for i in range(1, N - 1):
			table[i + 2] = table[i + 1] + table[i]
		print(table[N] % mod)
		return
if ab == 'B':
	if bb == 'B':
		print(1)
		return
	elif ba == 'A':
		print(pow(2, N - 3, mod))
		return
	else:
		table = [0] * (N + 1)
		table[2] = 1
		for i in range(1, N - 1):
			table[i + 2] = table[i + 1] + table[i]
		print(table[N] % mod)
		return


mod = 10 ** 9 + 7

def tr(c):
	if c == 'A':
		return 'B'
	else:
		return 'A'
n = int(input())
if n <= 3:
	print(1)
	return
caa = input()
cab = input()
cba = input()
cbb = input()
if cab == 'B':
	(caa, cbb) = (cbb, caa)
	caa = tr(caa)
	cab = tr(cab)
	cba = tr(cba)
	cbb = tr(cbb)
if caa == 'A':
	print(1)
	return
if cba == 'B':
	print(pow(2, n - 3, mod))
	return
(ans, prev) = (2, 1)
for i in range(4, n):
	(ans, prev) = ((ans + prev) % mod, ans)
print(ans)


N = int(input())
c1 = input()
c2 = input()
c3 = input()
c4 = input()
mod = 10 ** 9 + 7
dp = [[0] * 2 for _ in range(N)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(1, N):
	dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod
	dp[i][1] = dp[i - 1][0]
x = dp[N - 1][1]
if N == 2:
	print(1)
	return
if c2 == 'A':
	if c1 == 'A':
		print(1)
		return
	elif c3 == 'A':
		print(x)
		return
	else:
		print(pow(2, N - 3, mod))
		return
elif c4 == 'B':
	print(1)
	return
elif c3 == 'B':
	print(x)
	return
else:
	print(pow(2, N - 3, mod))
	return


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
N = int(input())
(AA, AB, BA, BB) = [input().rstrip() for _ in range(4)]
if N <= 3:
	print(1)
	return
fact = [1] * (N + 1)
fact_inv = [1] * (N + 1)
for i in range(1, N + 1):
	fact[i] = i * fact[i - 1] % mod
fact_inv[N] = pow(fact[N], mod - 2, mod)
for i in range(1, N + 1)[::-1]:
	fact_inv[i - 1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n - k] % mod
if AB == 'A':
	if AA == 'A':
		print(1)
	elif BA == 'A':
		ans = 0
		for x in range(N - 3 + 1):
			if N - 3 - x + 1 < x:
				break
			ans = (ans + comb(N - 3 - x + 1, x)) % mod
		print(ans)
	else:
		print(pow(2, N - 3, mod))
elif BB == 'B':
	print(1)
elif BA == 'B':
	ans = 0
	for x in range(N - 3 + 1):
		if N - 3 - x + 1 < x:
			break
		ans = (ans + comb(N - 3 - x + 1, x)) % mod
	print(ans)
else:
	print(pow(2, N - 3, mod))


import sys
read = sys.stdin.read
readline = sys.stdin.readline
N = int(readline())
aa = readline().strip()
ab = readline().strip()
ba = readline().strip()
bb = readline().strip()
nxt = [aa, ab, ba, bb]
n = 10
ans = [0] * n
ans[2] = 1
d = {'AB'}
k = ['AA', 'AB', 'BA', 'BB']
for i in range(3, n):
	nd = set()
	for v in d:
		for j in range(i - 2):
			idx = k.index(v[j:j + 2])
			c = v[:j + 1] + nxt[idx] + v[j + 1:]
			nd.add(c)
	d = nd
	ans[i] = len(d)
MOD = 10 ** 9 + 7
r = (ans[2], ans[3], ans[4], ans[5])
if r == (1, 1, 1, 1):
	print(1)
elif r == (1, 1, 2, 4):
	if N == 2:
		print(1)
	else:
		print(pow(2, N - 3, MOD))
elif r == (1, 1, 2, 3):
	(x, y) = (0, 1)
	for i in range(N - 2):
		(x, y) = (y, (x + y) % MOD)
	print(y % MOD)


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
n = inn()
aa = ins()
ab = ins()
ba = ins()
bb = ins()
if ab == 'A' and aa == 'A' or (ab == 'B' and bb == 'B'):
	print(1)
elif ab == 'A' and aa == 'B' and (ba == 'A') or (ab == 'B' and bb == 'A' and (ba == 'B')):
	d = [0] * (n + 1)
	d[0] = 1
	for i in range(2, n + 1):
		for j in range(i - 1):
			d[i] = (d[i] + d[j]) % R
	print(d[n])
else:
	d = [0] * (n + 1)
	d[0] = 1
	x = 1
	for i in range(2, n - 1):
		for j in range(i - 1):
			d[i] = (d[i] + d[j] * (i - j - 1)) % R
		x = (x + d[i]) % R
	print(x)


n = int(input())
aa = ord(input()) - 65
ab = ord(input()) - 65
ba = ord(input()) - 65
bb = ord(input()) - 65
mo = 10 ** 9 + 7

def f(a):
	r = 1
	for i in range(1, a + 1):
		r *= i
	return r

def c(a, b):
	return f(a) // f(b) // f(a - b)
if ab == 0:
	ab = 1
	ba = 1 - ba
	bb = 1 - aa
if n == 2:
	print(1)
elif bb == 1:
	print(1)
elif ba == 0:
	print(2 ** (n - 3) % mo)
else:
	m = n - 3
	s = 0
	for i in range(0, m + 1):
		if i > m + 1 - i:
			break
		s += c(m + 1 - i, i)
	print(s % mo)


import sys
sys.setrecursionlimit(10 ** 7)

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
N = I()
(AA, AB, BA, BB) = (S(), S(), S(), S())
mod = 10 ** 9 + 7
if N == 2:
	print(1)
	return
fib = [1, 1]
for i in range(N):
	fib.append((fib[-1] + fib[-2]) % mod)
if AB == 'A':
	if AA == 'A':
		print(1)
	elif BA == 'B':
		print(pow(2, N - 3, mod))
	else:
		print(fib[N - 2])
elif BB == 'B':
	print(1)
elif BA == 'A':
	print(pow(2, N - 3, mod))
else:
	print(fib[N - 2])


N = int(input())
caa = input()
cab = input()
cba = input()
cbb = input()
mod = 10 ** 9 + 7
if N <= 3 or (caa == 'A' and cab == 'A') or (cab == 'B' and cbb == 'B'):
	print(1)
elif caa == 'B' and cab == 'A' and (cba == 'B') or (cab == 'B' and cba == 'A' and (cbb == 'A')):
	print(pow(2, N - 3, mod))
else:
	dp = [0] * (N + 1)
	dp[2] = 1
	for i in range(3, N + 1):
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	print(dp[N])


mod = 10 ** 9 + 7
(N, aa, ab, ba, bb) = open(0).read().split()
N = int(N)
if N <= 3 or aa == ab == 'A' or ab == bb == 'B':
	print(1)
elif aa + ab + ba == 'BAB' or ab + ba + bb == 'BAA':
	print(pow(2, N - 3, mod))
else:
	(a, b) = (1, 1)
	for _ in range(N - 3):
		(a, b) = (a + b, a)
	print(a % mod)


n = int(input())
mod = 10 ** 9 + 7
c_aa = input()
c_ab = input()
c_ba = input()
c_bb = input()

def Fibo(n):
	cache = {}

	def impl(ni):
		nonlocal cache
		if ni <= 3:
			return 1
		if ni not in cache:
			cache[ni] = impl(ni - 2) + impl(ni - 1)
		return cache[ni]
	return impl(n)
if n <= 3:
	print(1)
	return
if c_ab == 'B':
	if c_bb == 'B':
		print(1)
		return
	if c_bb == 'A':
		if c_ba == 'A':
			print(2 ** (n - 3) % mod)
			return
		elif c_ba == 'B':
			print(Fibo(n) % mod)
elif c_ab == 'A':
	if c_aa == 'A':
		print(1)
		return
	elif c_aa == 'B':
		if c_ba == 'B':
			print(2 ** (n - 3) % mod)
			return
		elif c_ba == 'A':
			print(Fibo(n) % mod)


N = int(input())
(C_AA, C_AB, C_BA, C_BB) = [input() for _ in range(4)]
if N <= 3:
	print(1)
	return
mod = 10 ** 9 + 7

def solve(n):
	dp_a = [0] * (n + 1)
	dp_b = [0] * (n + 1)
	dp_b[0] = 1
	for i in range(1, n + 1):
		dp_b[i] = (dp_a[i - 1] + dp_b[i - 1]) % mod
		dp_a[i] = dp_b[i - 1]
	res = (dp_a[n] + dp_b[n]) % mod
	return res
if C_AB == 'B':
	if C_BB == 'B':
		ans = 1
	elif C_BA == 'B':
		ans = solve(N - 3)
	else:
		ans = pow(2, N - 3, mod)
elif C_AA == 'A':
	ans = 1
elif C_BA == 'A':
	ans = solve(N - 3)
else:
	ans = pow(2, N - 3, mod)
print(ans)


import bisect
import heapq
import itertools
import sys
import math
import random
import time
from collections import Counter, deque, defaultdict
from functools import reduce
from operator import xor
from types import FunctionType
from typing import List, Any
from sys import stdin
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 9)

def lmi():
	return list(map(int, stdin.readline().split()))

def narray(*shape, init: Any=0):
	if shape:
		num = shape[0]
		return [narray(*shape[1:], init=init) for _ in range(num)]
	if callable(init):
		return init()
	return init

def main():
	N = int(input())
	AA = input()
	AB = input()
	BA = input()
	BB = input()
	ans = solve(N, AA, AB, BA, BB)
	print(ans)

def solve(N, AA, AB, BA, BB):
	pattern = ''.join([AA, AB, BA, BB])
	ans = 1
	if pattern in ['AAAA', 'AAAB', 'AABA', 'AABB', 'ABAB', 'ABBB', 'BBAB', 'BBBB']:
		ans = f1(N)
	elif pattern in ['ABAA', 'BABA', 'BABB', 'BBAA']:
		ans = f2(N)
	elif pattern in ['ABBA', 'BAAA', 'BAAB', 'BBBA']:
		ans = f3(N - 1)
	return ans

def f1(N):
	return 1

def f2(N):
	return pow(2, max(0, N - 3), mod)

def f3(N):
	memo = [0] * (N + 3)
	memo[1] = 1
	memo[2] = 1
	for i in range(3, N + 1):
		memo[i] = memo[i - 1] + memo[i - 2]
		memo[i] %= mod
	return memo[N]

def stupid(N, AA, AB, BA, BB):
	ret = set()
	stack = ['AB']
	while stack:
		cur = stack.pop()
		if len(cur) == N:
			ret.add(cur)
			continue
		for i in range(len(cur) - 1):
			next_s = ''
			if cur[i:i + 2] == 'AA':
				next_s = cur[:i + 1] + AA + cur[i + 1:]
			elif cur[i:i + 2] == 'AB':
				next_s = cur[:i + 1] + AB + cur[i + 1:]
			elif cur[i:i + 2] == 'BA':
				next_s = cur[:i + 1] + BA + cur[i + 1:]
			elif cur[i:i + 2] == 'BB':
				next_s = cur[:i + 1] + BB + cur[i + 1:]
			stack.append(next_s)
	return len(ret)

def __starting_point():
	main()
__starting_point()


import io
import os
from collections import Counter, defaultdict, deque
import sys
sys.setrecursionlimit(10 ** 5)
MOD = 10 ** 9 + 7

def solveBrute(N, AA, AB, BA, BB):
	possible = set()
	cache = set()

	def f(s):
		if s in cache:
			return
		cache.add(s)
		if len(s) == N:
			possible.add(s)
			return
		for i in range(len(s) - 1):
			pair = s[i:i + 2]
			if pair == 'AA':
				f(s[:i + 1] + AA + s[i + 1:])
			elif pair == 'AB':
				f(s[:i + 1] + AB + s[i + 1:])
			elif pair == 'BA':
				f(s[:i + 1] + BA + s[i + 1:])
			elif pair == 'BB':
				f(s[:i + 1] + BB + s[i + 1:])
	f('AB')
	return len(possible) % MOD

def solve(N, AA, AB, BA, BB):
	if N == 2:
		return 1
	pattern = AA + AB + BA + BB
	if pattern in ['ABAA', 'BABA', 'BABB', 'BBAA']:
		return pow(2, N - 3, MOD)
	elif pattern in ['ABBA', 'BAAA', 'BAAB', 'BBBA']:
		fib = [0] * (N + 1)
		fib[0] = 1
		fib[1] = 1
		for i in range(2, N + 1):
			fib[i] = (fib[i - 1] + fib[i - 2]) % MOD
		return fib[N - 2]
	else:
		return 1
if False:
	for mask in range(1 << 4):
		for N in range(2, 10):
			args = [mask >> 3 & 1, mask >> 2 & 1, mask >> 1 & 1, mask >> 0 & 1]
			args = ['AB'[x] for x in args]
			print((N, ''.join(args), '\t', solveBrute(N, *args)))
			assert solveBrute(N, *args) == solve(N, *args)
		print()

def __starting_point():
	TC = 1
	for tc in range(1, TC + 1):
		N = int(input())
		AA = input()
		AB = input()
		BA = input()
		BB = input()
		ans = solve(N, AA, AB, BA, BB)
		print(ans)
__starting_point()


def main():
	N = int(input())
	if N == 2 or N == 3:
		return 1
	cAA = input()
	cAB = input()
	cBA = input()
	cBB = input()
	mod = pow(10, 9) + 7
	v1 = 1
	for i in range(N - 3):
		v1 = v1 * 2 % mod
	v2 = 1
	dp = [0, 1]
	for i in range(N - 3):
		temp = [0, 0]
		temp[0] = dp[1]
		temp[1] = (dp[0] + dp[1]) % mod
		dp = temp
	v2 = sum(dp) % mod
	if cAB == 'B':
		if cBB == 'B':
			return 1
		elif cBA == 'A':
			return v1
		else:
			return v2
	elif cAA == 'A':
		return 1
	elif cBA == 'B':
		return v1
	else:
		return v2

def __starting_point():
	print(main())
__starting_point()


P = 10 ** 9 + 7
nn = 2000
fa = [1] * (nn + 1)
fainv = [1] * (nn + 1)
for i in range(nn):
	fa[i + 1] = fa[i] * (i + 1) % P
fainv[-1] = pow(fa[-1], P - 2, P)
for i in range(nn)[::-1]:
	fainv[i] = fainv[i + 1] * (i + 1) % P
C = lambda a, b: fa[a] * fainv[b] % P * fainv[a - b] % P if 0 <= b <= a else 0
N = int(input())
if N < 4:
	print(1)
	return
c = []
for _ in range(4):
	c.append(input())
if c[1] == 'A':
	if c[0] == 'A':
		print(1)
	elif c[2] == 'B':
		N -= 3
		ans = 1
		for _ in range(N):
			ans = 2 * ans % P
		print(ans)
	else:
		N -= 3
		M = N // 2
		ans = 0
		for m in range(M + 1):
			a = N - m
			ans = (ans + C(a, m)) % P
			ans = (ans + C(a, m - 1)) % P
		if N % 2 == 1:
			ans = (ans + 1) % P
		print(ans)
elif c[3] == 'B':
	print(1)
elif c[2] == 'A':
	N -= 3
	ans = 1
	for _ in range(N):
		ans = 2 * ans % P
	print(ans)
else:
	N -= 3
	M = N // 2
	ans = 0
	for m in range(M + 1):
		a = N - m
		ans = (ans + C(a, m)) % P
		ans = (ans + C(a, m - 1)) % P
	if N % 2 == 1:
		ans = (ans + 1) % P
	print(ans)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def S():
	return sys.stdin.readline().rstrip()
N = I()
(AA, AB, BA, BB) = (S(), S(), S(), S())
mod = 10 ** 9 + 7
if N <= 3:
	print(1)
	return
ans1 = 1
fib = [1, 1]
for i in range(N - 3):
	fib.append((fib[-1] + fib[-2]) % mod)
ans2 = fib[-1]
ans3 = pow(2, N - 3, mod)
if AB == 'A':
	if AA == 'A':
		ans = ans1
	elif BA == 'A':
		ans = ans2
	else:
		ans = ans3
elif BB == 'B':
	ans = ans1
elif BA == 'B':
	ans = ans2
else:
	ans = ans3
print(ans)


mod = 10 ** 9 + 7
n = int(input())
if n == 2 or n == 3:
	print(1)
	return
c = [input() for _ in range(4)]
if c[0] == c[1] == 'A' or c[1] == c[3] == 'B':
	print(1)
elif c[0] == 'B' and c[1] == c[2] == 'A' or (c[3] == 'A' and c[1] == c[2] == 'B'):
	fact = [1]
	for i in range(1, n + 1):
		fact.append(fact[-1] * i % mod)
	rfact = [pow(fact[-1], mod - 2, mod)]
	for i in range(n, 0, -1):
		rfact.append(rfact[-1] * i % mod)
	rfact = rfact[::-1]
	ans = 0
	for i in range(n - 1):
		if 2 * i - (n - 2) < 0:
			continue
		ans += fact[i] * rfact[n - 2 - i] * rfact[2 * i - (n - 2)]
	print(ans % mod)
else:
	print(pow(2, n - 3, mod))


import sys

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

def mapint():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
N = int(input())
AA = input()
AB = input()
BA = input()
BB = input()
mod = 10 ** 9 + 7
if N <= 3:
	print(1)
elif AA == 'A' and AB == 'A':
	print(1)
elif BB == 'B' and AB == 'B':
	print(1)
elif (AA, AB, BA, BB) in [('A', 'B', 'A', 'A'), ('B', 'A', 'B', 'A'), ('B', 'A', 'B', 'B'), ('B', 'B', 'A', 'A')]:
	print(pow(2, N - 3, mod))
else:
	dp = [[0] * 2 for _ in range(N)]
	dp[0][0] = 1
	for i in range(1, N):
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod
		dp[i][1] = dp[i - 1][0] % mod
	print(dp[-1][1])


import sys
MOD = 10 ** 9 + 7
N = int(input())
if N == 2:
	print(1)
	return
c = [input() for _ in range(4)]
s = ''.join(c)
DP = [0 for i in range(N + 1)]
DP[0] = 1
DP[1] = 1
DP_sum = 2
for i in range(2, N - 2):
	DP[i] += DP_sum - DP[i - 1]
	DP_sum += DP[i]
if s == 'AAAA' or s == 'BBBB' or s == 'AABA' or (s == 'BBAB'):
	print(1)
elif s == 'AAAB' or s == 'ABBB' or s == 'ABAB' or (s == 'AABB'):
	print(1)
elif s == 'ABAA' or s == 'BABB' or s == 'BABA' or (s == 'BBAA'):
	print(2 ** (N - 3) % MOD)
elif s == 'ABBA' or s == 'BAAB' or s == 'BAAA' or (s == 'BBBA'):
	if N == 3:
		print(1)
		return
	print(DP_sum % MOD)


import math
import sys
import itertools
A = 'A'
B = 'B'

def c(s):
	(caa, cab, cba, cbb) = s
	return {A: {A: caa, B: cab}, B: {A: cba, B: cbb}}

def f(s, n, C):
	if len(s) == n:
		yield s
	else:
		for i in range(len(s) - 1):
			yield from f(s[:i + 1] + C[s[i]][s[i + 1]] + s[i + 1:], n, C)

def g(n, s):
	return len(set(f('AB', n, c(s))))
n = int(input())
caa = input()
cab = input()
cba = input()
cbb = input()
s = ''.join([caa, cab, cba, cbb])
mod = 10 ** 9 + 7
X = g(6, s)
if n == 2:
	print(1)
elif X == 8:
	print(pow(2, n - 3, mod))
elif X == 5:
	a = 0
	b = 1
	for i in range(n - 2):
		(a, b) = (b, (a + b) % mod)
	print(b)
elif X == 1:
	print(1)
for sx in itertools.product(*[[A, B]] * 4):
	s = ''.join(sx)
	print(' '.join([s, *['%2d' % g(i, s) for i in range(2, 10)]]), file=sys.stderr)


N = int(input())
D = {}
D['A', 'A'] = str(input())
D['A', 'B'] = str(input())
D['B', 'A'] = str(input())
D['B', 'B'] = str(input())
Val = [{} for i in range(6)]
Val[0]['A', 'B'] = 1
for i in range(len(Val)):
	for (k, v) in Val[i - 1].items():
		K = list(k)
		for j in range(1, len(k)):
			A = K[0:j] + [D[K[j - 1], K[j]]] + K[j:]
			Val[i][tuple(A)] = 1
mod = 10 ** 9 + 7
if N <= 7:
	print(len(Val[-1 - (7 - N)]))
elif len(Val[-1]) == 1:
	print(1)
elif len(Val[-1]) == 8:
	L = [2, 3]
	for i in range(N - 5):
		L.append((L[-1] + L[-2]) % mod)
	print(L[-1])
else:
	print(pow(2, N - 3, mod))


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

def main():
	N = int(input())
	caa = input()
	cab = input()
	cba = input()
	cbb = input()
	if N < 4:
		print(1)
		return
	if cab == 'B':
		if cbb == 'B':
			print(1)
		elif cba == 'A':
			print(pow(2, N - 3, m))
		else:
			f = [1, 2]
			for i in range(N - 4):
				f.append((f[-1] + f[-2]) % m)
			print(f[-1])
	elif caa == 'A':
		print(1)
	elif cba == 'B':
		print(pow(2, N - 3, m))
	else:
		f = [1, 2]
		for i in range(N - 4):
			f.append((f[-1] + f[-2]) % m)
		print(f[-1])

def __starting_point():
	main()
__starting_point()


from itertools import product
P = 10 ** 9 + 7
F = [0, 1]
for i in range(1010):
	F.append(sum(F[-2:]) % P)
N = int(input())
AA = input()
AB = input()
BA = input()
BB = input()
P = 10 ** 9 + 7

def calc(aa, ab, ba, bb):
	if N <= 3:
		return 1
	ss = aa + ab + ba + bb
	if aa == 'A' and bb == 'B':
		return 1
	if aa == 'A' and ab == 'A':
		return 1
	if bb == 'B' and ab == 'B':
		return 1
	if ss == 'ABAA' or ss == 'BABB' or ss == 'BABA' or (ss == 'BBAA'):
		return pow(2, N - 3, P)
	if ss == 'ABBA' or ss == 'BAAB' or ss == 'BAAA' or (ss == 'BBBA'):
		return F[N - 1]
	return -1
print(calc(AA, AB, BA, BB))