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):
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
S1 = list(input())
S2 = list(input())
a = []
now = 0
while now < N:
    if S1[now] == S2[now]:
        a.append("s")
        now += 1
    else:
        a.append("d")
        now += 2

for i in range(len(a)):
    if i == 0:
        if a[i] == "s":
            ans = 3
        else:
            ans = 6
    else:
        if a[i-1] == "s":
            ans *= 2
        else:
            if a[i] == "d":
                ans *= 3

print(ans%MOD)

Solution (Python):
MOD = 10 ** 9 + 7
N = int(input())
S = iter(input() + " ")
prev = next(S)
count = 0
counts = []
for c in S:
    count += 1
    if prev != c:
        counts.append(count)
        count = 0
    prev = c
counts = iter(counts)
prev = next(counts)
ans = 3 * prev
for count in counts:
    if prev == 1:
        ans *= 2
    elif count == 2:
        ans *= 3
    prev = count
print(ans % MOD)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()
S1 = input()
S2 = input()
dp = [0 for i in range(N)]
if S1[0] == S2[0]:
    dp[0] = 3
else:
    dp[0] = 6







for i in range(1, N):
    
    if S1[i] == S1[i - 1]:
        dp[i] = dp[i - 1]
    
    else:
        
        if S1[i] == S2[i]:
            
            if S1[i - 1] == S2[i - 1]:
                dp[i] = (dp[i - 1] * 2) % mod
            
            else:
                dp[i] = dp[i - 1]
        
        else:
            
            if S1[i - 1] == S2[i - 1]:
                dp[i] = (dp[i - 1] * 2) % mod
            
            else:
                dp[i] = (dp[i - 1] * 3) % mod
print(dp[-1])

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

mod=1000000007

x=0
cnt=1
while x<n:
    if x==0:
        if s1[x]==s2[x]:
            cnt*=3%mod
            x+=1
        else:
            cnt*=6%mod
            x+=2
    else:
        if s1[x-1]==s2[x-1]:
            
            
            if s1[x]==s2[x]:
                cnt*=2%mod
                x+=1
            
            
            
            else:
                cnt*=2%mod
                x+=2
        else:
            
            
            if s1[x]==s2[x]:
                cnt*=1%mod
                x+=1
            
            
            else:
                cnt*=3%mod
                x+=2

print(cnt%mod)

Solution (Python):
N = int(input())
s = input()
t = input()

mod = int(1e9)+7

ans = 1
bef = 0
i = 0
while i < N:
    
    if bef == 0:
        if s[i] == t[i]:
            bef = 1
            ans *= 3
        else:
            bef = 2
            ans *= 6
            i += 1
    elif bef == 1:
        if s[i] == t[i]:
            ans = (ans*2)%mod
        else:
            bef = 2
            ans = (ans*2)%mod
            i += 1
    else:
        if s[i] == t[i]:
            bef = 1
        else:
            ans = (ans*3)%mod
            i += 1
    i += 1

print(ans%mod)

Solution (Python):
def main():
    n = int(input())
    s1 = input()
    s2 = input()
    mod = 10**9 + 7
    h = "h"
    v = "v"
    d = ""
    i = 0
    while i < n:
        if s1[i] == s2[i]:
            d += v
        else:
            d += h
            i += 1
        i += 1
    c = 3 + 3 * (d[0] == h)
    for i in range(len(d) - 1):
        if d[i] == v:
            c = c * 2 % mod
        else:
            if d[i + 1] == h:
                c = c * 3 % mod
    print(c)

if __name__ == '__main__':
    main()

Solution (Python):
import sys


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


sys.setrecursionlimit(10 ** 9)


MOD = 1000000007


def main():
    N = int(input())
    S1 = input()
    S2 = input()
    answer = 1
    cnt = 0
    while cnt < N:
        if cnt == 0:
            if S1[0] == S2[0]:
                answer *= 3
                cnt += 1
            else:
                answer *= 6
                cnt += 2
        else:
            if S1[cnt - 1] == S2[cnt - 1]:
                if S1[cnt] == S2[cnt]:
                    answer *= 2
                    cnt += 1
                else:
                    answer *= 2
                    cnt += 2
            else:
                if S1[cnt] == S2[cnt]:
                    answer *= 1
                    cnt += 1
                else:
                    answer *= 3
                    cnt += 2
        answer %= MOD

    print(answer % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
mod = 10**9 + 7
ans = -1
for i, c in enumerate(s1):
    if i==0:
        if s1[i]==s2[i]:
            ans = 3
        else:
            ans = 6
    else:
        if s1[i-1]==s1[i] and s2[i-1]==s2[i]:
            continue
        elif s1[i-1]==s2[i-1] and s1[i]==s2[i]:
            ans *= 2
        elif s1[i-1]==s2[i-1] and s1[i]!=s2[i]:
            ans *= 2
        elif s1[i-1]!=s2[i-1] and s1[i]==s2[i]:
            ans *= 1
        else:
            ans *= 3
        ans %= mod
print(ans%mod)

Solution (Python):
n = int(input())
ty = [0]*n 
s1 = input()
prev = ""
cnt = 0
for i in range(n):
    if prev == s1[i]:
        ty[i] = 1
        ty[i-1] = 1
    prev = s1[i]
ans = 1
mod = 10**9+7
f = 0
if ty[0] ==0:
    ans = 3
else:
    ans = 6
    f = 1

for i in range(1,n):
    if f==1:
        f = 0
        continue

    if ty[i] ==1:
        f = 1
        if ty[i-1] ==1:
            ans = ans*3 %mod
        else:
            ans = ans*2 %mod
    elif ty[i] == 0:
        if ty[i-1] == 0:
            ans = ans*2 %mod
        else:
            ans = ans*1
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    S1 = readline().rstrip()
    S2 = readline().rstrip()
    if S1[0] == S2[0]:
        cnt = 3
        i = 1
        pre = 'x'
    else:
        cnt = 6
        i = 2
        pre = 'y'
    while i < N:
        if S1[i] == S2[i]:
            next = 'x'
        else:
            next = 'y'
        if pre == next == 'x':
            cnt *= 2
            i += 1
        elif pre == next == 'y':
            cnt *= 3
            i += 2
        elif pre == 'x' and next == 'y':
            cnt *= 2
            i += 2
        else:
            i += 1
        pre = next

    print(cnt % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = [list(input()) for i in range(2)]
i = 0
ans = 1
mod = 10**9+7
if S[0][i]==S[1][i]:
    ans = 3
    i += 1
    flag = 0
else:
    ans = 6
    i += 2
    flag = 1
while i<N:
    if flag==0 and S[0][i]==S[1][i]:
        ans *= 2
        ans %= mod
        i += 1
        flag = 0
    elif flag == 1 and S[0][i]==S[1][i]:
        i += 1
        flag = 0
    elif flag == 0 and S[0][i]!=S[1][i]:
        ans *= 2
        ans %= mod
        i += 2
        flag = 1
    else:
        ans *= 3
        ans %= mod
        i += 2
        flag = 1
print(ans)

Solution (Python):
import sys

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


def resolve():
    n = int(input())
    S1 = input()
    S2 = input()

    Domino = []
    i = 0
    while i < n:
        if S1[i] == S2[i]:
            Domino.append("X")
            i += 1
        else:
            Domino.append("Y")
            i += 2

    res = 3 if Domino[0] == "X" else 6
    for i in range(1, len(Domino)):
        if Domino[i] == "X" and Domino[i - 1] == "X":
            res = res * 2 % mod
        elif Domino[i] == "X" and Domino[i - 1] == "Y":
            pass
        elif Domino[i] == "Y" and Domino[i - 1] == "X":
            res = res * 2 % mod
        else:
            res = res * 3 % mod

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):

n = int(input())
s = [input(), input()]
mod = 10**9+7
i = 0
ans = 3
pre = 0

while i < n:
    if s[0][i] == s[1][i]:
        typ = 1
        i += 1
    else:
        typ = 2
        i += 2
    if pre == 0 and typ == 2:
        ans *= 2
    elif pre == 1:
        ans = (ans*2)%mod
    elif pre == 2 and typ == 2:
        ans = (ans*3)%mod
    pre = typ
print(ans)

Solution (Python):
n=int(input())
l1=[str(x) for x in input()]
l2=[str(x) for x in input()]

if l1[0]==l2[0]:
    pat=3
    typ='lon'
else:
    pat=6
    typ='lat'
for i in range(1,n):
    if l1[i]!=l1[i-1]:
        if typ=='lon':
            if l1[i]==l2[i]:
                pat *= 2
            else:
                pat *= 2
                typ='lat'
        else:
            if l1[i]==l2[i]:
                typ='lon'
            else:
                pat *= 3
print(pat%(10**9+7))

Solution (Python):
N = int(input())
S = [input() for _ in range(2)]

ans = 0
mod = 10 ** 9 + 7
prev = False
cur = False
for i in range(N):
    if cur:
        cur = False
        continue

    if S[0][i] == S[1][i]:
        if i == 0:
            ans = 3
        elif not prev:
            ans = ans * 2 % mod
        cur = False
        prev = False
    else:
        if i == 0:
            ans = 6
        elif prev:
            ans = ans * 3 % mod
        else:
            ans = ans * 2 % mod
        cur = True
        prev = True

print(ans)

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

mat=[]
for i in range(2):
  mat.append(list(input()))


dp=[1]+[0]*N
i=1
while i<N+1:
  if mat[0][i-1]==mat[1][i-1]:
    if i==1:
      dp[1]=3
    else:
      if mat[0][i-2]==mat[1][i-2]:
        dp[i]=2*dp[i-1]
        dp[i]%=MOD
      else:
        dp[i]=dp[i-1]
  else:
    if i==1:
      dp[1]=dp[2]=6
      i+=1
    else:
      if mat[0][i-2]==mat[1][i-2]:
        dp[i]=dp[i+1]=2*dp[i-1]
        dp[i]%=MOD
        dp[i+1]%=MOD
        i+=1
      else:
        dp[i]=dp[i+1]=3*dp[i-1]
        dp[i]%=MOD
        dp[i+1]%=MOD
        i+=1
  i+=1
        

print(dp[-1])

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
ans = 1
ch1 = 1
N = 1000000007
s1+='?'

if s1[0]==s1[1]:
    ch2=2
    ans=6
    s=3
else:
    ch2=1
    ans=3
    s=2

for i in range(s,n+1):
        if s1[i]==s1[i-1]:
            ch1+=1
        else:
            if ch1 ==1:
                if ch2==2:
                    ans*=1
                else:
                    ans=ans*2%N
            else:
                if ch2==2:
                    ans=ans*3%N
                else:
                    ans=ans*2%N
            ch2=ch1
            ch1=1

print(ans)

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

ans = 1
pre = None
i = 0
while i < N:
    if pre is None:
        if S1[i] == S2[i]:
            ans = ans*3 % mod
            pre = 'x'
            i += 1
        else:
            ans = ans*6 % mod
            pre = 'y'
            i += 2
    elif pre == 'x':
        if S1[i] == S2[i]:
            ans = ans*2 % mod
            pre = 'x'
            i += 1
        else:
            ans = ans*2 % mod
            pre = 'y'
            i += 2
    elif pre == 'y':
        if S1[i] == S2[i]:
            ans = ans*1 % mod
            pre = 'x'
            i += 1
        else:
            ans = ans*3 % mod
            pre = 'y'
            i += 2

print(ans % mod)

Solution (Python):
n=int(input())
s1=input()
s2=input()
mod=10**9+7
ans=3
for i in range(1,n):
  if i==1 or s1[i-1]==s2[i-1]:
    ans*=2
  elif not s1[i-1]==s1[i] and not s1[i]==s2[i]:
    ans*=3
print(ans%mod)

Solution (Python):
MOD = 1000000007

n = int(input())
s1 = input()
s2 = input()

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

while i<n:
    
    if s1[i] == s2[i]:
        i += 1
        if prev == 1:
            ans *= 2
        else:
            prev = 1
    else:
        i += 2
        if prev == 1:
            ans *= 2
            prev = 2
        else:
            ans *= 3
    ans %= MOD

print(ans)

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

ans=0
MOD= 1000000007
cnt=0
ptn=-1
while cnt<n:
    if a[cnt]==b[cnt]:
        if cnt==0:
            ans=3
            ptn=0
        else:
            if ptn==0:
                ans*=2
                ptn=0
            else:
                ans*=1
                ptn=0
        cnt+=1
    else:
        if cnt==0:
            ans=6
            ptn=1
        else:
            if ptn==0:
                ans*=2
                ptn=1
            else:
                ans*=3
                ptn=1
        cnt+=2
    ans%=MOD

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    S=[list(input()) for _ in range(2)]
    ans=1
    prev=0
    i=0
    while i<N:
        if S[0][i]==S[1][i]:
            ans*=3-prev
            prev=1
            i+=1
        else:
            if prev==0:
                ans*=6
            elif prev==1:
                ans*=2
            else:
                ans*=3
            prev=2
            i+=2
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
mod = 10 ** 9 + 7
if n == 1:
    print(3)
    exit()
if s[0] == s[1]:
    i = 2
    rslt = 6
    flag = True
else:
    i = 1
    rslt = 3
    flag = False
while i < n:
    if i != n-1 and s[i] == s[i + 1]:
        if flag:
            rslt = rslt * 3 % mod
        else:
            rslt = rslt * 2 % mod
        i += 2
        flag = True
    else:
        if not flag:
            rslt = rslt * 2 % mod
        i += 1
        flag = False

print(rslt)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
ans = 1
mod = 1000000007
i = 0
while i < N:
    if i == 0:
        if S1[i] == S2[i]:
            ans *= 3
            i += 1
        else:
            ans *= 6
            i += 2
    else:
        if S1[i] == S2[i]:
            if S1[i-1] == S2[i-1]:
                ans *= 2
                ans %= mod
                i += 1
            else:
                ans *= 1
                ans %= mod
                i += 1
        else:
            if S1[i-1] == S2[i-1]:
                ans *= 2
                ans %= mod
                i += 2
            else:
                ans *= 3
                ans %= mod
                i += 2
print(ans)

Solution (Python):


data = int(input())

data1 = [input(), input()]

mod = 10**9+7

i = 1 + (data1[0][0] != data1[1][0])

ans = 3 * i

while i < data:
    p = data1[0][i-1] == data1[1][i-1]
    if data1[0][i] == data1[1][i]:
        ans *= 1 + p
        i += 1
    else:
        ans *= 3 - p
        i += 2
    ans %= mod

print(ans)

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

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

MOD = 10**9+7
ans = 3 * ptn[0]
for a,b in zip(ptn,ptn[1:]):
    if a == 1 and b == 1:
        ans *= 2
    elif a == 1 and b == 2:
        ans *= 2
    elif a == 2 and b == 2:
        ans *= 3
    ans %= MOD
print(ans)

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

mod = 10**9+7

if s1[0] == s2[0]:
    ans = 3
    bfr = 'T'
    idx = 1
else:
    ans = 6
    bfr = 'Y'
    idx = 2

if n == 1:
    print(ans)
    exit()

while idx <= n-1:
    if s1[idx] == s2[idx]:
        if bfr == 'T':
            ans *= 2
            ans %= mod
        idx += 1
        bfr = 'T'
    else:
        if bfr == 'T':
            ans *= 2
            ans %= mod
        else:
            ans *= 3
            ans %= mod
        idx += 2
        bfr = 'Y'
        
print(ans%mod)

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


n = int(input())
s1 = input(); s2 = input()

s = ""
i = 0
while i < n:
    if s1[i] == s2[i]:
        s += "A"
        i += 1
    else:
        s += "B"
        i += 2

answer = 3 if s[0] == "A" else 6
for i in range(len(s) - 1):
    if s[i] + s[i + 1] == "AA":
        answer *= 2
    elif s[i] + s[i + 1] == "AB":
        answer *= 2
    elif s[i] + s[i + 1] == "BA":
        answer *= 1
    else:
        answer *= 3
    answer %= mod

print(answer)

Solution (Python):
n= int(input())
s1=input()
s2=input()
index=0
s=''
while index<n:
    if s1[index]==s2[index]:
        index+=1
        s=s+'t'
    else:
        index+=2
        s=s+'y'
adict = {'tt':2,'ty':2,'yt':1,'yy':3}
ans = 0
if s[0]=='t':ans=3
else:ans=6
for i in range(len(s)-1):
    ans = (ans%1000000007) * (adict[s[i:i+2]]%1000000007) % 1000000007
print(ans)

Solution (Python):
n=int(input())
s1=input()
s1_=list(s1)
s2=input()
for i in range(len(s1)-1):
  if s1[i]==s1[i+1]:
    idx=s1_.index(s1[i])
    s1_[idx+1]='1'
    del s1_[idx]
mod=10**9+7
if s1_[0]=='1':
  ans=6
else:
  ans=3

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

Solution (Python):
from itertools import groupby
n = int(input())
list_S = input()
list_E = input()
list_MAP = []
list_C = groupby(list_S)
for num, gr in list_C:
    list_MAP.append(len(list(gr)))
ans = 1
if list_MAP[0] == 2:
    ans *= 6
else:
    ans *= 3

for i in range(1, len(list_MAP)):
    if list_MAP[i-1] == 1 and list_MAP[i] == 1:
        ans *= 2


    if list_MAP[i-1] == 1 and list_MAP[i] == 2:
        ans *= 2


    if list_MAP[i-1] == 2 and list_MAP[i] == 1:
        ans *= 1


    if list_MAP[i-1] == 2 and list_MAP[i] == 2:
        ans *=3



ans = ans % 1000000007
print(ans)

Solution (Python):
MOD = 10**9 + 7
N = int(input())
S = input()
S2 = input()
check = []
flg = False
for i in range(N-1):
    if flg:
        check.append(2)
        flg = False
        continue
    if S[i] == S[i+1]:
        flg = True
    else:
        check.append(1)
if flg:
    check.append(2)
else:
    check.append(1)
ans = 3 if check[0] == 1 else 6
for i in range(1,len(check)):
    if check[i-1] == 1:
        ans *= 2
    elif check[i] == 2 and check[i-1] == 2:
        ans *= 3
print(ans%MOD)

Solution (Python):
import sys
import heapq
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


n = int(input())
s1 = input()
s2 = input()
ans = 1
v = False
h1 = False
h2 = False
for i in range(n):
    if i == 0:
        if s1[i] == s2[i]:
            ans *= 3
            v = True
        else:
            ans *= 6
            h1 = True
    else:
        if v:
            if s1[i] == s2[i]:
                ans *= 2
                v = True
                h1 = False
                h2 = False
            else:
                ans *= 2
                v = False
                h1 = True
                h2 = False
        elif h1:
            v = False 
            h1 = False
            h2 = True
        else:
            if s1[i] == s2[i]:
                v = True
                h1 = False
                h2 = False
            else:
                ans *= 3
                v = False
                h1 = True
                h2 = False
    ans %= mod
            
print(ans)

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

n = int(input())
s1 = input()
s2 = input()
ans = 1

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

t = [[2, 2], [1, 3]]
while True:
    if i >= n:
        break
    if s1[i] == s2[i]:
        pat = 0
        i += 1
    else:
        pat = 1
        i += 2
    ans *= t[pre_pat][pat]
    ans %= MOD
    
    pre_pat = pat
print(ans)

Solution (Python):













n = int(input())
s1, s2 = input(), input()
ans = 0
idx = 0
MOD = 10**9 + 7
pre = -1  
while idx < n:
    if s1[idx] == s2[idx]:
        if idx == 0:
            ans = 3
        else:
            if pre == 1:
                ans *= 2
            elif pre == 2:
                ans *= 1  
        pre = 1
        idx += 1
    else:
        if idx == 0:
            ans = 6
        else:
            if pre == 1:
                ans *= 2
            elif pre == 2:
                ans *= 3
        pre = 2
        idx += 2
    ans %= MOD

print(ans)

Solution (Python):
import sys
n = int(input())
s = input()
t = []

if (len(s)==1):
    print(3)
    sys.exit()
if (len(s)==2):
    print(6)
    sys.exit()

for i in range(len(s)-1):
    if (i>0):
        if(s[i-1]==s[i]):
            if (i == len(s)-2):
                t.append(1)
                continue
            else:
                continue
        elif (i == len(s)-2 and s[i]!=s[i+1]):
            t.append(1)
            
    
    if (s[i]==s[i+1]):
        t.append(2)
    else:
        t.append(1)

if (t[0]==1):
    ans = 3
else:
    ans = 6

for i in range(len(t)-1):
    
    if (t[i]==1):
        if (t[i+1]==1):
            ans *= 2
        else:
            ans *= 2
    else:
        if (t[i+1]==1):
            ans *= 1
        else:
            ans *= 3
print(ans % 1000000007)

Solution (Python):
N = int(input())
S = [input() for _ in range(2)]

MOD = 1000000007
i = 0
C = []
while i < N:
    if S[0][i] == S[1][i]:
        C.append(0)
        i += 1
    else:
        C.append(1)
        i += 2

ans = 3 if C[0] == 0 else 6
for i in range(len(C) - 1):
    if C[i] == 0:
        ans = ans * 2 % MOD
    elif C[i + 1] == 1:
        ans = ans * 3 % MOD
print(ans)

Solution (Python):
n = int(input())
s = input()
t = input()
u = []
flg = 0
mod = 10**9+7
for i in range(n):
	if s[i] == t[i]:
		u.append(1)
	else:
		if flg == 1:
			u.append(0)
			flg = 0
		else:
			flg = 1
if u[0] == 1:
	ans = 3
else:
	ans = 6
for i in range(len(u)-1):
	if u[i] == 1 and u[i+1] == 1:
		ans *= 2
	elif u[i] == 1 and u[i+1] == 0:
		ans *= 2
	elif u[i] == 0 and u[i+1] == 1:
		continue
	else:
		ans *= 3
	ans %= mod
print (ans)

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

MOD = 1000000007


pattern = []
i = 0
while i < N - 1:
    if S1[i] == S1[i + 1]:
        pattern.append('-')
        i += 2
    else:
        pattern.append('|')
        i += 1
else:
    if i == N - 1:
        pattern.append('|')

cnt = 3 if pattern[0] == '|' else 6
for i in range(1, len(pattern)):
    l = pattern[i - 1]
    r = pattern[i]
    if (l, r) == ('|', '|'):
        cnt *= 2
    elif (l, r) == ('|', '-'):
        cnt *= 2
    elif (l, r) == ('-', '|'):
        cnt *= 1
    elif (l, r) == ('-', '-'):
        cnt *= 3
    else:
        raise Exception
    cnt %= MOD

print(cnt)

Solution (Python):
n=int(input())
s=[list(input()) for i in range(2)]
mod=10**9+7
idx=0
dp=[0]*n
if s[0][0]==s[1][0]:
  dp[0]=3
  idx+=1
else:
  dp[0]=6
  dp[1]=dp[0]
  idx+=2
while idx<n:
  if s[0][idx]==s[1][idx] and s[0][idx-1]!=s[1][idx-1]:
    dp[idx]=dp[idx-1]
    idx+=1
  elif s[0][idx]!=s[1][idx] and s[0][idx-1]==s[1][idx-1]:
    dp[idx+1]=dp[idx]=(dp[idx-1]*2)%mod
    idx+=2
  elif s[0][idx]==s[1][idx] and s[0][idx-1]==s[1][idx-1]:
    dp[idx]=(dp[idx-1]*2)%mod
    idx+=1
  else:
    dp[idx+1]=dp[idx]=(dp[idx-1]*3)%mod
    idx+=2
print(dp[n-1])

Solution (Python):
mod = int(1e9) + 7

n = int(input())
s1 = input()
s2 = input()

if s1[0] == s2[0]:
    ans = 3
    i = 1
else:
    ans = 6
    i = 2
while i < n:
    
    if s1[i] == s2[i]:

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

        if s1[i-1] == s2[i-1]:
            ans *= 2
            ans %= mod
        else:
            ans *= 3
            ans %= mod
        i += 2
print(ans)

Solution (Python):


def submit():
    n = int(input())
    s1 = input()
    s2 = input()
    modp = 1000000007

    curr = 0
    ans = 1
    prev = 0 
    while curr < n:
        if s1[curr] == s2[curr]:
            
            if prev == 0:
                ans = 3
            elif prev == 1:
                ans *= 2
                ans %= modp
            prev = 1
            curr += 1
        else:
            if prev == 0:
                ans = 6
            elif prev == 1:
                ans *= 2
                ans %= modp
            else:
                ans *= 3
                ans %= modp
            prev = 2
            curr += 2
    print(ans)


submit()

Solution (Python):


def main():
    n = int(input())
    s1 = input()
    s2 = input()
    i = 0
    res = 1
    while i < n:
        if i == 0:
            if s1[i] == s2[i]:
                res *= 3
                i += 1
                pretwo = False
            else:
                res *= 6
                i += 2
                pretwo = True
        else:
            if s1[i] == s2[i]:
                res *= (1 if pretwo else 2)
                i += 1
                pretwo = False
            else:
                res *= (3 if pretwo else 2)
                i += 2
                pretwo = True
    print(res % (10 ** 9 + 7))

if __name__ == "__main__":
    main()

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

ans = 1

T = [0] * len(S1)

if S1[0] == S2[0]:
    T[0] = 1
else:
    T[0] = T[1] = 1
    ans *= 2

ans *= 3
MOD = 10 ** 9 + 7

for i in range(len(S1)-1):
    if T[i] == 0:
        T[i] = 1
        if S1[i] == S1[i+1]:  
            T[i+1] = 1
            if S1[i-1] == S2[i-1]:  
                ans *= 2
                ans %= MOD
            else:  
                ans *= 3
                ans %= MOD

        else:  
            if S1[i-1] == S2[i-1]:  
                ans *= 2
                ans %= MOD
            else:  
                pass

if T[-1] == 0:
    if S1[-2] == S2[-2]:
        ans *= 2
        ans %= MOD

print(ans)

Solution (Python):
n=int(input())
s1=input()
s2=input()
if s1[0]==s2[0]:
    i=1
else:
    i=0
ans=3

flag=False
while i<n:
    if s1[i]==s2[i]:
        if flag:
            flag=False
            i+=1
        else:
            ans*=2
            i+=1
    else:
        if flag:
            ans*=3
            i+=2
        else:
            ans*=2
            i+=2
            flag=True

print(ans%(10**9+7))

Solution (Python):
n=int(input())
s1=input()
s2=input()
if n>1:
    if s1[0]==s1[1]:
        i=0
    else:
        i=1
else:
    i=1
ans=3

flag=False
while i<n:
    if i<n-1:
        if s1[i]==s1[i+1]:
            if flag:
                ans*=3
                i+=2
            else:
                ans*=2
                i+=2
                flag=True
        else:
            if flag:
                flag=False
                i+=1
            else:
                ans*=2
                i+=1
    else:
        if flag:
            flag=False
            i+=1
        else:
            ans*=2
            i+=1
print(ans%(10**9+7))

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

lis = []
i = 0
while i < N:
  if i == N-1:
    lis.append(1)
    i += 1
  elif S1[i] == S1[i+1]:
    lis.append(2)
    i += 2
  else:
    lis.append(1)
    i += 1

ans = 3
if lis[0]==2:
  ans = 6
for i in range(len(lis)-1):
  if lis[i]==2:
    if lis[i+1]==2:
      ans *= 3
  else:
    ans *= 2
  ans %= 10**9+7
print(ans)