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):
MOD = 10**9 + 7


def main():
    N = int(input())
    S = [input() for _ in range(2)]
    dp = [0] * N
    if S[0][0] == S[1][0]:
        dp[0] = 3
    else:
        dp[0] = 3 * 2
    for i in range(1, N):
        if S[0][i] == S[0][i-1]:
            dp[i] = dp[i-1] % MOD
            continue
        l = 1 if S[0][i-1] == S[1][i-1] else 2
        r = 1 if S[0][i] == S[1][i] else 2
        if l == 1:
            dp[i] = dp[i-1] * 2 % MOD
        elif r == 2:
            dp[i] = dp[i-1] * 3 % MOD
        else:
            dp[i] = dp[i-1] % MOD
    print(dp[N-1])


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
d = defaultdict(int)
a = LI()
for i in a:
    d[i] += 1
d = list(d.items())
d.sort(key = lambda x:-x[0])
l = 0
k = 0
for i,j in d:
    if j >= 2:
        if l == 0:
            l = i
        else:
            k = i
        if j >= 4:
            k = i
    if k != 0:break
print(l*k)
"""


n = I()
s1 = S()
s2 = S()
ans = 0
i = 0
key = 1
d = defaultdict(int)
while i < n:
    if s1[i] == s2[i]:
        if not d[s1[i]]:
            d[s1[i]] = 1
            if i == 0:
                ans = 3
            else:
                if key:
                    ans *= 2
        key = 1
    else:
        if not d[s1[i]] and not d[s2[i]]:
            d[s1[i]] = 1
            d[s2[i]] = 1
            if i == 0:
                ans = 6
            else:
                if key:
                    ans *= 2
                else:
                    ans *= 3
        if not d[s1[i]]:
            d[s1[i]] = 1
            if not key:
                ans *= 2
        if not d[s2[i]]:
            d[s2[i]] = 1
            if not key:
                ans *= 2
        key = 0
        i += 1
    i += 1
    ans %= mod
print(ans)

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

p = 1
i = 0
prevm = 0
while i < len(s1):
  if s1[i] != s2[i]:
    if prevm == 0:
      p *= 6
    elif prevm == 1:
      p *= 2
    elif prevm == 2:
      p *= 3
    prevm = 2
    i += 1
  else:
    if prevm == 0:
      p *= 3
    elif prevm == 1:
      p *= 2
    prevm = 1
  i += 1
    
print(p % 1000000007)

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
cnt = 1
i = 0
while i <= n-1:
    if i == 0:
        if s1[i] == s2[i]:
            cnt *= 3
            s = 0
        else:
            cnt *= 6
            i += 1
            s = 1
    elif s1[i] == s2[i]:
        if s == 0:
            cnt *= 2
        else:
            cnt *= 1
        s = 0
    else:
        if s == 0:
            cnt *= 2
        else:
            cnt *= 3
        s = 1
        i += 1
    i += 1
print(cnt % (10**9+7))

Solution (Python):
n = int(input())
s1= input()
s2= input()
ans =3
if s1[0]!=s2[0]:
  ans = 6
  k = 2
  tate_flag = False
else:
  ans = 3
  k = 1
  tate_flag = True
  
flag =False
for i in range(k,n):
  if flag:
    flag = False
  elif s1[i]!=s2[i] and tate_flag:
    ans = ans * 2
    flag = True
    tate_flag = False
  elif s1[i]!=s2[i] and not tate_flag:
    ans = ans * 3
    flag = True
    tate_flag = False
  elif s1[i]==s2[i] and tate_flag:
    ans = ans *2
    tate_flag = True
  else:
    ans =ans*1
    tate_flag = True
  ans = ans % 1000000007
print(ans)

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
n=I()
s1=list(S())
s2=SL()
mod=pow(10,9)+7
s=[]
i=0
if n==1:
    ans=3
elif n==2:
    ans=6
else:
    while i<=n-2:
        if s1[i]==s1[i+1]:
            s.append(2)
            i+=2
        else:
            s.append(1)
            i+=1
    if s1[-1]!=s1[-2]:
        s.append(1)
    if s[0]==1:
        ans=3
    else:
        ans=6
    for i in range(1,len(s)):
        if s[i-1]==1:
            ans*=2
        else:
            if s[i]==2:
                ans*=3
        ans=ans%mod
print(ans)

Solution (Python):
x=0
N=int(input())
S=[input() for _ in range(2)]
mod=10**9+7

l=[]
while x<N:
    if S[0][x]==S[1][x]:
        l.append(1)
        
        x+=1
    else:
        l.append(0)
        
        x+=2

v=1
for i,j in enumerate(l):
    if not i:
        v=3 if j else 6
    else:
        if l[i-1]:
            v*=2
        elif not j:
            v*=3
    v%=mod

print(v)

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

p=0
prev=0
ans=3

if S1[p]==S2[p]:
    p+=1
    prev=1
else:
    p+=2
    prev=2
    ans*=2

while p<N:
    if S1[p]==S2[p]:
        p+=1
        if prev==1:
            ans*=2
        prev=1
    else:
        p+=2
        if prev==1:
            ans*=2
        else:
            ans*=3
        prev=2
    ans%=1000000007
print(ans)

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

Solution (Python):
a = int(input())
x=list(input())
y=list(input())
s = 1
i=0
if x[0] == y[0]:
    s*=3
    i+=1
else:
    s*=6
    i+=2
while i <a :
    if x[i-1] == y[i-1] and x[i]==y[i]:
        s*=2
    elif x[i-1] == y[i-1] and x[i]!=y[i]:
        s*=2
    elif x[i-1] != y[i-1] and x[i] !=y[i]:
        s*=3
    if not x[i] == y[i]:
        i+=1
    i+=1
print(s%1000000007)

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

i = 0
while i < n:
    if i == 0:
        if s1[i] == s2[i]:
            a = 3
            i += 1
            pre = 0
        else:
            a = 6
            i += 2
            pre = 1
    else:
        if pre == 0:
            a *= 2
            if s1[i] == s2[i]:
                i += 1
            else:
                pre = 1
                i += 2
        elif pre == 1:
            if s1[i] == s2[i]:
                pre = 0
                i += 1
            else:
                a *= 3
                i += 2

print(a%1000000007)

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
if s1[0] == s2[0]:
    preState = 0
    ans = 3
    index = 1
else:
    preState = 1
    ans = 6
    index = 2
while index < n:
    if s1[index] == s2[index]:
        if preState == 0:
            ans *= 2
        else:
            pass
        preState = 0
        index += 1

    else:
        if preState == 0:
            ans *= 2
        else:
            ans *= 3
        preState = 1
        index += 2
print(ans % 1000000007)

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

if S[0][0] == S[1][0]:
    last_kind = 0
    ans = 3
    i = 1
else:
    last_kind = 1
    ans = 6
    i = 2
while i < N:
    if last_kind == 0 and S[0][i] == S[1][i]:
        ans *= 2
        last_kind = 0
        i += 1
    elif last_kind == 1 and S[0][i] == S[1][i]:
        last_kind = 0
        i += 1
    elif last_kind == 0 and S[0][i] == S[0][i+1]:
        ans *= 2
        last_kind = 1
        i += 2
    elif last_kind == 1 and S[0][i] == S[0][i+1]:
        ans *= 3
        last_kind = 1
        i += 2
    ans %= M

print(ans)

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

if S[0][0] == S[1][0]:
    last_kind = 0
    ans = 3
    i = 1
else:
    last_kind = 1
    ans = 6
    i = 2
while i < N:
    if last_kind == 0 and S[0][i] == S[1][i]:
        ans *= 2
        last_kind = 0
        i += 1
    elif last_kind == 1 and S[0][i] == S[1][i]:
        last_kind = 0
        i += 1
    elif last_kind == 0 and S[0][i] == S[0][i+1]:
        ans *= 2
        last_kind = 1
        i += 2
    elif last_kind == 1 and S[0][i] == S[0][i+1]:
        ans *= 3
        last_kind = 1
        i += 2
    ans %= M

print(ans)

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

if S1[0] == S2[0]:
    result = 3
    skip   = False
    tate   = True
else:
    result = 6
    skip   = True
    tate   = False

for n in range(1, N):
    if skip == True:
        skip = False
        continue
    elif S1[n] == S2[n]:
        if tate == True:
            result *= 2
        else:
            tate = True
    else:
        if tate == True:
            result *= 2
        else:
            result *= 3
        skip    = True
        tate    = False
    if result  >= 1000000007:
        result %= 1000000007

print(result)

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

count = 0
i = 0
if s1[0] == s2[0]:
    i += 1
    count = 3
else:
    count = 6
    i += 2
while i < n:
    if s1[i - 1] == s2[i - 1]:
        if s1[i] == s2[i]:
            count *= 2
            i += 1
        else:
            count *= 2
            i += 2
    else:
        if s1[i] == s2[i]:
            i += 1
        else:
            count *= 3
            i += 2
print(count % (10 ** 9 + 7))

Solution (Python):


MOD = 1000000007

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

ptns = []
i = 0

while i < N:
    if S1[i] == S2[i]:
        ptns.append('X')
        i += 1
    else:
        ptns.append('Y')
        i += 2

if ptns[0] == 'X':
    ans = 3
elif ptns[0] == 'Y':
    ans = 6
for i in range(1, len(ptns)):
    
    if ptns[i-1] == 'X' and ptns[i] == 'X':
        ans *= 2
    elif ptns[i-1] == 'X' and ptns[i] == 'Y':
        ans *= 2
    elif ptns[i-1] == 'Y' and ptns[i] == 'X':
        ans *= 1
    elif ptns[i-1] == 'Y' and ptns[i] == 'Y':
        ans *= 3
    ans %= MOD
print(ans)

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

i = 0
prev = -1
ans = 1
while i < N:
    if s1[i] == s2[i]:
        if prev == 1:
            ans *= 1
        elif prev == 0:
            ans *= 2
        else:
            ans *= 3
        prev = 0
    else:
        if prev == 0:
            ans *= 2
        elif prev == 1:
            ans *= 3
        else:
            ans *= 6
        i += 1
        prev = 1
    i += 1

print(ans % mod)

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


S1 += '*'
P = []
i = 0
while i < N:
    if S1[i] == S1[i + 1]:
        P.append('横')
        i += 1
    else:
        P.append('縦')
    i += 1

ans = 0
if P[0] == '縦':
    ans = 3
    one_before = '縦'
elif P[0] == '横':
    ans = 6
    one_before = '横'

for p in P[1:]:
    if p == '縦' and one_before == '縦':
        ans = ans * 2 % mod
        one_before = p

    elif p == '縦' and one_before == '横':
        one_before = p

    elif p == '横' and one_before == '縦':
        ans = ans * 2 % mod
        one_before = p

    elif p == '横' and one_before == '横':
        ans = ans * 3 % mod
        one_before = p

print(ans)

Solution (Python):
Mod = 10**9+7
def f(s,t):
  if s[-1] == t[-1]:
    if len(s) == 1:
      return 3
    elif s[-2] == t[-2]:
      return 2*f(s[:-1],t[:-1])%Mod
    else:
      return 1*f(s[:-1],t[:-1])%Mod
  else:
    if len(s) == 2:
      return 6
    elif s[-3] == t[-3]:
      return 2*f(s[:-2],t[:-2])%Mod
    else:
      return 3*f(s[:-2],t[:-2])%Mod

n = int(input())
x = input()
y = input()
print(f(x,y))

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

MOD = 10 ** 9 + 7

ans = 1
i = 0
if s1[0] == s2[0]:
    ans *= 3
    i += 1
elif s1[0] == s1[1] and s2[0] == s2[1]:
    ans *= 3 * 2
    i += 2

t = (s1[0] == s2[0])  
while i < N:
    if t:
        ans *= 2
        ans %= MOD
    else:
        if i + 1 < N:
            if s1[i] == s1[i + 1] and s2[i] == s2[i + 1]:
                ans *= 3
                ans %= MOD
    t = (s1[i] == s2[i])
    i += 1 if t else 2

print(ans)

Solution (Python):

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

MOD = 10**9 + 7
ans = []
skip = False
pre_tate = False
for u,l in zip(S1,S2):
    if skip == True:
        skip = False
        continue

    if len(ans) == 0:
        if u == l:
            ans.append(3)
            pre_tate = True
        else:
            ans.append(6)
            skip = True
            pre_tate = False
    else:
        if u == l:
            if pre_tate:
                ans.append(2)
            else:
                ans.append(1)
            pre_tate = True
        else:
            if pre_tate:
                ans.append(2)
            else:
                ans.append(3)
            skip = True
            pre_tate = False

tmp = 1
for a in ans:
    tmp *= a

print(tmp%MOD)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
dp_v = 0
dp_h = 0
mod = 1000000007
is_first = True
while S1:
    if len(S1) > 1 and S1[0] == S1[1]:
        S1 = S1[2:]
        if is_first:
            dp_h = 6
            dp_v = 0
            is_first = False
        else:
            dp_h = dp_v*2+dp_h*3
            dp_v = 0
    else:
        S1 = S1[1:]
        if is_first:
            dp_v = 3
            dp_h = 0
            is_first = False
        else:
            dp_v = dp_v*2+dp_h
            dp_h = 0
    dp_v %= mod
    dp_h %= mod
print((dp_h+dp_v) % mod)

Solution (Python):
N=int(input())
d=list(input())
do=""
if N==1:
  print(3)
  exit()
if d[0]==d[1]:
  ans=6
  flag=0
  do+=d[0]*2+","
else:
  ans=3
  flag=1
  do+=d[0]+","
for i in range(1,N-1):
  if flag==1:
    if d[i]==d[i+1]:
      ans*=2
      flag=0
      do+=d[i]*2+","
    else:
      ans*=2
      flag=1
      do+=d[i]+","
  elif flag==2:
    if d[i]==d[i+1]:
      ans*=3
      flag=0
      do+=d[i]*2+","
    else:
      ans*=1
      flag=1
      do+=d[i]+","
  elif flag==0:
    flag=2
if flag==1:
  ans*=2
  do+=d[N-1]
elif flag==2:
  ans*=1
  do+=d[N-1]
  
print(ans%(10**9+7))

Solution (Python):
N = int(input())
MOD = 10**9+7
u,d = input(),input()
ans,i = 0,0
if u[0]==d[0]:
    ans = 3
    i = 1
else:
    ans = 6
    i = 2
while i<N:
    if u[i-1]==d[i-1]:
        ans *= 2
        if u[i]==d[i]:
            i += 1
        else:
            i += 2
    else:
        if u[i]==d[i]:
            ans *= 1
            i += 1
        else:
            ans *= 3
            i += 2
print(ans%MOD)

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

Solution (Python):
ans=1
n=int(input())
s=input()
t=input()
m=False
if s[0]==t[0]:
    ans*=3
    flag=True
else:
    ans*=6
    flag=False
    m=True
for i in range(1,n):
    if m==True:
        m=False
        continue
    if flag==True and s[i]==t[i]:
        ans*=2
        continue
    if flag==True and s[i]!=t[i]:
        ans*=2
        m=True
        flag=False
        continue
    if flag==False and s[i]==t[i]:
        flag=True
        continue
    if flag==False and s[i]!=t[i]:
        ans*=3
        m=True
        continue
print(ans%(10**9+7))

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

Solution (Python):
n = int(input())
s = [list(input()) for _ in range(2)]
MOD = 10 ** 9 + 7

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

ans = 0
p = 0
b = 0
if s[0][0] == s[1][0]:
    ans = 3
    p = 1
    b = 1
else:
    ans = 6
    p = 2
    b = 2

while p < n:
    if s[0][p] == s[1][p]:
        if b == 1:
            ans *= 2
            ans %= MOD
        else:
            b = 1
        p += 1
    else:
        if b == 1:
            ans *= 2
            ans %= MOD
            b = 2
        else:
            ans *= 3
            ans %= MOD
        p += 2

print(ans)

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

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


if X[0] == "Y":
    ans = 6
    before = "Y"
elif X[0] == "T":
    ans = 3
    before = "T"

for x in X[1:]:
    if before == "Y" and x == "Y":
        ans = ans * 3 % mod
        before = "Y"

    elif before == "Y" and x == "T":
        ans = ans * 1 % mod
        before = "T"

    elif before == "T" and x == "Y":
        ans = ans * 2 % mod
        before = "Y"

    elif before == "T" and x == "T":
        ans = ans * 2 % mod
        before = "T"

print(ans % mod)

Solution (Python):
n=int(input())
a=input()
b=input()
mod=10**9+7
x=[]
j=True
for i in range(n):
    if a[i]!=b[i]:
        if j:
            x.append(2)
            j=False
        else:
            j=True
    else:
        x.append(1)
res=1
j=0
for t in x:
    if t==1:
        if j==0:
            res*=3
        elif j==1:
            res*=2
        else:
            res*=1
        j=1
    else:
        if j==0:
            res*=6
        elif j==1:
            res*=2
        else:
            res*=3
        j=2
print(res%mod)

Solution (Python):
N = int(input())
s1 = input()
s2 = input()
mod = 1000000007
ans = 1
tate = True
if s1[0]==s2[0]:
    ans *= 3
    s1 = s1[1:]
else:
    ans *= 6
    s1 = s1[2:]
    tate = False
while len(s1) > 1:
    if s1[0] == s1[1]:
        s1 = s1[2:]
        if tate:
            ans *= 2
        else:
            ans *= 3
        ans %= mod
        tate = False
    else:
        if tate:
            ans *= 2
            ans %= mod
        s1 = s1[1:]
        tate = True
if tate and len(s1) == 1:
    ans *= 2
    ans %= mod
print(ans)

Solution (Python):
N = int(input())
S = []
for i in range(2):
    S.append(input())
mod = 7 + 10**9

if S[0][0] == S[1][0]: 
    ans, pre = 3, "v"
    i = 1
else: 
    ans, pre = 6, "w"
    i = 2

while i < N:
    if S[0][i] == S[1][i]: 
        if pre == "v": 
            ans *= 2
            ans %= mod
        else: 
            pre = "v"
        i += 1
    else: 
        if pre == "v": 
            ans *= 2
            ans %= mod
            pre = "w"
        else: 
            ans *= 3
            ans %= mod
        i += 2

print(ans)

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

tmp=''
arr=[]
for x in input()+'0':
    if tmp =='':
        tmp=x
        continue
    if tmp == x:
        tmp=''
        arr.append(2)
    else:
        tmp=x
        arr.append(1)

tmp=arr.pop(0)
ans=tmp*3
for x in arr:
    if tmp == 1:
        ans*=2
    else:
        if x==2:
            ans*=3
    tmp=x
    ans%=1000000007
print(ans)

Solution (Python):
 
"""
Created on Sun Sep 30 11:46:57 2018
ABC071D
@author: maezawa
"""

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

comb = 1
adj = 0
i = 0
while i < n:
    if i < n-1 and s1[i] == s1[i+1]:
        if adj == 2:
            comb *= 3
        else:
            comb *= 3 - adj
            comb *= 3 - adj -1
        i += 2
        adj = 2
    else:
        comb *= 3 - adj
        i += 1
        adj = 1

print(comb%mod)

Solution (Python):
N = int(input())
S = input()+"1"
T = input()+"1"
U = ""

k = 0
while k < N:
    if S[k] == S[k+1]:
        U = U + "Y"
        k += 2
    else:
        U = U + "T"
        k += 1

if U[0] == "Y":
    ans = 6
else:
    ans = 3

mod = 1000000007
U = "1" + U
for k in range(2,len(U)):
    if U[k] == U[k-1] == "T":
        ans *= 2
        ans %= mod
    elif U[k-1] == "Y" and U[k] == "T":
        ans *= 1
        ans %= mod
    elif U[k-1] == "T" and U[k] == "Y":
        ans *= 2
        ans %= mod
    elif U[k-1] == "Y" and U[k] == "Y":
        ans *= 3
        ans %= mod

print(ans)

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

mod = 10**9 + 7



dp = [[0 for j in range(2)] for i in range(n+1)]

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

print((dp[n-1][0] % mod + dp[n-1][1] % mod) % mod)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

MOD = 10**9+7


n = ni()
s1 = lc()
s2 = lc()

xy = []

cnt = 0
while cnt < n:
    if s1[cnt] == s2[cnt]:
        xy.append("x")
        cnt += 1
    else:
        xy.append("y")
        cnt += 2
        
ans = 0

if xy[0] == "x":
    ans = 3
else:
    ans = 6
   
    
for pr,nx in zip(xy[:-1], xy[1:]):
    if pr == "x" and nx == "x":
        ans = (ans * 2) % MOD
        
    elif pr == "x" and nx == "y":
        ans = (ans * 2) % MOD
        
    elif pr == "y" and nx == "y":
        ans = (ans * 3) % 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):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    S = [input(), input()]

    if S[0][0] == S[1][0]:
        ans = 3
        i = 1
        pre = 0
    else:
        ans = 6
        i = 2
        pre = 1

    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 %= 1000000007
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
mod = 10 ** 9 + 7
n = int(input())
s1 = input()
s2 = input()
pre = 0
i = 0
while i < len(s1):
    if pre == 0:
        if s1[i] == s2[i]:
            num = 3
            i += 1
            pre = 1
        else:
            num = 6
            i += 2
            pre = 2
    elif pre == 1:
        if s1[i] == s2[i]:
            num *= 2
            num %= mod
            i += 1
            pre = 1
        else:
            num *= 2
            num %= mod
            i += 2
            pre = 2
    else:
        if s1[i] == s2[i]:
            i += 1
            pre = 1
        else:
            num *= 3
            num %= mod
            i += 2
            pre = 2

print(num)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
p = 10 ** 9 + 7
dp = [0] * 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]
  elif S1[i - 1] == S2[i - 1]:
    dp[i] = dp[i - 1] * 2 % p
  elif S1[i] == S2[i]:
    dp[i] = dp[i - 1]
  else:
    dp[i] = dp[i - 1] * 3 % p
print(dp[-1])

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
if S1[0] == S2[0]:
    count = 3
    start_idx = 1
    prev = 'v'
else:
    count = 6
    start_idx = 2
    prev = 'h'

skip = False

for i in range(start_idx, len(S1)):
    if skip:
        skip = False
        continue
    if S1[i] == S2[i]:  
        if prev == 'v':
            count *= 2
            prev = 'v'
        else:
            count *= 1
        prev = 'v'
    else:               
        if prev == 'v':
            count *= 2
        else:
            count *= 3
        prev = 'h'
        skip = True
print(count % (10**9 + 7))

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

mod = 10 ** 9 + 7

i, cnt = 0, 0
prev = ''
if S1[i] == S2[i]:
    cnt += 3
    prev = '|'
    i += 1
else:
    cnt += 6
    prev = '='
    i += 2

while i < N:
    if S1[i] == S2[i]:
        currnet = '|'
        i += 1
    else:
        currnet = '='
        i += 2
    if prev == '|':
        cnt *= 2        
    elif prev == '=' and currnet == '=':
        cnt *= 3
    cnt %= mod
    prev = currnet
print(cnt % mod)

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

i = 0
ans = 1
pre_state = None
while i < n:
    if s1[i] == s2[i]:
        if pre_state == 'same':
            ans = (ans*2)%MOD
        elif pre_state == 'diff':
            pass
        else:
            ans = 3
        pre_state = 'same'
        i += 1
    elif s1[i] != s2[i]:
        if pre_state == 'same':
            ans = (ans*2)%MOD
        elif pre_state == 'diff':
            ans = (ans*3)%MOD
        else:
            ans = 6
        pre_state = 'diff'
        i += 2

print(ans)

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

v=3
for i in range(1,n):
  if s1[i-1]==s2[i-1] or i==1:
    v*=2
  elif s1[i-1]!=s1[i] and s1[i]!=s2[i]:
    v*=3

print(v%1000000007)

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

v=3
for i in range(1,n):
  if s1[i-1]==s2[i-1]:
    v*=2
  elif s1[i-1]!=s1[i] and s1[i]!=s2[i]:
    v*=3
  elif i==1:
    v*=2

print(v%1000000007)

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

S = input()
T = input()

MODN = 1000000007


pat = []
i = 0
while i < N:
  if S[i] == T[i]:
    pat.append('t')
    i += 1
  else:
    pat.append('y')
    i += 2



cnt = 3 if pat[0] == 't' else 6

for i in range(1,len(pat)):
  if (pat[i-1], pat[i]) == ('t', 't'):
    cnt = cnt * 2 % MODN
  elif (pat[i-1], pat[i]) == ('t', 'y'):
    cnt = cnt * 2 % MODN
  elif (pat[i-1], pat[i]) == ('y', 't'):
    cnt = cnt
  elif (pat[i-1], pat[i]) == ('y', 'y'):
    cnt = cnt * 3 % MODN
  else:
    print("Error") 

print(cnt)

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

S = input()
T = input()

MODN = 1000000007


pat = []
i = 0
while i < N:
  if S[i] == T[i]:
    pat.append('t')
    i += 1
  else:
    pat.append('y')
    i += 2



cnt = 3 if pat[0] == 't' else 6

for i in range(1,len(pat)):
  if (pat[i-1], pat[i]) == ('t', 't'):
    cnt = cnt * 2 % MODN
  elif (pat[i-1], pat[i]) == ('t', 'y'):
    cnt = cnt * 2 % MODN
  elif (pat[i-1], pat[i]) == ('y', 't'):
    cnt = cnt
  elif (pat[i-1], pat[i]) == ('y', 'y'):
    cnt = cnt * 3 % MODN
  else:
    print("Error") 

print(cnt)

Solution (Python):
N=int(input())
S1=input()
S2=input()
l=0
ans=1
flag='a'
if S1[0]==S2[0]:
    l+=1
    ans*=3
    flag='t'
else:
    l+=2
    ans*=6
    flag='y'

for i in range(l,N):
    
    if flag=='t':
        if S1[l]==S2[l]:
            l+=1
            ans*=2
            ans=ans%1000000007
            if l>=N:
                break
        else:
            l+=2
            ans*=2
            ans=ans%1000000007
            flag='y'
            if l>=N:
                break
    else:
        if S1[l]==S2[l]:
            l+=1
            flag='t'
            if l>=N:
                break
        else:
            l+=2
            ans*=3
            ans=ans%1000000007
            if l>=N:
                break

print(ans%1000000007)

Solution (Python):
n = int(input())
s = input()
s2 = input()
i = 0
flag = -1
ans = 1
mod = 1000000007
while i<n:
  if s[i] == s2[i]:
    if flag == -1:
      ans *= 3
      flag = 0
    elif flag == 0:
      ans *= 2
      flag=0
    else:
      flag=0
    i+=1
  else:
    if flag == -1:
      ans *= 6
      flag = 1
    elif flag == 0:
      ans *= 2
      flag = 1
    else:
      ans *= 3
      flag = 1
    i += 2
  ans %= mod
print(ans)