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

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

#aかbのどちらかは無限に増やせる
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)))
else:
    if 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]))




# 2darray
## [[0] * 4 for i in range(3)]

# import itertools
# import sys
## return

# l_2d = [[20, 3, 100], [1, 200, 30], [300, 10, 2]]
# sorted(l_2d, key=lambda x: x[0])
## [[1, 200, 30], [20, 3, 100], [300, 10, 2]]

# import numpy as np
# l_2d_t = np.array(l_2d).T.tolist()
# l_2d_ts = sorted(l_2d_t, key=lambda x: x[0])
# np.array(l_2d_ts).T.tolist()
## [[3, 20, 100], [200, 1, 30], [10, 300, 2]]



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
else:
    if n==2:
        ans = 1
    else:
        if 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
#                 print(dp0, dp1)
                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


#Qはソート済み（低次のものから並ぶようにする）
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

#Q[0] != 0 が必要
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: # (d, c) = (0, 1)
    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 = 998244353
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
    # switch so that c_aa == 'A'
    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'
    # trivial case
    if c_aa == 'A':
        return 1
    # c_ab == 'A', c_aa == 'B'
    if c_ba == 'A':
        # A_XXX_AB no 'BB'
        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
    # c_ab == 'A', c_aa == 'B', c_ba == 'B'
    # A_XXX_AB: X: any
    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


#aa,ab,ba,bb
#A,B,(A,B),(A,B)
#B,A,(A,B),(A,B)

if (ab=="A" and ba=="A")or(ab=="B" and ba=="B"):
  # AAAAB+AAAAB+AAAB
  # (A*(1~) + B*1)*(1~)
  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

# AAAAA + BBBBB + AAAAA + BBBBB + AAAAA + B
# (A*(1~) + B*(1))*(1~) + A*(1~) + B*1

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))
  else:
    if cba=='B':
      print((pow(2,n-3,MOD)))
    else:
      print(ans)
else:
  if cbb=='B':
    print((1))
  else:
    if 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)
    else:
        if 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))
else:
    if AA == 'A':
        print(1)
    else:
        if 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()


"""

2^4通り -> 16

AB = A & AA = A なら1通り
AB = B & BB = B なら1通り

AB = A の時だけ考えればあとは反転
AA = B の時だけ考えればいい

BA = Aなら簡単
BA = BだとBBが連続できる


"""

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

        if ba == "B":
            print((pow(2,N-3,mod)))
            return
        else:
            print (ANSC)
            return

else:

    if bb == "B":
        print((1))
        return

    else:
        if 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':#4
        return 1
    
    if Cab=='B' and Cbb=='B':#4
        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]))
else:
    if 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]))
#
#print(ss)
#print(len(ss))


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)

# coding:UTF-8
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:
    # xBxB
    print((1))
    return
if C[1] == 0 and C[0] == 0:
    # AAxx
    print((1))
    return
if C[1] == C[2] == 1 and C[3] == 0:
    # xBBA
    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:
    # BAAx
    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))
    else:
        if 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))
else:
    if aa == "a":
        print((1))
    else:
        if 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):#a**n mod p
    bi = str(format(n,"b"))#2進表現に
    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
      #print(one, two)
    ans = one
else:
  if 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)
    else:
        if c["AB"] == "A":
            if c["AA"] == "A":
                print(1)
            else:
                if 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))
        else:
            if c["BB"] == "B":
                print(1)
            else:
                if 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))
else:
    if b=='B':
        if d=='B':
            print((1))
        else:
            if c=='A':
                print((pow(2,n-3,mod)))
            else:
                print(f)
    else:
        if a=='A':
            print((1))
        else:
            if 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
    else:
        if 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
else:
    if bb == "B":
        print(1)
        return
    else:
        if 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 #aa
    dp[1][1] = 1 #ab
    dp[1][2] = 1 #ba
    dp[1][3] = 1 #bb
    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
    # print(dp)
    return (sum(dp[n-1]))%MOD


def rev(s):
    if s == 'A': return 'B'
    else: return 'A'


# print(calc2(3))
# print(calc2(4))
# print(calc2(5))
# print(calc2(6))


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 == 'B':
#     aa = rev(aa)
#     ab = rev(ab)
#     ba = rev(ba)
#     bb = rev(bb)

# print('---')
# print(aa)
# print(ab)
# print(ba)
# print(bb)

if ab == 'A':
    if aa == 'A':
        print(1)
        # print('www1')
    else: # aa 'B
        if ba == 'A':
            ans = calc(n-3)
            print(ans)
            # print('www2')
        else:
            if bb == 'A':
                ans = pow(2,n-3,MOD)
                print(ans%MOD)
            else:
                ans = pow(2,n-3,MOD)
                print(ans%MOD)
                # else:
                #     ans = calc2(n-3)
                #     print(ans)
                # print('www3')

else:
    if bb == 'B':
        print(1)
        # print('www1')
    else: # aa 'B
        if ba == 'B':
            ans = calc(n-3)
            print(ans)
            # print('www2')
        else:
            if 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))
        else:
            if 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)))
    else:
        if bb == "B":
            print((1))
        else:
            if 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()

#!/usr/bin/env python3
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
        else:
            if 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
# AB == False

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)


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

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
# dp2 = [[0]*2 for _ in range(N+1)]
# dp2[0][1] = 1
# for i in range(1,N+1):
#   for j in range(i):
#     dp2[i][0] += dp2[j][1]
#     dp2[i][0] %= MOD
#     dp2[i][1] += dp2[j][0]
#     dp2[i][1] %= 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)
else:
  if 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)
#print('# ans3s:', ans3s, file=sys.stderr)
ans4s = [1, 1, 1]
for i in range(N+10):
    ans = ans4s[-1] * 2
    ans4s.append(ans % MOD)
#print('# ans4s:', ans4s, file=sys.stderr)

ptn = ptns[C]
#print('# C:', C, '/ ptn:', ptn, file=sys.stderr)
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])
else:
	if 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

"""
端が固定されているのを足掛かりにしたい
初手はA,(Cab),Bは確定
最終的にA,(Cax),...,(Cxb),Bも確定
Aから初めて，適当に進めて，最後を帳尻合わせするか?
dpで，末尾がcaa~cbbの4通りを持っておくか，いや，これだと被りを検知できないのでA,Bの2通りにしたい

Cab=A かつ　Caa=Aだと一通り
Cab=B かつ　Cbb=Bだと一通り

なので，
Cab=AならばCaa=Bを仮定して話を進められる.
このとき，
Cba=Bならば，先頭A，末尾ABの全てが作れる=2^(N-3)
Cba=Aならば，先頭A，末尾ABかつBBを含まない文字列が作れる.これはフィボナッチF(N-2)

Cab=Bでも似たような感じ
"""


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
else:
    if 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 = 1_000_000_007


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)))
else:
    if 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(1e9) + 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(1e18)

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))
    else:
        if 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','A','A','A']:
  #elif ary==['A','A','A','B']:
  #elif ary==['A','A','B','A']:
  #elif ary==['A','A','B','B']:
  elif ary==['A','B','A','A']: # 先頭はA、末尾はB。xxxの部分は任意。ABxxxxxxB
    return pow(2,n-3,mod)
  #elif ary==['A','B','A','B']:
  elif ary==['A','B','B','A']: # 先頭はA、末尾はB。xxxの部分でAは連続しない。ABxxxxxxxB
    dpa=[0]*(n-2) # dpa[i]:i+2文字目がa
    dpb=[0]*(n-2) # dpb[i]:i+2文字目がb
    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==['A','B','B','B']:
  elif ary==['B','A','A','A']: # 先頭はA、末尾はB。xxxの部分でBは連続しない。AxxxxxxxAB
    dpa=[0]*(n-2) # dpa[i]:i+2文字目がa
    dpb=[0]*(n-2) # dpb[i]:i+2文字目がb
    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']: # 先頭はA、末尾はB。xxxの部分は任意。ABxxxxxxxB
    dpa=[0]*(n-2) # dpa[i]:i+2文字目がa
    dpb=[0]*(n-2) # dpb[i]:i+2文字目がb
    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']: # 先頭はA、末尾はB。xxxの部分は任意。AxxxxxxxAB
    return pow(2,n-3,mod)
  elif ary==['B','A','B','B']: 
    return pow(2,n-3,mod)
  elif ary==['B','B','A','A']: # 先頭はA、末尾はB。xxxの部分は任意。ABxxxxxxxB
    return pow(2,n-3,mod)
  #elif ary==['B','B','A','B']:
  elif ary==['B','B','B','A']: # 先頭はA、末尾はB。xxxの部分でAは連続しない。ABxxxxxxxB
    dpa=[0]*(n-2) # dpa[i]:i+2文字目がa
    dpb=[0]*(n-2) # dpb[i]:i+2文字目がb
    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','B','B','B']:
  else:
    return ary[5]


n=int(input())
caa=input()
cab=input()
cba=input()
cbb=input()
print(main(n,caa,cab,cba,cbb))

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]))
else:
    if R[-3]+R[-2] == R[-1]:
        for _ in range(N-2-4):
            R.append((R[-1]+R[-2])%MOD)
    elif R[-2] == R[-1]:
        pass
    elif R[-2]*2 == R[-1]:
        for _ in range(N-2-4):
            R.append(R[-1]*2%MOD)
    print((R[-1]))


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]

# print(dpoku, dpokanai)

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 
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))
else:
    if b=='B':
        if d=='B':
            print((1))
        else:
            if c=='A':
                print((pow(2,n-3,mod)))
            else:
                print(f)
    else:
        if a=='A':
            print((1))
        else:
            if c=='B':
                print((pow(2,n-3,mod)))
            else:
                print(f)


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
#print(N, caa, cab, cba, cbb)

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)))
    # fibo
    elif CAA == "B" and CAB == "A" and CBA == "A" and CBB == "B":
        print((fibo(N)))
    # fibo
    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)))
    # fibo
    elif CAA == "B" and CAB == "B" and CBA == "B" and CBB == "B":
        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())
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:
            # n-3の区間にaaを除く全パターン
            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:
            # n-3の区間にaaを除く全パターン
            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')
"""
from itertools import product
for n in range(3, 100):
    for bit in product(['A', 'B'], repeat=4):
        aa, ab, ba, bb = bit
        solve(n, aa, ab, ba, bb)
"""
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])))

# AB = ["A", "B"]
# for s1 in AB:
#     for s2 in AB:
#         for s3 in AB:
#             for s4 in AB:
#                 print(s1+s2+s3+s4)
#                 T(6, [s1, s2, s3, s4])


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)
    else:
        if 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)
else:
    if bb=="B":
        print(1)
    else:
        if 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))
else:
    if c_AB == 'B':
        if c_BB == 'B':
            print((1))
        else:
            if c_BA == 'A':
                print((pow(2, N - 3, MOD)))
            else:
                print((fibonacchi(N - 1, MOD)))
    else:
        if c_AA == 'A':
            print((1))
        else:
            if 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))
    else:
        if C["BA"]=="A":
            print((pow(2,N-3,mod)))
        else:
            print((F[N-2]))
else:
    if C["AA"]=="A":
        print((1))
    else:
        if 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
  else:
    if 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
  else:
    if 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

#!/usr/bin/env python3
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
        else:
            if 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()

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
  else:
    if c3=="A":
      print(x)
      return
    else:
      print(pow(2,N-3,mod))
      return
else:
  if c4=="B":
    print(1)
    return
  else:
    if 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)
    else:
        if 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))
else:
    if BB == 'B':
        print(1)
    else:
        if 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))

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

N = int(readline())
#n,m = map(int,readline().split())
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)

#print(ans)

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


#from collections import deque,defaultdict
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 # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

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
        #ddprint(f"{i=} {x=} {d[i]=}")
        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))
    else:
        if BA == 'B':
            print((pow(2,N-3,mod)))
        else:
            print((fib[N-2]))
else:
    if BB == 'B':
        print((1))
    else:
        if 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)

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

#aかbのどちらかは無限に増やせる
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]*(n-1)
        dp[0]=1
        dp[1]=1
        for i in range(2,n-1):
            dp[i]=(dp[i-1]+dp[i-2])%mod
        if c3=="A":
            print((dp[-1]))
        else:
            print((pow(2,n-3,mod)))
else:
    if c4=="B":
        print((1))
    else:
        dp = [0] * (n - 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n - 1):
            dp[i] =(dp[i-1]+dp[i-2])%mod
        if c3=="B":
            print((dp[-1]))
        else:
            print((pow(2,n -3,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
    else:
        # [AB]xxxxxx[B]
        if C_BA == "B":
            # A は 1 連続まで
            ans = solve(N-3)
        else:
            # B と A は任意
            ans = pow(2, N-3, mod)
else:
    if C_AA == "A":
        ans = 1
    else:
        # [A]xxxxxx[AB]
        if 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)
    # for i in range(2, 10):
    #     for pattern in itertools.product('AB', repeat=4):
    #         N = i
    #         ans = stupid(N, *pattern)
    #         print(ans, *pattern)
    #         # assert ans == solve(N, *pattern)
    #     print('-' * 100)

    # if AB == 'A':
    #     if AA == 'A':
    #         print(1)
    #         return
    #     else:
    #         # AB: A, AA: B
    #         pass
    # else:
    #     if BB == 'B':
    #         print(1)
    #     else:
    #         pass

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)
    # print(ret)
    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

    # print(v1, v2)

    if cAB == 'B':
        if cBB == 'B': return 1
        else:
            if cBA == 'A':
                return v1
            else:
                return v2
    else:
        if cAA == 'A': return 1
        else:
            if 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)
  else:
    if 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)
else:
  if c[3] == "B":
    print(1)
  else:
    if 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
    else:
        if BA == 'A':
            ans = ans2
        else:
            ans = ans3
else:
    if BB == 'B':
        ans = ans1
    else:
        if 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):
        # Bが連続しないように置く
        dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod
        dp[i][1] = dp[i-1][0]%mod
    print((dp[-1][1]))
    

# def f(aa, ab, ba, bb):
#     l = [aa, ab, ba, bb]
#     start = 'AB'
#     se = set([start])
#     while True:
#         new = set()
#         for s in se:
#             lens = len(s)
#             for i in range(lens-1):
#                 new.add(s[:i+1]+l[lis.index(s[i:i+2])]+s[i+1:])
#         if len(s)+1==N:
#             return new
#         se = new

# N = 10
# lis = ['AA', 'AB', 'BA', 'BB']
# for AA in ('A', 'B'):
#     for AB in ('A', 'B'):
#         for BA in ('A', 'B'):
#             for BB in ('A', 'B'):
#                 print(AA, AB, BA, BB, len(f(AA, AB, BA, BB)))


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

    


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)] #間を開けて選ぶ場合の数(i番目を選ぶ場合)
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)
        #print(K)
        for j in range(1,len(k)):
          
            A=K[0:j]+[D[(K[j-1],K[j])]]+K[j:]
            #print(tuple(A))
            Val[i][tuple(A)]=1
#print(len(Val[-1]))
mod=10**9+7
if N<=7:
    print(len(Val[-1-(7-N)]))
else:
    if 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))

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

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


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))
        else:
            if 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]))
    else:
        if caa == 'A':
            print((1))
        else:
            if 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)
# print("F =", F[:20])
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
# for s in product("AB", repeat = 4):
#     print(s, calc(*s))

print(calc(AA, AB, BA, BB))