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):
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor


"""
need to consider the case that ticket is not enough to lower everything
"""

N = gi()
S1 = gw()
S2 = gw()

i = 1
ans = 3

if (N > 1 and S1[0] == S1[1]):
    i = 2
    ans = 6

while i < N:
    isV = S1[i - 1] == S2[i - 1]
    if S1[i] == S2[i]:
        if isV:
            ans *= 2
            ans %= MOD
        i += 1
    else:
        if isV:
            ans *= 2
        else:
            ans *= 3
        ans %= MOD
        i += 2

print(ans)

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

p=[]
i=0
while i<N:
    if S1[i]==S2[i]:
        p.append(0)
        i+=1
    else:
        p.append(1)
        i+=2

ans=3 if p[0]==0 else 6
for i in range(1,len(p)):
    if p[i]==0 and p[i-1]==0:
        ans=ans*2%MOD
    if p[i]==0 and p[i-1]==1:
        ans=ans*1%MOD
    if p[i]==1 and p[i-1]==0:
        ans=ans*2%MOD
    if p[i]==1 and p[i-1]==1:
        ans=ans*3%MOD

print(ans)

Solution (Python):
N=int(input())
S1=input()
S2=input()
LIST=[]
i=0
while(N>i):
    if(S1[i]==S2[i]):
        LIST.append(1)
    else:
        LIST.append(0)
        i+=1
    i+=1

s=1
t=9
for i in range(len(LIST)):
    if(t==0):
        if(LIST[i]==0):
            s*=3
        else:
            s*=1
    elif(t==1):
        if(LIST[i]==0):
            s*=2
        else:
            s*=2
    else:
        if(LIST[i]==0):
            s*=6
        else:
            s*=3
    t=LIST[i]
    s=s%1000000007
print(s)

Solution (Python):
mod=10**9+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=ans*3%mod
        else:
            ans=ans*2%mod
        i+=2
    elif S1[i]==S2[i]:
        if S1[i-1]==S2[i-1]:
            ans=ans*2%mod
        i+=1

print(ans)

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

mod=10**9+7

if S1[0]==S2[0]:
    cnt=3
    i=1
    f=0
if S1[0]!=S2[0]:
    cnt=6
    i=2
    f=1

while i<N:
    if S1[i]==S2[i]:
        if f==0:
            cnt=(cnt*2)%mod
        elif f==1:
            cnt=(cnt*1)%mod
        i+=1
        f=0
    elif S1[i]!=S2[i]:
        if f==0:
            cnt=(cnt*2)%mod
        elif f==1:
            cnt=(cnt*3)%mod
        i+=2
        f=1

print(cnt)

Solution (Python):
N=int(input())
S=list(input())
T=list(input())
state=[]
lim=1000000007
i=0
while i<N:
    if S[i] == T[i]:
        state.append(0)
        i+=1
    else:
        state.append(1)
        i+=2
if state[0]==0:
    ans=3
else:
    ans=6
for i in range(1,len(state)):
    if state[i] == 1 and state[i-1] == 1:
        ans = (ans * 3) % lim
    elif state[i] == 1 and state[i-1] == 0:
        ans = (ans * 2) % lim
    elif state[i] == 0 and state[i-1] == 1:
        pass
    elif state[i] == 0 and state[i-1] == 0: 
        ans = (ans * 2) % lim
print(ans)

Solution (Python):
import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  

N = ri()
MOD = 10 ** 9 + 7
S1 = rs()
S2 = rs()
color = [None] * N

answer = 1
pattern = 0 

for i in range(N):
    if color[i] != None:
        continue
    if S1[i] == S2[i]:
        answer *= 3 - pattern
        pattern = 1
    else:
        answer *= [6, 2, 3][pattern]
        color[i+1] = 1
        pattern = 2

print(answer%MOD)

Solution (Python):
N = int(input())
A = [input() for _ in range(2)]
mod = 10**9+7
ptn = []
for i in range(N-1):
    if A[0][i] == A[0][i+1]:
        ptn.append("=")
    elif A[0][i] == A[1][i]:
        ptn.append("|")
if A[0][-1] == A[1][-1]:
    ptn.append("|") 

if ptn[0] == "|":
    ans = 3
else:
    ans = 6
for i in range(1,len(ptn)):
    if (ptn[i-1],ptn[i]) == ("|","|"):
        ans = ans * 2 % mod
    elif (ptn[i-1],ptn[i]) == ("=","="):
        ans = ans * 3 % mod
    elif (ptn[i-1],ptn[i]) == ("|", "="):
        ans = ans * 2 % mod
    else:
        continue
print(ans)

Solution (Python):
N=int(input())
S1=list(input())
S2=list(input())
mod=1000000007

ty=[]
i=0
while i<N:
  if S1[i]==S2[i]:
    ty.append(1)
    i+=1
  else:
    ty.append(0)
    i+=2
    
if ty[0]==0:
  ans=6
else:
  ans=3
  
for i in range(1,len(ty)):
  if ty[i-1]==0:
    if ty[i]==0:
      ans=(ans*3)%mod
  else:
    ans=(ans*2)%mod
    
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    s1=input()
    s2=input()
    if s1[0]==s2[0]:
        ans=3
        index=1
        key=0
    else:
        ans=6
        index=2
        key=1
    while index<=n-1:
        if s1[index]==s2[index]:
            if key==0:
                ans=(ans*2)%mod
                index+=1
            else:
                key=0
                index+=1
                continue
        else:
            if key==0:
                ans=(ans*2)%mod
                index+=2
                key=1
            else:
                ans=(ans*3)%mod
                index+=2
    print(ans)
if __name__ == "__main__":
    main()

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

N = int(input())
S1 = input()
S2 = input()
pattern = []
i = 0
while i < N:
    if i == N - 1 or S1[i] != S1[i+1]:
        pattern.append(1)
        i += 1
    else:
        pattern.append(2)
        i += 2
dp = [1 for _ in range(len(pattern) + 1)]
for i in range(len(pattern)):
    if i == 0:
        if pattern[0] == 1:
            dp[i+1] = 3
        else:
            dp[i+1] = 6
    elif pattern[i-1] == 1:
        dp[i+1] = (dp[i] * 2) % MOD
    elif pattern[i-1] == pattern[i] == 2:
        dp[i+1] = (dp[i] * 3) % MOD
    else:
        dp[i+1] = dp[i]
print(dp[-1])

Solution (Python):
n=int(input())
s_1=str(input())
s_2=str(input())
i=0
if s_1[0]==s_2[0]:
    ans=3
    c=1
    i+=1
else:
    ans=6
    c=2
    i+=2
while i<n:
    if s_1[i]==s_2[i]:
        if c==1:
            ans=ans*2%(1000000007)
        c=1
        i+=1
    else:
        if c==2:
            ans=ans*3%(1000000007)
        else:
            ans=ans*2%(1000000007)
        c=2
        i+=2
print(ans%(1000000007))

Solution (Python):
N = int(input())
S = []
S += [input()]
S += [input()]

idx = 0
if S[0][idx]==S[1][idx]:
    flag = 0
    cnt = 3
    idx +=1
elif S[0][idx]!=S[1][idx]:
    flag = 1
    cnt = 6
    idx +=2

while idx<N:
  tmp = [S[0][idx],S[1][idx]]
  if flag == 0:
    if S[0][idx]==S[1][idx]:
      cnt *=2
      flag = 0
      idx +=1
    else:
      cnt *=2
      flag =1
      idx +=2
  elif flag ==1:
    if S[0][idx]==S[1][idx]:
      cnt *=1
      flag = 0
      idx +=1
    else :
      cnt *=3
      flag =1
      idx +=2

print(cnt%1000000007)

Solution (Python):
N = int(input())
s1 = input()
s2 = input()
MOD = 1000000007
state = -1
ans = 1
flag = False
for i in range(N):
  if i+1<N:
    if s1[i]==s1[i+1]:
      flag = True
      continue
    if flag:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 3
      else:
        ans *= 6
      state = 2
    else:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 1
      else:
        ans *= 3
      state = 1
    flag = False
  else:
    if flag:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 3
      else:
        ans *= 6
    else:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 1
      else:
        ans *= 3
  ans %= MOD
print(ans)

Solution (Python):
n = int(input())
U = list(input())
input()

mod = 1000000007

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

idx = 0
li = []
while idx < len(U) - 1:
  if U[idx] == U[idx + 1]:
    li.append(2)
    idx += 1
  else:
    li.append(1)
  idx += 1
if U[-1] != U[-2]:
  li.append(1)

ans = 1
pre = li[0]

if pre == 1:
  ans = ans * 3 % mod
else:
  ans = ans * 6 % mod
  
for i in li[1:]:
  if pre == 1:
    ans = ans * 2 % mod
  else:
    if i == 2:
      ans = ans * 3 % mod
  pre = i

print(ans)

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline

N = int(input())
S = [list(input())[: -1] for _ in range(2)]

h = 0
v = 0
x = [0] * N
mod = 10 ** 9 + 7
for i in range(N):
  if S[0][i] == S[1][i]:
    v += 1
    x[i] = 1
for i in range(N - 1):
  if S[0][i] == S[0][i + 1]:
    h += 1
    x[i] = 0
res = 3
i = 0
if x[0] == 0:
  i += 2
  res *= 2
else: i += 1
while i < N:
  
  if x[i] == 0:
    if x[i - 1] == 0:
      res *= 3
      res %= mod
    else:
      res *= 2
      res %= mod
    i += 1
  else:
    if x[i - 1] != 0:
      res *= 2
      res %= mod
  i += 1


print(res)

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

S1 = input()
S2 = input()

if S1[0] == S2[0]:
	res = 3
	i = 1
	form = "S"
else:
	res = 6
	i = 2
	form = "B"

while i < N:
	if S1[i] == S2[i]:
		if form == "S":
			res = res*2
		form = "S"
		i += 1
	else:
		if form == "S":
			res = res*2
		else:
			res = res*3
		form = "B"
		i += 2

print(res%md)

Solution (Python):
n=int(input())
w1=input()
w2=input()
count=1
now=0
frag=True
while now<n:
  if w1[now]==w2[now]:
    if now==0:
      count*=3
    else:
      if frag:
        count*=2
      else:
        count*=1
        frag=True
    now+=1
  else:
    if now==0:
      count*=6
    else:
      if frag:
        count*=2
      else:
        count*=3
    now+=2
    frag=False
print(count%(10**9+7))

Solution (Python):
n=int(input())
a=input()
b=input()
mod=10**9+7
ans=0
i=1
mae=-1
if a[0]==b[0]:
    ans=3
    mae=1
else:
    ans=6
    i+=1
    mae=0

while i<n:
    if a[i]==b[i]:
        if mae:
            ans*=2
        else:
            pass

        i+=1
        mae=1
    else:
        if mae:
            ans*=2
        else:
            ans*=3
        i+=2
        mae=0
    ans%=mod
print(ans%mod)

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

    print(cnt)




if __name__ == "__main__":
    main()

Solution (Python):
MOD = 1000000007
N = int(input())
S1 = list(input())
S2 = list(input())

if S1[0] == S2[0]:
    ans = 3
    tmp = True 
    j = 1 
else:
    ans = 6
    tmp = False
    j = 2

while j < N:
    if S1[j] == S2[j]: 
        if tmp: 
            ans *= 2
        else: 
            ans *= 1
        tmp = True
        j += 1
    else: 
        if tmp: 
            ans *= 2
        else: 
            ans *= 3
        tmp = False
        j += 2
    ans %= MOD

print (ans)

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
memo_ls = [0 for j in range(n)]
ind = 0
while ind < n:
    if s1[ind] == s2[ind]:
        if ind == 0:
            memo_ls[ind] = 3
        elif s1[ind-1] == s2[ind-1]:
            memo_ls[ind] = memo_ls[ind - 1] * 2 % (10**9+7)
        else:
            memo_ls[ind] = memo_ls[ind - 1]
        ind += 1
    else:
        if ind == 0:
           memo_ls[ind] = 6
        elif s1[ind-1] == s2[ind-1]:
            memo_ls[ind] = memo_ls[ind - 1] * 2 % (10 ** 9 + 7)
        else:
            memo_ls[ind] = memo_ls[ind - 1] * 3 % (10 ** 9 + 7)
        memo_ls[ind + 1] = memo_ls[ind]
        ind += 2
print(memo_ls[n-1])

Solution (Python):
MOD = 1000000007

N = int(input())
S1 = list(input())
S2 = list(input())

if S1[0] == S2[0]:
    ans = 3
else:
    ans = 6

for i in range(0,N-1):
    if S1[i] == S2[i]:
        ans *= 2
    elif S1[i] != S2[i] and S1[i+1] != S2[i+1] and S1[i] != S1[i+1]:
        ans *= 3
    ans %= MOD

print(ans)

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

import math

def main():
    N = int(input())
    S1 = input().strip()
    S2 = input().strip()

    ans = 1
    tate = False
    i = 0
    if S1[i] == S2[i]: 
        ans *= 3
        tate = True
        i += 1
    else: 
        ans *= 6
        tate = False
        i += 2

    mod = 1000000007
    while i <= N-1:
        if tate:
            tate = S1[i] == S2[i]
            if tate: 
                ans = ans * 2 % mod
                i += 1
            else: 
                ans = ans * 2 % mod
                i += 2
        else:
            tate = S1[i] == S2[i]
            if tate: 
                ans = ans * 1 % mod
                i += 1
            else: 
                ans = ans * 3 % mod
                i += 2
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s1 = list(input())
s2 = list(input())
inf = 10**9+7

l = []
flag = False
for i in range(n):
    if s1[i] == s2[i]:
        l.append(1)
    else:
        if flag:
            l.append(2)
            flag = False
        else:
            flag = True



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

for i in range(1,len(l)):
    if l[i-1] == 1 and l[i] == 1:
        ans *= 2
    elif l[i-1] == 1 and l[i] == 2:
        ans *= 2
    elif l[i-1] == 2 and l[i] == 1:
        ans *= 1
    else:
        ans *= 3
    ans %= inf

print(ans)

Solution (Python):
N = int(input())
A = input()
B = input()

def f(horizontal_flag):
    if horizontal_flag[0]:
        if horizontal_flag[1]:
            return 3
        else:
            return 1
    else:
        return 2

if N == 1:
    print(3)    
else:
    if A[0] == A[1]:
        counter = 6
        initial_num = 2
        horizontal_flag = [1,0]
    else:
        counter = 3
        initial_num = 1
        horizontal_flag = [0,0]

    for i in range(initial_num,N):
        if i == N-1:
            if horizontal_flag[1] == 2:
                horizontal_flag[1] = 1
                counter *= f(horizontal_flag)
            else:
                horizontal_flag[1] = 0
                counter *= f(horizontal_flag)
        elif A[i] == A[i+1]:
            horizontal_flag[1] = 2
        else:
            if horizontal_flag[1] == 2:
                horizontal_flag[1] = 1
                counter *= f(horizontal_flag)
            else:
                horizontal_flag[1] = 0
                counter *= f(horizontal_flag)
            horizontal_flag[0] = horizontal_flag[1]
    print(counter % 1000000007)

Solution (Python):
N = int(input())
S1 = list(input())
S2 = list(input())
n = 0
ans = 1
MOD = 10 ** 9 + 7
while n < N:
    if S1[n] == S2[n]:
        if n == 0:
            ans = 3
        elif n > 0:
            if S1[n - 1] == S2[n - 1]:
                ans *= 2
            else:
                ans *= 1
        n += 1
    elif S1[n] != S2[n]:
        if n == 0:
            ans = 6
        elif n > 0:
            if S1[n - 1] == S2[n - 1]:
                ans *= 2
            else:
                ans *= 3
        n += 2
    ans = ans % MOD
    
print(ans)

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


mod = 1000000007

pointa_s1 = 0
pointa_s2 = 0
if S1[pointa_s1] == S2[pointa_s2]:  
    ans = 3
    pointa_s1 += 1
    pointa_s2 += 1
else:  
    ans = 6
    pointa_s1 += 2
    pointa_s2 += 2

while N > pointa_s1:
    
    if S1[pointa_s1] == S2[pointa_s2]:  
        if S1[pointa_s1-1] == S2[pointa_s2-1]:  
            ans *= 2
            pointa_s1 += 1
            pointa_s2 += 1
        else:  
            ans *= 1
            pointa_s1 += 1
            pointa_s2 += 1
    else:  
        if S1[pointa_s1-1] == S2[pointa_s2-1]:  
            ans *= 2
            pointa_s1 += 2
            pointa_s2 += 2
        else:  
            ans *= 3
            pointa_s1 += 2
            pointa_s2 += 2

print(ans % mod)

Solution (Python):
import itertools
import math

N = int(input())
S1 = input()
S2 = input()
MOD = 1000000007
dir = 0 

if N == 1:
    ans = 3
    i = 1

elif S1[0] == S1[1]:
    dir = 0
    ans = 6
    i = 2
else:
    dir = 1
    ans = 3
    i = 1
p = [0,0,0,0]
while True:
    if i>=N:
        break


    if dir == 0:
        if i + 1 < N and S1[i] == S1[i + 1]: 

            dir = 0
            i += 2
            p[0] += 1
            ans *= 3
        else:

            i+=1  
            dir = 1
            ans *= 1


            p[1] += 1

    elif dir == 1:
        if i + 1 < N and  S1[i] == S1[i + 1]: 
            i += 2
            dir = 0

            ans *= 2


            p[2] +=1
        else: 
            i += 1
            dir = 1
            ans *= 2
            p[3] +=1
    
    ans %= MOD
print(ans)

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

ans = 1
status = 0
i = 0
while (i < N):
  if S[0][i] == S[1][i]:
    if status == 0:
      ans *= 3
    elif status == 1:
      ans *= 2
    status = 1
    i += 1
  else:
    if status == 0:
      ans *= 6
    elif status == 1:
      ans *= 2
    else:
      ans *= 3
    status = 2
    i += 2
  ans %= MOD
print(ans)

Solution (Python):
import sys,heapq,bisect

mod = 10**9+7

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

def GCD(a,b):
    while(a%b != 0):
        a,b = b,a%b
    return b

def LCM(a,b):
    return a*b//GCD(a,b)

def main():
    N = I()
    S1 = S()
    S2 = S()

    r = 1
    d_type = 0
    i = 0

    if S1[0] == S2[0]:
        r *= 3
        i += 1
        d_type = 0
    else:
        r *= 3 * 2
        i += 2
        d_type = 1

    while i < N:
        if d_type == 0 and S1[i] == S2[i]:
            r *= 2
            r %= mod
            d_type = 0
            i += 1
        elif d_type == 1 and S1[i] == S2[i]:
            d_type = 0
            i += 1
        elif d_type == 0 and S1[i] != S2[i]:
            r *= 2
            r %= mod
            d_type = 1
            i += 2
        else:
            r *= 3
            r %= mod
            d_type = 1
            i += 2

    return(r)

if __name__ == "__main__":
    print(main())

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

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


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


md=10**9+7
ans=1
for i in u:
  ans*=i
  ans%=md
print(ans)

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


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

if S1[0] != S2[0]:
    ans = 6
    i = 2
    prev = 0  
else:
    ans = 3
    i = 1
    prev = 1

while i <= N-1:
    if prev == 0 and S1[i] != S2[i]:
        ans *= 3
        i += 2
        prev = 0
    elif prev == 0 and S1[i] == S2[i]:
        ans *= 1
        i += 1
        prev = 1
    elif prev == 1 and S1[i] != S2[i]:
        ans *= 2
        i += 2
        prev = 0
    else:
        ans *= 2
        i += 1
        prev = 1
    ans %= MOD
print(ans)

Solution (Python):
N = int(input())
S1 = list(input())
S2 = list(input())
ans=1
prev=0
ue = ""
for i in range(N):
  if S1[i]==S2[i]:
    if prev == 0:
      ans*=3
    elif prev == 1:
      ans*=2
    else:
      ans*=1
    prev = 1
  else:
    if ue == S1[i]:
      continue
    else:
      if prev == 0:
        ans*=6
      elif prev == 1:
        ans*=2
      else:
        ans*=3
      ue=S1[i]
      prev=2
print(ans%1000000007)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() 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)]
mod = 1000000007


n = I()
U = S()
D = S()
ans = 3
if U[0] != D[0]:
    ans *= 2
for i in range(1, n):
    if U[i-1] == U[i] or (U[i] == D[i] and U[i-1] != D[i-1]):
        continue
    elif U[i-1] != D[i-1] and U[i] != D[i]:
        ans = ans * 3 % mod
    else:
        ans = ans * 2 % mod



print(ans)

Solution (Python):


N=int(input())
s=[[]*N for i in range(2)]
s[0]=input()
s[1]=input()

prev=0
ans=1
i=0
while i!=N:
    if s[0][i]==s[1][i]:
        if prev==1:
            ans=ans*2
        elif prev==-1:
            pass
        else:
            ans=ans*3
        prev=1
    else:
        if prev==1:
            ans=ans*2
        elif prev==-1:
            ans=ans*3
        else:
            ans=ans*6
        prev=-1
        i+=1
    i+=1
print(ans%(10**9+7))

Solution (Python):
"""
abb
acc  6

ab
ab   6

bbc
aac  3

bbaa
ccdd  2
"""

n = int(input())
u = input()
d = input()

bef = -1 

ans = 1
ind = 0
mod = 1000000007
while (True):
    if u[ind] == d[ind]:
        ind += 1
        if bef == -1:
            ans *= 3
        elif bef == 0:
            ans *= 2
            ans %= mod
        else:
            ans *= 1
            ans %= mod
        bef = 0

    else:
        ind += 2
        if bef == -1:
            ans *= 6
        elif bef == 0:
            ans *= 2
            ans %= mod
        else:
            ans *= 3
            ans %= mod
        bef = 1
    
    if ind > n-1:
        break
print(ans)

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

A = []
cur = 0
while cur < N:
    if S1[cur] == S2[cur]:
        A.append("X")
        cur += 1
    else:
        A.append("Y")
        cur += 2

ans = 3 if A[0] == "X" else 6
for i in range(1, len(A)):
    if A[i - 1] == "X":
        ans *= 2
    elif A[i] == "Y":
        ans *= 3
    ans %= 1000000007

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,k = LI()
    a = LI()
    d = defaultdict(lambda:0)
    for i in a:
        d[i] += 1
    d = list(d.values())
    d.sort()
    ans = 0
    for i in range(len(d)-k):
        ans += d[i]
    print(ans)
    return


def B():
    n,z,w = LI()
    a = LI()
    if n == 1:
        print(abs(a[0]-w))
        return
    ans = max(abs(a[-1]-w),abs(a[-2]-a[-1]))
    print(ans)
    return


def C():
    n = I()
    s1 = S()
    s2 = S()
    dp = [[[0]*3 for j in range(3)] for i in range(n+1)]
    if s1[0] == s2[0]:
        dp[1] = [[1 if i == j else 0 for j in range(3)] for i in range(3)]
    else:
        dp[1] = [[0 if i == j else 1 for j in range(3)] for i in range(3)]
    for i in range(1,n):
        ni = i+1
        if s1[i] == s2[i]:
            for j in range(3):
                for k in range(3):
                    if k == j:continue
                    for l in range(3):
                        if l == j:continue
                        dp[ni][j][j] += dp[i][k][l]
        else:
            if i and s1[i] == s1[i-1]:
                for j in range(3):
                    for k in range(3):
                        dp[ni][j][k] = dp[i][j][k]
            else:
                for j in range(3):
                    for k in range(3):
                        if k == j:continue
                        for l in range(3):
                            if l == j:continue
                            for m in range(3):
                                if m == k:continue
                                dp[ni][j][k] += dp[i][l][m]
    ans = 0
    for i in range(3):
        for j in range(3):
            ans += dp[n][i][j]
    print(ans%mod)
    return


def D():

    return


def E():

    return


if __name__ == "__main__":
    C()

Solution (Python):

def main():
    N = int(input())
    S1 = input().rstrip()
    S2 = input().rstrip()
    MOD = 10 ** 9 + 7
    a, b = S1[0], S2[0]
    ans = 3 if a == b else 6
    for i, j in zip(S1[1:], S2[1:]):
        if a != i and b != j:
            if a == b:
                ans *= 2
            else:
                ans *= 1 if i == j else 3
            ans %= MOD
        a, b = i, j
    print(ans)


if __name__ == "__main__":
    main()

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

n = int(input())
a = input()
b = input()
ans = 1
for i in range(n):
    if a[i] == b[i]:
        if i == 0:
            ans *= 3
        elif a[i-1] == b[i-1]:
            ans *= 2
    else:
        if i == 0:
            ans *= 6
        else:
            if a[i-1] == a[i]:
                continue
            elif a[i-1] == b[i-1]:
                ans *= 2
            else:
                ans *= 3
    ans = ans % mod
print(ans)

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

        else:
            if s1[i] == s1[i-1] and s2[i] == s2[i-1]:
                continue
            elif s1[i - 1] == s2[i - 1]:
                ans *= 2
            else:
                ans *= 3
        ans %= mod
else:
    ans = 6
    for i in range(2,n):
        if s1[i] == s2[i]:
            if s1[i-1] == s2[i-1]:
                ans *= 2

        else:
            if s1[i] == s1[i-1] and s2[i] == s2[i-1]:
                continue
            elif s1[i-1] == s2[i-1]:
                ans *= 2
            else:
                ans *= 3
        ans %= mod

print(ans)

Solution (Python):
MOD = int(1e9+7)
N = int(input())
S1 = input()
S2 = input()
now = 0
ans = 1
flag = False
for i in range(N):
    if flag:
        flag = False
        continue
    s11 = S1[i]
    s21 = S2[i]
    if s11 == s21:
        ans = (ans * (3 - now)) % MOD
        now = 1
    else:
        flag = True
        if now == 0:
            ans = (ans * 6) % MOD
        elif now == 1:
            ans = (ans * 2) % MOD
        else:
            ans = (ans * 3) % MOD
        now = 2
print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s1 = input()
s2 = input()
ans = 0
flg = 0
fact = [1]*53
for i in range(1,53):
    fact[i] = fact[i-1]*i

def comb(n,r):
    return fact[n] // fact[n-r] // fact[r]

if s1[0] == s2[0]:
    ans += 3
    flg = 0
    i = 1
else:
    ans += comb(3,2)*2
    ans %= mod
    flg = 1
    i = 2
while i < n:
    if flg == 0 and s1[i] == s2[i]:
         ans *= 2
         ans %= mod
         i += 1
    elif flg == 1 and s1[i] == s2[i]:
        ans *= 1
        flg = 0
        i += 1
    elif flg == 0 and s1[i] != s2[i]:
        ans *= 2
        ans %= mod
        flg = 1
        i += 2
    elif flg == 1 and s1[i] != s2[i]:
        ans *= 3
        ans %= mod
        i += 2
print(ans)

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

def main():
    MOD = 1000000007
    N = int(input())
    s = []
    s.append(list(input().strip()))
    s.append(list(input().strip()))

    
    i = 0
    if s[0][i] == s[1][i]:
        pre = 0
        ans = 3
        i += 1
    else:
        pre = 1
        ans = 6
        i += 2
    
    while i < N:
        
        if s[0][i] == s[1][i]:
            if pre == 0:
                ans *= 2
            else:
                ans *= 1
            i += 1
            pre = 0
        else:
            if pre == 0:
                ans *= 2
            else:
                ans *= 3
            i += 2
            pre = 1
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
mod = 10**9+7

if n == 1:
  print(3)
  exit()
  
ans = 6
for i in range(2,n):
  if s1[i] == s2[i]:
    if s1[i-1] == s2[i-1]:
      ans *= 2
      ans %= mod
  elif s1[i] != s2[i] and s1[i] != s1[i-1]:
    if s1[i-1] == s2[i-1]:
      ans *= 2
      ans %= mod
    else:
      ans *= 3
      ans %= mod

print(ans)