Problem:
 Score : 400 points    Problem Statement We have a board with a 2 \times N grid.
Snuke covered the board with N dominoes without overlaps.
Here, a domino can cover a 1 \times 2 or 2 \times 1 square.  Then, Snuke decided to paint these dominoes using three colors: red, cyan and green.
Two dominoes that are adjacent by side should be painted by different colors.
Here, it is not always necessary to use all three colors.  Find the number of such ways to paint the dominoes, modulo 1000000007 .  The arrangement of the dominoes is given to you as two strings S_1 and S_2 in the following manner:   Each domino is represented by a different English letter (lowercase or uppercase).  The j -th character in S_i represents the domino that occupies the square at the i -th row from the top and j -th column from the left.       Constraints  1 \leq N \leq 52  |S_1| = |S_2| = N  S_1 and S_2 consist of lowercase and uppercase English letters.  S_1 and S_2 represent a valid arrangement of dominoes.         Input Input is given from Standard Input in the following format:  N  S_1  S_2       Output Print the number of such ways to paint the dominoes, modulo 1000000007 .        Sample Input 1 3
aab
ccb      Sample Output 1 6  There are six ways as shown below:        Sample Input 2 1
Z
Z      Sample Output 2 3  Note that it is not always necessary to use all the colors.       Sample Input 3 52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn      Sample Output 3 958681902

Solution (Python):
n = int(input())
s = [input(),input()]
tate = []
i = 0
while i < n:
    if s[0][i] != s[1][i]:
        tate.append(0)
        i += 2
    else:
        tate.append(1)
        i += 1
ans = 6 - tate[0]*3
mod = 1000000007
for i in range(len(tate) - 1):
    if tate[i] ^ tate[i+1]:
        if tate[i]:
            ans *= 2
            ans %= mod
    else:
        if tate[i]:
            ans *= 2
        else:
            ans *= 3
        ans %= mod
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 1000000007
n = ni()
s1 = list(ns())
s2 = list(ns())
a = []

for i in range(n):
    if s1[i] == s2[i]:
        a.append(0)
    elif i > 0 and s1[i-1] == s1[i] and s2[i-1] == s2[i]:
        a.append(1)

ans = 3 if a[0] == 0 else 6
for j in range(1,len(a)):
    if a[j] == 0:
        if a[j-1] == 0:
            ans*=2
        else:
            ans*=1
    else:
        if a[j-1] == 0:
            ans*=2
        else:
            ans*=3
    ans%=mod

print(ans%mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s1 = readline().rstrip().decode()
s2 = readline().rstrip().decode()
mod = 10 ** 9 + 7

if s1[0] == s2[0]:
    ans = 3
    cnt = 1
else:
    cnt = 2
    ans = 6

for i in range(n):
    if cnt >= n:
        break
    if s1[cnt] != s2[cnt]:
        if s1[cnt - 1] == s2[cnt - 1]:
            ans *= 2
        else:
            ans *= 3
        cnt += 2
    else:
        if s1[cnt - 1] != s2[cnt - 1]:
            ans *= 1
        else:
            ans *= 2
        cnt += 1
    ans %= mod
print(ans)

Solution (Python):
MOD = 10**9 + 7


def main():
    N = int(input())
    S1 = input()
    _ = input()
    skip = False
    ans = 0
    pre = True  
    for i in range(N):
        if i == 0:
            if i != N-1 and S1[i] == S1[i+1]:
                pre = False
                ans = 6
                skip = True
            else:
                pre = True
                ans = 3
            continue
        if skip:
            skip = False
            continue
        if i != N-1 and S1[i] == S1[i+1]:
            if pre:
                ans *= 2
            else:
                ans *= 3
            pre = False
            skip = True
        else:
            if pre:
                ans *= 2
            else:
                ans *= 1
            pre = True
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S1 = input().strip()
S2 = input().strip()
mod = 10 ** 9 + 7

ans = 1
idx = 0
before_type = 0
if S1[0] == S2[0]:
    ans *= 3
    idx = 1
    before_type = 0
else:
    ans *= 6
    idx = 2
    before_type = 1

while idx < N:
    if S1[idx] == S2[idx]:
        if before_type == 0:
            ans *= 2
        idx += 1
        before_type = 0
    else:
        if before_type == 1:
            ans *= 3
        else:
            ans *= 2
        idx += 2
        before_type = 1
    ans %= mod
print(ans)

Solution (Python):
N = int(input())
S1 = input().strip()
S2 = input().strip()
mod = 10 ** 9 + 7

ans = 1
idx = 0
before_type = 0
if S1[0] == S2[0]:
    ans *= 3
    idx = 1
    before_type = 0
else:
    ans *= 6
    idx = 2
    before_type = 1

while idx < N:
    if S1[idx] == S2[idx]:
        if before_type == 0:
            ans *= 2
        idx += 1
        before_type = 0
    else:
        if before_type == 1:
            ans *= 3
        else:
            ans *= 2
        idx += 2
        before_type = 1
    ans %= mod
print(ans)

Solution (Python):
M = 1000000007
n = int(input())


def pack(s):
    p = [s[0]]
    for i in range(1, len(s)):
        if s[i] != s[i - 1]:
            p.append(s[i])
    return p


s1 = pack(input())
s2 = pack(input())


def solve():
    res = 6 if s1[0] != s2[0] else 3
    for i in range(1, len(s1)):
        if s1[i - 1] != s2[i - 1]:
            if s1[i] != s2[i]:
                res *= 3
            else:
                res *= 1
        else:
            if s1[i] != s2[i]:
                res *= 2
            else:
                res *= 2
        res %= M
    return res


print(solve())

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
mod = 10 ** 9 + 7
if s1[0] == s2[0]:
  ans = 3
  flag = 1
  now = 1
else:
  ans = 6
  flag = 0
  now = 2
while now < n:
  if s1[now] == s2[now]:
    if flag:
      ans *= 2
    flag = 1
    now += 1
  else:
    if flag:
      ans *= 2
    else:
      ans *= 3
    flag = 0
    now += 2
  ans %= mod
print(ans)

Solution (Python):
N = int(input())
A = input()
B = input()
MOD = 10 ** 9 + 7

i = 0
vh = []
while i < N:
    if A[i] == B[i]:
        vh.append('v')
        i += 1
    else:
        vh.append('h')
        i += 2


if vh[0] == 'v':
    ans = 3
else:
    ans = 6
for j in range(1, len(vh)):
    if vh[j] == 'v':
        if vh[j - 1] == 'v':
            ans = (ans * 2) % MOD
        else:
            ans = (ans * 1) % MOD
    else:
        if vh[j - 1] == 'v':
            ans = (ans * 2) % MOD
        else:
            ans = (ans * 3) % MOD
print(ans)

Solution (Python):
n = int(input())
s_1 = list(input())
s_2 = list(input())
array_kind = []
i = 0
while i < n:
    if s_1[i] == s_2[i]:
        array_kind.append('X')
        i += 1
    else:
        array_kind.append('Y')
        i += 2
ans = 1
mod = 10**9+7
if array_kind[0] == 'X':
    ans = 3
else:
    ans = 6
for i in range(1,len(array_kind)):
    if array_kind[i] == 'X':
        if array_kind[i-1] == 'X':
            ans *= 2
        else:
            ans *= 1
    else:
        if array_kind[i-1] == 'X':
            ans *= 2
        else:
            ans *= 3
    ans %= mod
print(ans)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
ans = 1
mod = 10**9+7
cnt = 0
former = 0 
 
if S1[0] == S2[0]:
    cnt += 1
    ans = 3
    former = 0
else:
    cnt += 2
    ans = 6
    former = 1
 
while cnt < N:
    if S1[cnt] == S2[cnt]:
        if former:
            ans *= 1
        else:
            ans *= 2
        ans %= mod
        former = 0
        cnt += 1
    else:
        if former:
            ans *= 3
        else:
            ans *= 2
        former = 1
        cnt += 2
        ans %= mod
print(ans)

Solution (Python):
N = int(input())
S = input()
T = input()
mod = int(1e9) + 7
L = []
cnt = 0
while cnt != N:
  if S[cnt] == T[cnt]:
    L.append(1)
    cnt += 1
  else:
    L.append(2)
    cnt += 2
dp = [0 for _ in range(55)]
dp[0] = 1
for i in range(len(L)):
  if i == 0:
    dp[i+1] = 3 * L[i]
  else:
    if L[i] != L[i-1]:
      dp[i+1] = (dp[i] * L[i]) % mod
    else:
      dp[i+1] = (dp[i] * (1 + L[i])) % mod
print(dp[len(L)])

Solution (Python):
import sys
n = int(input())
s1 = list(input())
s2 = list(input())

li = []
tmp = 1
if n == 1:
    print(3)
    sys.exit()
for i,s in enumerate(s1):
    
    if i == len(s1) - 1:
        break
    
    if s != s1[i+1]:
        li.append(tmp)
        tmp = 1
    
    else:
        tmp = 2




if s1[-1] == s1[-2]:
    li.append(2)
else:
    li.append(1)


all_count = 1
for j,l in enumerate(li):
    if j == 0:
        if li[0] == 2: 
            all_count *= 6
        else:
            all_count *= 3
        continue
    if l == 2 and li[j-1] == 2:
        all_count *= 3
    elif l == 1 and li[j-1] == 2:
        all_count *= 1
    else:
        all_count *= 2
print(all_count%1000000007)

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N = iip(False)
    S1 = iip()
    S2 = iip()

    cur = 0

    dp = [0 for i in range(N)]

    n = -1
    for i, j in zip(S1, S2):
        n += 1
        if n == 0:
            if i==j:
                dp[n] = 3
            else:
                dp[n] = 6
            cur_i = i
            cur_j = j
            continue

        if cur_i == i:
            dp[n] = dp[n-1]
        elif i == j and cur_i == cur_j:
            dp[n] = dp[n-1] * 2
        elif i==j and cur_i != cur_j:
            dp[n] = dp[n-1]
        elif cur_i != cur_j:
            dp[n] = dp[n-1] *3
        else:
            dp[n] = dp[n-1]*2

        cur_i = i
        cur_j = j
        dp[n] %= mod


    
    print(dp[-1])




def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  
    d = input().split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=False, num_only=True):  
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): 
    l = left
    r = right
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
S1=input()
S2=input()
MOD=10**9+7
for i in range(N):
  if i==0:
    if S1[0]==S2[0]:
      ans=3
    else:
      ans=6
  else:
    if S1[i-1]==S2[i-1]:
      ans*=2
    else:
      if S1[i]==S2[i]:
        pass
      else:
        if S1[i-1]==S1[i]:
          pass
        else:
          ans*=3
  ans%=MOD
print(ans)

Solution (Python):
mod = 10**9+7
N = int(input())
T = []
U = list(map(str, input()))
B = list(map(str, input()))

cond = 0
for i in range(N):
    if cond:
        cond = 0
        continue
    if U[i] == B[i]:
        T.append(1)
    else:
        T.append(2)
        cond = 1

if T[0] == 1:
    ans = 3
else:
    ans = 6

for i in range(1,len(T)):
    if T[i-1] == 1:
        ans *= 2
        ans %= mod
    else:
        if T[i] == 1:
            ans *= 1
        else:
            ans *= 3
            ans %= mod

ans %= mod
print(ans)

Solution (Python):
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()
s1 = ins()
s2 = ins()
if s1[0]==s2[0]:
    p = 3
    i = 1
else:
    p = 6
    i = 2
while i<n:
    if s1[i-1]==s2[i-1]:
        if s1[i]==s2[i]:
            p = (p*2)%R
            i += 1
        else:
            p = (p*2)%R
            i += 2
    else:
        if s1[i]==s2[i]:
            i += 1
        else:
            p = (p*3)%R
            i += 2
print(p)

Solution (Python):
n=int(input())
A=list(input())+["
B=list(input())+["*"]
C=""
mod=10**9+7

i=0
while i<n:
    if A[i]==B[i]:
        C +="X";i +=1
    elif A[i]==A[i+1] and B[i]==B[i+1]:
        C +="Y";i +=2

cnt=3 if C[0]=="X" else 6
for i in range(1,len(C)):
    word=C[i-1]+C[i]
    if word=="XY":cnt *=2
    elif word=="XX":cnt *=2
    elif word=="YX":cnt *=1
    elif word=="YY":cnt *=3
    cnt %=mod
print(cnt)

Solution (Python):
N=int(input())
S1=input()
S2=input()


mod=1000000007
ans=3
i=0
flag=0
while N-1>=i:
    if S1[i]==S2[i]:
        if i!=0:
            if flag==0:
                ans*=2
        else:
            ans=3
        flag=0
        i+=1
    else:
        if i!=0:
            if flag==0:
                ans*=2
            else:
                ans*=3
        else:
            ans=6
        flag=1
        i+=2

print(ans%mod)

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()

N=int(input())
S=input()
input()
mod=10**9+7
w=0
count=3
flag=0
while w<N:
    if w<N-1 and S[w]==S[w+1]:
        if flag==0:
            count*=2
            count%=mod
        if flag==1:
            count*=3
            count%=mod
        if flag==2:
            count*=2
            count%=mod
        w+=2
        flag=1
    else:
        if flag==2:
            count*=2
            count%=mod
        w+=1
        flag=2

print(count%mod)

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    S1 = input()
    S2 = input()

    pre_s1 = S1[0]
    pre_s2 = S2[0]
    if pre_s1 == pre_s2:
        ans = 3
        i = 1
    else:
        ans = 6
        i = 2

    while i < N:
        if pre_s1 == pre_s2:
            ans *= 2
            ans %= MOD
            if S1[i] == S2[i]:
                d = 1
            else:
                d = 2
        else:
            if S1[i] == S2[i]:
                d = 1
            else:
                ans *= 3
                ans %= MOD
                d = 2
        pre_s1 = S1[i]
        pre_s2 = S2[i]
        i += d
                
    print(ans)
    

    

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = input()
b = input()
MOD = 1000000007

ans = 3 * ((a[0] != b[0])+1)
tate = (a[0] == b[0])+0
skip = (a[0] != b[0])+0
for x, y in zip(a[1:], b[1:]):
    if skip:
        skip = 0
        continue
    if x == y:
        now_tate = 1
    else:
        now_tate = 0
        skip = 1

    if tate:
        ans *= 2
    else:
        if now_tate:
            ans *= 1
        else:
            ans *= 3
    tate = now_tate
    ans = ans % MOD
print(ans % MOD)

Solution (Python):
n = int(input())
a = input()
b = input()
MOD = 1000000007

ans = 1
if a[0] == b[0]:
    ans *= 3
    tate = 1
    skip = 0
    for x, y in zip(a[1:], b[1:]):
        if skip:
            skip = 0
            continue
        if x == y:
            now_tate = 1
        else:
            now_tate = 0
            skip = 1

        if tate:
            ans *= 2
        else:
            if now_tate:
                ans *= 1
            else:
                ans *= 3
        tate = now_tate
        ans = ans % MOD
else:
    ans *= 6
    tate = 0
    skip = 0
    for x, y in zip(a[2:], b[2:]):
        if skip:
            skip = 0
            continue
        if x == y:
            now_tate = 1
        else:
            now_tate = 0
            skip = 1

        if tate:
            ans *= 2
        else:
            if now_tate:
                ans *= 1
            else:
                ans *= 3
        tate = now_tate
        ans = ans % MOD
print(ans % MOD)

Solution (Python):

N=int(input())
Sa=list(input())
Sb=list(input())

MOD=10**9+7

k=0
ans=1
swich=0

while k<N:
    if Sa[k]==Sb[k]:
        k+=1
        if swich==0:
            ans*=3
            ans=ans%MOD
        elif swich==1:
            ans*=2
            ans=ans%MOD
        elif swich==2:
            ans*=1
            ans=ans%MOD
        swich=1
    else:
        k+=2
        if swich==0:
            ans*=6
            ans=ans%MOD
        elif swich==1:
            ans*=2
            ans=ans%MOD
        elif swich==2:
            ans*=3
            ans=ans%MOD
        swich=2
print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  s1=S()
  s2=S()

  i=0
  ans=1
  free=3
  while True:
    if i+1>n:
      return ans%mod

    if i==0:
      if s1[i]==s2[i]:
        ans*=3
        ans%=mod
        i+=1
        free=0
      else:
        ans*=6
        ans%=mod
        i+=2
        free=1
      continue

    if s1[i]==s2[i]:
      if free==0:
        ans*=2
        ans%=mod
      i+=1
      free=0
    else:
      if free==0:
        ans*=2
        ans%=mod
      else:
        ans*=3
        ans%=mod
      i+=2
      free=1


print(main())

Solution (Python):
mod = 10 ** 9 + 7

N = int(input())
S1 = input()
S2 = input()
cnt = 0
if S1[0] == S2[0]:
    cnt += 3
    i = 1
    x = True
else:
    cnt += 6
    i = 2
    x = False

while i < N:
    if S1[i] == S2[i]:
        if x:
            cnt *= 2
        else:
            pass
        x = True
        i += 1
    else:
        if x:
            cnt *= 2
        else:
            cnt *= 3
        x = False
        i += 2
print(cnt % mod)

Solution (Python):
from sys import stdin
mod = 1000000007
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
t = stdin.readline().rstrip()
now = 0
pazzle = ""
while now < n:
    if s[now] == t[now]:
        now += 1
        pazzle += "T"
    else:
        now += 2
        pazzle += "Y"

if pazzle[0] == "T":
    point = 3
else:
    point = 6
for i in range(1,len(pazzle)):
    if pazzle[i-1] == "T" and pazzle[i] == "T":
        point *= 2
        point %= mod
    elif pazzle[i-1] == "T" and pazzle[i] == "Y":
        point *= 2
        point %= mod
    elif pazzle[i-1] == "Y" and pazzle[i] == "Y":
        point *= 3
        point %= mod
print(point)

Solution (Python):
from sys import stdin
from math import factorial
mod = 1000000007
def permutations_count(n, r):
    return factorial(n) // factorial(n - r)
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
t = stdin.readline().rstrip()
now = 0
pazzle = ""
while now < n:
    if s[now] == t[now]:
        now += 1
        pazzle += "T"
    else:
        now += 2
        pazzle += "Y"

if pazzle[0] == "T":
    point = 3
else:
    point = 6
for i in range(1,len(pazzle)):
    if pazzle[i-1] == "T" and pazzle[i] == "T":
        point *= 2
        point %= mod
    elif pazzle[i-1] == "T" and pazzle[i] == "Y":
        point *= 2
        point %= mod
    elif pazzle[i-1] == "Y" and pazzle[i] == "Y":
        point *= 3
        point %= mod
print(point)

Solution (Python):
MOD = 10**9+7
N = int(input())
S1 = input()
S2 = input()
pre_flag = S1[0] == S2[0]
if pre_flag:
    ans = 3
    i = 1
else:
    ans = 6
    i = 2

while i < N:
    flag = S1[i] == S2[i]
    if flag:
        if pre_flag:
            ans =  (ans * 2) % MOD
        i += 1
        pre_flag = flag
        continue
    if pre_flag:
        ans =  (ans * 2) % MOD
    else:
        ans =  (ans * 3) % MOD
    i += 2
    pre_flag = flag
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S1 = input().rstrip('\n')
    S2 = input().rstrip('\n')

    S = [0]
    for i in range(N-1):
        if S1[i+1] == S1[i]:
            S[-1] += 1
        else:
            S.append(0)
    mod = 1000000007
    if S[0] == 0:
        ans = 3
    else:
        ans = 6
    for i in range(len(S)-1):
        if S[i] == 0 and S[i+1] == 0:
            ans = (ans*2)%mod
        elif S[i] == 0 and S[i+1] == 1:
            ans = (ans*2)%mod
        elif S[i] == 1 and S[i+1] == 0:
            pass
        else:
            ans = (ans * 3)%mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s1 = input()
s2 = input()

ans=3
last="X"
i=0

if s1[i] == s2[i]:
    last="x"
    ans=3
    i=1
else:
    last="y"
    ans=6
    i=2

while i < n:
    if s1[i] == s2[i]: 
        if last=="x":
            ans*=2
        last="x"
        i+=1
    else:
        if last=="x":
            ans*=2
        else:
            ans*=3
        last="y"
        i+=2
    ans %= 1000000007
print(ans)

Solution (Python):
def examC():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] += 1
    a = [0,0]
    for key,i in d.items():
        if i>=4:
            if a[1]<key:
                a = [key,key]
            elif a[0]<key:
                a = [key,a[1]]
        elif i>=2:
            if a[1]<key:
                a = [a[1],key]
            elif a[0]<key:
                a = [key,a[1]]
    ans = a[0]*a[1]
    print(ans)
    return

def examD():
    N = I()
    S = [SI() for _ in range(2)]
    ans = 1
    flag = 0
    i = 0
    while(i<N):
        if S[0][i]==S[1][i]:
            if flag==1:
                ans *= 2
            elif flag==0:
                ans *= 3
            flag = 1
        else:
            if flag==0:
                ans *= 6
            elif flag==1:
                ans *= 2
            elif flag==2:
                ans *= 3
            flag = 2
        i += flag
        ans %= mod
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Solution (Python):
N = int(input())
S = input()
i = 0
l = []
while i < N:
    if i + 1 < N:
        if S[i] == S[i + 1]:
            i += 2
            l.append(2)
            continue
    i += 1
    l.append(1)

if l[0] == 1:
    ans = 3
else:
    ans = 6
for i in range(1, len(l)):
    if l[i] == 1:
        if l[i - 1] == 1:
            ans *= 2
    else:
        if l[i - 1] == 1:
            ans *= 2
        else:
            ans *= 3
print(ans % 1000000007)

Solution (Python):


N = int(input())
s1 = input()
s2 = input()
S = [s1, s2]
MOD = 10**9+7

if N == 1:
    print(3)
    exit()


x = 0
ans = 1
while x <= N-1:
    
    if S[0][x] == S[1][x]:
        if x == 0:
            ans *= 3
            x += 1
        else:
            
            if S[0][x-1] == S[1][x-1]:
                ans *= 2
                x += 1
            else:
                
                x += 1
    
    else:
        if x == 0:
            ans *= 3*2
            x += 2
        else:
            
            if S[0][x-1] == S[1][x-1]:
                ans *= 2*1
                x += 2
            else:
                ans *= 3
                x += 2
    ans %= MOD
        
print(ans)

Solution (Python):
MOD = 10**9+7
N = int(input())
S = input()
S2 = input()
lst = []
i = 0
while i < N:
    if i == N-1 or S[i] != S[i+1]:
        lst.append(1)
        i += 1
    else:
        lst.append(2)
        i += 2
if lst[0] == 1:
    ans = 3
else:
    ans = 6
for j in range(1, len(lst)):
    if lst[j-1] == 1:
        ans *= 2
    elif lst[j-1] == 2 and lst[j] == 2:
        ans *= 3
    ans %= MOD
print(ans)

Solution (Python):
M = 10**9+7
N=int(input())
S=input().strip()
T=input().strip()
for i in range(N):
    if i == 0:
        if S[i] == T[i]:
            r = 3
            tmp = 1
        else:
            r = 6
            tmp = 0
        continue
    if S[i] == S[i-1]:
        tmp = 0
        continue
    if tmp:
        r = r*2%M
    elif S[i] != T[i]:
        r = r*3%M
    tmp=1
print(r)

Solution (Python):
n = int(input())
s = str(input())
gomi = str(input())
num = [1]
for i in range(n-1):
  if s[i] == s[i+1]:
    num[-1]+=1
  else:
    num.append(1)
ans = 1
before = 0
for i in range(len(num)):
  if num[i] == 2:
    if before == 1:
      ans *= 2
      before = 2
    elif before == 2:
      ans *= 3
    else:
      ans *= 6
      before = 2
  else:
    if before == 1:
      ans *= 2
    elif before == 2:
      before = 1
    else:
      ans *= 3
      before = 1
  ans %= 10 ** 9 + 7
print(ans)

Solution (Python):
N = int(input())
s1 = input()
s2 = input()
ans = 1
being_horizontal = False
was_horizontal = False
was_vertical = False
MOD = 10**9+7
for i in range(N):

    if not was_horizontal and not being_horizontal and not was_vertical: 
        if s1[i] != s2[i]:
            ans *= 6
            being_horizontal = True
        else:
            ans *= 3
            was_vertical = True
    elif being_horizontal:
        being_horizontal = False
        was_horizontal = True
    elif was_horizontal and s1[i] == s2[i]:
        was_horizontal = False
        was_vertical = True
    elif was_horizontal and s1[i] != s2[i]:
        ans *= 3
        being_horizontal = True
        was_horizontal = False
    elif was_vertical and s1[i] == s2[i]:
        ans *= 2
        was_vertical = True
    elif was_vertical and s1[i] != s2[i]:
        ans *= 2
        was_vertical = False
        being_horizontal = True
    ans %= MOD
print(ans)

Solution (Python):
import sys
bbn=1000000007
	


		
def main():
	n = int(input())
	sa = input()
	sb = input()
	ll=[]
	i=0
	while i < n:
		if sa[i] == sb[i]:
			ll.append(1)
		else:
			ll.append(2)
			i+=1
		i+=1
	
	val= 3 if ll[0]==1 else 6
	vv=[[2,2],[1,3]]
	for pre, now in zip(ll,ll[1:]):
		val *= vv[pre-1][now-1]
		val = val % bbn
		
	print(val)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
pro = 1
i = 0
if S1[0] != S2[0]:
    pro = 6
    i = 2
    two = True
else:
    pro = 3
    i = 1
    two = False
while i < N:
    if S1[i] != S2[i]:
        i += 2
        if two:
            pro *= 3
        else:
            pro *= 2
        two = True
    else:
        i += 1
        if not two:
            pro *= 2
        two = False
print(pro%(10**9+7))

Solution (Python):
p = 10**9+7
N = int(input())
S1 = input().strip()
S2 = input().strip()
cnt = 1
i = 0
if S1[0]==S2[0]:
    cnt = (cnt*3)%p
    flag = 1
    i += 1
else:
    cnt = (cnt*6)%p
    flag = 2
    i += 2
while i<N:
    if S1[i]==S2[i]:
        if flag==1:
            cnt = (cnt*2)%p
        flag = 1
        i += 1
    else:
        if flag==1:
            cnt = (cnt*2)%p
        else:
            cnt = (cnt*3)%p
        flag = 2
        i += 2
print(cnt)