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

Solution (Python):
N = int(input())
S = [input()+".", input()+","]
mod = 10**9+7

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

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

while i < N:
    if S[0][i] == S[1][i]:
        if S[0][i-1] == S[1][i-1]:
            ans *= 2
        else:
            pass
        ans %= mod
        i += 1
    
    else:
        if S[0][i-1] == S[1][i-1]:
            ans *= 2
        else:
            ans *= 3
        ans %= mod
        i += 2

print(ans)

Solution (Python):
import sys



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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    L1 = [None] + list(input()) + [None]
    L2 = [None] + list(input()) + [None]
    seq = []
    if L1[1] == L2[1]:  
        L1[1] = L2[1] = "
        seq.append("X")
    elif L1[1] == L1[2]:  
        L1[1] = L1[2] = L2[1] = L2[2] = "
        seq.append("Y")

    for i in range(1, n + 1):
        if L1[i] == "
            continue
        else:
            if L1[i] == L2[i]:
                seq.append("X")
                L1[i] = "
            elif L1[i] == L1[i + 1]:
                seq.append("Y")
                L1[i] = L1[i + 1] = "
    if seq[0] == "X":
        ans = 3
    elif seq[0] == "Y":
        ans = 6

    for i in range(1, len(seq)):
        if seq[i - 1] == "X":
            if seq[i] == "X":
                ans *= 2
            elif seq[i] == "Y":
                ans *= 2
        elif seq[i - 1] == "Y":
            if seq[i] == "X":
                ans *= 1
            elif seq[i] == "Y":
                ans *= 3
        ans %= 1000000007
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
N,S,T=open(0)
ans=3
i=1
if S[0]!=T[0]:
    ans*=2
    i*=2
while i<int(N):
    if S[i-1]==T[i-1]:
        ans*=2
    elif S[i]!=T[i]:
        ans*=3
    i+=1+(S[i]!=T[i])
print(ans%(10**9+7))

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N=intput()
S1=input()
S2=input()
i=0
ans=1

tmp=0
same=[3,2,1]
diff=[6,2,3]
while i<N:
    if S1[i]==S2[i]:
        ans*=same[tmp]
        tmp=1
        i+=1
    else:
        ans*=diff[tmp]
        tmp=2
        i+=2
    ans%=MOD
print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7


def get_pattern(A, B, pos, pre):
    if pre == 0:
        if A[pos] == B[pos]:
            return 3, pos+1, 1
        elif A[pos] == A[pos+1]:
            return 6, pos+2, 2
    if pre == 1:
        if A[pos] == B[pos]:
            return 2, pos+1, 1
        elif A[pos] == A[pos+1]:
            return 2, pos+2, 2
    if pre == 2:
        if A[pos] == B[pos]:
            return 1, pos+1, 1
        elif A[pos] == A[pos+1]:
            return 3, pos+2, 2

def run():
    N = int(input())
    S1 = input()
    S2 = input()
    pos = 0
    pre = 0
    ans = 1
    while pos < N:
        val, pos, pre = get_pattern(S1, S2, pos, pre)
        
        ans *= val
        ans %= mod

    print(ans)

if __name__ == "__main__":
    run()

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

if S1[0] == S2[0]:
  ans = 3
  cnt = 1
  tmp = 0
else:
  ans = 6
  cnt = 2
  tmp = 1
  
while cnt < N:
  if tmp == 0:
    if S1[cnt] == S2[cnt]:
      ans *= 2
      cnt += 1
    else:
      ans *= 2
      cnt += 2
      tmp = 1
  else:
    if S1[cnt] == S2[cnt]:
      cnt += 1
      tmp = 0
    else:
      ans *= 3
      cnt += 2
print(ans%1000000007)

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

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
ans = 1
i = 1
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]:
        if s1[i] == s2[i]:
            ans = (ans * 2) % mod
            i += 1
            continue
        else:
            ans = (ans * 2) % mod
            i += 2
            continue
    else:
        if s1[i] == s2[i]:
            ans = (ans * 1) % mod
            i += 1
            continue
        else:
            ans = (ans * 3) % mod
            i += 2
            continue
print(ans)

Solution (Python):
from collections import Counter
n = int(input())
S = input()
Do = Counter(S)
Ans = 0
i = 0
if Do[S[0]] == 1:
    Ans = 3
    i += 1
    sig = 1
else:
    Ans = 6
    i += 2
    sig = 2
while not i >= n:
    if Do[S[i]] == 1:
        if sig == 1:
            Ans *= 2
        else:
            Ans *= 1
        sig = 1
        i +=1
    else:
        if sig == 1:
            Ans *=2
        else:
            Ans *=3
        sig = 2
        i += 2
    Ans = Ans%(10**9+7)
print(Ans)

Solution (Python):
N=int(input())
l=""
mod=10**9+7
Sa=list(input())
Sb=list(input())
for i in range(N):
   if Sa[i]==Sb[i]:
      l+="X"
   else:
      l+="Y"
l=l.replace("YY","Y")
ans=6 if l[0]=="Y" else 3
for i in range(1,len(l)):
   if l[i]=="Y" and l[i-1]=="Y":
      ans*=3
   if l[i]=="X" and l[i-1]=="X":
      ans*=2
   if l[i]=="Y" and l[i-1]=="X":
      ans*=2
   ans=ans%mod
print(ans)

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

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

while i < N:
  pre_s1, pre_s2 = S1[i-1], S2[i-1]
  s1, s2 = S1[i], S2[i]
  if pre_s1 == pre_s2:
    ans *= 2
    ans %= MOD
    if s1 == s2:
      i += 1
    else:
      i += 2
  else:
    if s1 == s2:
      i += 1
    else:
      ans *= 3
      ans %= MOD
      i += 2

print(ans)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
ans = 1
MOD = 10**9+7
i = 0
flag = True

while i<N:
    if S1[i]==S2[i]:
        if i==0:
            ans *= 3
        else:
            if flag:
                ans *= 2
        
        i += 1
        flag = True
    else:
        if i==0:
            ans *= 6
        else:
            if flag:
                ans *= 2
            else:
                ans *= 3
        
        i += 2
        flag = False
    
    ans %= MOD

print(ans)

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

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

Mod=10**9+7
S=input()
T=input()

if S[0]==T[0]:
    K,I=3,1
    Mode=True
else:
    K,I=6,2
    Mode=False



while I<N:
    if S[I]==T[I]:
        if Mode:
            K*=2
        else:
            K*=1
        Mode=True
        I+=1
    else:
        if Mode:
            K*=2
        else:
            K*=3
        Mode=False
        I+=2
    K%=Mod
print(K)

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

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
if s1[0] == s2[0]:
    a = 3
    l = 0
    v = True
else:
    a = 6
    l = 1
    v = False
mod = 10**9+7
def mult_mod(x,y):
    return (x*y) % mod
while l+1 < n:
    if v:
        if s1[l+1] == s2[l+1]:
            l += 1
            a = mult_mod(a,2)
        else:
            l += 2
            a = mult_mod(a,2)
            v = False
    else:
        if s1[l+1] == s2[l+1]:
            l += 1
            v = True
        else:
            l += 2
            a = mult_mod(a,3)

print(a%mod)

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

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

mod = 10**9+7
yoko = True
if s1[0]==s2[0]:
    ans = 3
    cur = 1
    yoko = False
else:
    ans = 6
    cur = 2

while cur<n:
    if s1[cur]==s2[cur]:
        ans *= 1 if yoko else 2
        ans %= mod
        cur += 1
        yoko = False
    else:
        ans *= 3 if yoko else 2
        ans %= mod
        cur += 2
        yoko = True

print(ans)

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

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

if S1[0] == S1[1]:
    dp = 6
    start = 2
    state = 0
else:
    dp = 3
    start = 1
    state = 1

i = start
while i<L-1:
    if S1[i] == S1[i+1]:
        if state == 0:
            dp *= 3
            dp %= MOD
        else:
            dp *= 2
            dp %= MOD
        state = 0
        i += 2
    else:
        if state == 1:
            dp *= 2
            dp %= MOD
        state = 1
        i += 1
if state == 1:
    dp *= 2
    dp %= MOD
print(dp)

Solution (Python):
N = int(input())
grid = [input(),input()]
MOD = 10**9 + 7

cnt = 3 if grid[0][0] == grid[1][0] else 6

for i in range(1,N):
    a,b = grid[0][i-1],grid[1][i-1]
    c,d = grid[0][i],grid[1][i]

    if a == b:
        cnt *= 2
    elif c != d and a != c:
        cnt *= 3
    cnt %= MOD

print(cnt)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    l = []
    res = 1
    while res < N:
        if S1[res - 1] == S1[res]:
            l.append(2)
            res += 2
        else:
            l.append(1)
            res += 1
    if res == N:
        l.append(1)

    n = len(l)
    if l[0] == 1:
        ans = 3
    else:
        ans = 6

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

mod = 10 **9 + 7
def main():
    n = ii()
    s = []
    s.append(input())
    s.append(input())
    if s[0][0] == s[1][0]:
        ans = 3
    else:
        ans = 6

    for i in range(1,n):
        if s[0][i-1] == s[1][i-1]:
            ans  *= 2
            ans %= mod
        else:
            if s[0][i] != s[0][i-1] and s[1][i] != s[1][i-1] and s[0][i] != s[1][i]:
                ans *= 3
                ans %= mod
    print(ans)
            

            





if __name__ == '__main__':
    main()

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

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

for i in range(1, N):
    if S1[i] == S1[i-1]:
        continue
    if S1[i] == S2[i]:
        if t == 1:
            ans *= 2
        t = 1
    else:
        if t == 1:
            ans *= 2
        else:
            ans *= 3
        t = 2
    ans %= 10 ** 9 + 7

print(ans)

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

m1=""
m=10**9+7
S1+="."
for i in range(len(S1)-1):
    if S1[i]==S1[i+1]:
        m1+='y'
    else:
        m1+='t'
m1 = m1.replace('yt','y')
score = [1]*len(m1)
for i in range(1,len(m1)):
    if m1[i-1]=='t' and m1[i]=='t':
        score[i]=2
    elif m1[i-1]=='y' and m1[i]=='t':
        score[i]=1
    elif m1[i-1]=='t' and m1[i]=='y':
        score[i]=2
    elif m1[i-1]=='y' and m1[i]=='y':
        score[i] = 3
if m1[0]=='y':
    score[0]=6
else:
    score[0]=3

ans = 1
for i in range(len(m1)):
    ans =(ans*score[i])%m
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = [SS() for _ in range(2)]

    
    t = []
    i = 0
    if N == 1:
        t.append('v')
    else:
        while i + 1 < N:
            if S[0][i] == S[0][i+1]:
                t.append('h')
                i += 2
            else:
                t.append('v')
                i += 1
        if S[0][-2] != S[0][-1]:
            t.append('v')
    

    ans = 1
    if t[0] == 'h':
        ans *= 6
    else:
        ans *= 3
    ans %= MOD
    for i in range(len(t) - 1):
        if t[i] == 'h':
            if t[i+1] == 'h':
                ans *= 3
            else:
                ans *= 1
        else:
            if t[i+1] == 'h':
                ans *= 2
            else:
                ans *= 2
        ans %= MOD
    
    print(ans)
                
if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
s = input() + "@"
t = input() + "@"
mod = 10 ** 9 + 7



b = []
for i in range(n):
    if s[i] == s[i + 1]:
        continue
    b.append(s[i] == t[i])


if b[0]:
    ans = 3
else:
    ans = 6

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

print(ans % mod)

Solution (Python):
n = int(input())
s = input() + "@"
t = input() + "@"
mod = 10 ** 9 + 7



b = []
for i in range(n):
    if s[i] == s[i + 1]:
        continue
    b.append(s[i] == t[i])


if b[0]:
    ans = 3
else:
    ans = 6

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

print(ans)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
s1 = input()
s2 = input()

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

Solution (Python):
mod = 1000000007
n = int(input())
s = input()
s2 = input()
a = [] if n > 1 else [1]
for i in range(n-1):
  if i != 0 and s[i-1] == s[i]:
    continue
  if s[i] == s[i+1]:
    a.append(2)
    if i == n-3:
      a.append(1)
  else:
    a.append(1)
    if i == n-2:
      a.append(1)
ans = 3 if a[0] == 1 else 6
for i in range(len(a)-1):
  b,c = a[i:i+2]
  if b == 1:
    ans = (ans * 2) % mod
  else:
    if c == 2:
      ans = (ans * 3) % mod
print(ans)

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

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

l = []
res = 1
while res < N:
    if S1[res-1] == S1[res]:
        l.append(2)
        res += 2
    else:
        l.append(1)
        res += 1
if res == N:
    l.append(1)

n = len(l)
if l[0] == 1:
    ans = 3
else:
    ans = 6

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

print(ans)

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    s1 = input()
    s2 = input()
    P = []
    modulo = 10**9+7
    H, V = 0, 1
    for i in range(N):
        if i > 0 and s2[i] == s2[i-1]:
            P[-1] = H
        else:
            P.append(V)
    dp = []
    if P[0] == H:
        dp.append(6)
    else:
        dp.append(3)
    """
    A B     |C
    B A|C    A

    dp[i] = 3*dp[i-1] if P[i]=H&P[i-1]=H
            2*dp[i-1]    P[i]=H&P[i-1]=V
            2*dp[i-1]    P[i]=V&P[i-1]=V
            1*dp[i-1]    P[i]=V&P[i-1]=V
    """
    for i in range(1, len(P)):
        if P[i] == H and P[i-1] == H:
            dp.append(3*dp[i-1])
        elif P[i] == H and P[i-1] == V:
            dp.append(2*dp[i-1])
        elif P[i] == V and P[i-1] == V:
            dp.append(2*dp[i-1])
        else:
            dp.append(dp[i-1])
        dp[-1] %= modulo
    return dp[-1]


if __name__ == '__main__':
    print(solve())

Solution (Python):
n=int(input())
a=input()
b=input()
if a[0]==b[0]:
  c=3
  i=1
  d=0
else:
  c=6
  i=2
  d=1

while i<n:
  if a[i]==b[i]:
    if d==0:
      c=(c*2)%(10**9+7)
    else:
      d=0
  else:
    i+=1
    if d==0:
      c=(c*2)%(10**9+7)
      d=1
    else:
      c=(c*3)%(10**9+7)
  i+=1
print(c)

Solution (Python):
from itertools import groupby

N = int(input())
s = input()
S = input()
mod = 10 ** 9 + 7

s = [len(list(j)) for i, j in groupby(s)]

ans = 3 * s[0]

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

print(ans)

Solution (Python):


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

num  = 0

itr = zip(S[0], S[1])
c1, c2 = itr.__next__()

if c1 == c2:
    prev = 1 
    num = 3
else:
    prev = 2 
    num = 6
    itr.__next__()

for c1, c2 in itr:
    if c1 == c2:
        
        if prev == 1:
            num *= 2
            num %= 1000000007
        prev = 1 
    else:
        
        if prev == 1:
            num *= 2
        else:
            num *= 3
        num %= 1000000007
        itr.__next__()
        prev = 2

print(num)

Solution (Python):

from collections import defaultdict
n = int(input())
s1 = input()
s2 = input()
ans = 0
mod = 10 ** 9 + 7

if s1[0] == s2[0]:
    i = 1
    ans += 3
    flag = False
else:
    i = 2
    ans += 6
    flag = True
while i < n:
    if flag:
        if s1[i] == s2[i]:
            flag = False
        else:
            ans *= 3 % mod
            i += 1
    else:
        ans *= 2 % mod
        if s1[i] != s2[i]:
            flag = True
            i += 1
    i += 1
print(ans % mod)

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

if s1[0]==s2[0]:
    i=1
    ans+=3
    dual=False
else:
    i=2
    ans+=6
    dual=True
while i<N:
    if dual:
        if s1[i]==s2[i]:
            dual=False
        else:
            ans*=3
            ans%=mod
            i+=1
    else:
        ans*=2
        ans%=mod
        if s1[i]!=s2[i]:
            dual=True
            i+=1
    i+=1
print(ans%mod)

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

ans = 1
if(S1[0] == S2[0]):
    ans *= 3
    ans %= mod
    
    idx = 1
else:
    ans *= 6
    ans %= mod
    idx = 2

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

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

Solution (Python):
n = int(input())
S = [list(input()) for _ in range(2)]
mod = 1000000007
if S[0][0]==S[1][0]:
    ans = 3
    i = 1
    typ = '2x1'
else:
    ans = 6
    i = 2
    typ = '2x2'
while i<n:
    if S[0][i]==S[1][i]:
        if typ=='2x1':
            ans *= 2
        typ = '2x1'
        i += 1
    else:
        if typ=='2x1':
            ans *= 2
        else:
            ans *= 3
        typ = '2x2'
        i += 2
    ans %= mod
print(ans)

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

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

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

ans = 3 if S_1[0] == S_2[0] else 6

for i in range(1, N):
    if S_1[i-1] == S_1[i]:
        continue
    if S_1[i-1] == S_2[i-1]:
        ans = ans * 2 % MOD
    elif S_1[i] != S_2[i]:
        ans = ans * 3 % MOD
print(ans)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,readline().split())
s = input()
t = input()

MOD = 10**9+7
v = 2 
ans = 1
i = 0
while i < n:
    if s[i]==t[i]:
        i += 1
        if v==0:
            ans *= 2
        if v==2:
            ans *= 3
        v = 0
        ans %= MOD
    else:
        i += 2
        if v==0:
            ans *= 2
        if v==1:
            ans *= 3
        if v==2:
            ans *= 6
        v = 1
        ans %= MOD

print(ans%MOD)

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

s = list(zip(s1, s2))
ss = []

skip = 0
for i in s:
    if skip:
        skip=0
        continue

    if i[0]!=i[1]:
        skip = 1
    ss.append(i)



mod = 10**9+7
ans = 1
if ss[0][0]==ss[0][1]:
    f = 1
    ans *= 3
else:
    f = 0
    ans *= 6


for i in range(1, len(ss)):
    if ss[i][0]==ss[i][1]:
        nf = 1
    else:
        nf = 0

    if f:
        ans *= 2
    else:
        if not nf:
            ans *= 3
    ans %= mod
    f = nf
print(ans)

Solution (Python):
n = int(input())
s = input()
t = input()
prev = -1
i = 0
ans = 1
mod = pow(10,9)+7
while i != n:
    if s[i] == t[i]:
        if prev == -1:
            ans *= 3
        elif prev == 0:
            ans *= 2
        prev = 0
        i += 1
    else:
        if prev == -1:
            ans *= 6
        elif prev == 0:
            ans *= 2
        else:
            ans *= 3
        prev = 1
        i += 2
    ans %= mod
print(ans)

Solution (Python):
import sys

N = int(sys.stdin.readline())
S = ["", ""]
S[0] = sys.stdin.readline().strip()
S[1] = sys.stdin.readline().strip()

mod = 10**9 + 7

pre = [S[0][0], S[1][0]]
ans = 3
if S[0][0] != S[1][0]:
    ans *= 2


for i in range(1, N):
    
    if pre[0] == S[0][i] and pre[1] == S[1][i]:
        continue

    if pre[0] == pre[1]:
        ans *= 2
        ans %= mod
        
        
        
        
        
        
        
    else:
        
        if S[0][i] == S[1][i]:
            ans *= 1
        else:
            ans *= 3
            ans %= mod

    

    pre[0] = S[0][i]
    pre[1] = S[1][i]

print(ans)

Solution (Python):
def main():
    N = int(input())
    S = []
    S.append(input())
    S.append(input())
    MOD = 10**9 + 7
    ans = 1
    pre_mino_flag = -1 
    pass_flag = False
    if S[0][0] == S[1][0]:
        ans *= 3
        pre_mino_flag = 0
    else:
        ans *= 6
        pre_mino_flag = 1
        pass_flag = True
    
    for i in range(1, N):
        if pass_flag:
            pass_flag = False
            continue
        
        if S[0][i] == S[1][i]:
            if pre_mino_flag == 0:
                ans *= 2
                ans %= MOD
            else:
                pass
            pre_mino_flag = 0
        else:
            pass_flag = True
            if pre_mino_flag == 0:
                ans *= 2
                ans %= MOD
            else:
                ans *= 3
                ans %= MOD
            pre_mino_flag = 1
            
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

n = int(input())
s = [input() for _ in range(2)]
mod = 10 ** 9 + 7
""" 
たて*たて = *2
たて*よこ = *2
よこ*よこ = *3 (1,2)=(2,3)(2,1),(3,1)
よこ*たて = *1
"""
tmp = 1
pos = 0  
pre_state = -1  
while pos < n:
    if s[0][pos] == s[1][pos]:
        if pos == 0:
            tmp *= 3
        else:
            if pre_state == 0:
                tmp *= 2
            else:
                tmp *= 1
        pre_state = 0
        pos += 1
    else:
        if pos == 0:
            tmp *= 6
        else:
            if pre_state == 0:
                tmp *= 2
            else:
                tmp *= 3
        pre_state = 1
        pos += 2
    tmp %= mod
print(tmp)

Solution (Python):
n=int(input())
s1=list(input())
s2=list(input())
ans=0
if s1[0]==s2[0]:
    ans=3
else:
    ans=6
for i in range(n-1):
    if s1[i]==s2[i]:
        ans*=2
    else:
        if s1[i]==s1[i+1]:
            continue
        else:
            if s1[i+1]!=s2[i+1]:
                ans*=3
            else:
                ans*=1
print(ans%1000000007)

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

def rle(string):
    rle_str = string[0]
    rle_cnt = 1
    ans_l = []
    for i in range(1, len(string)):
        if rle_str == string[i]:
            rle_cnt += 1
        else:
            ans_l.append([rle_str, rle_cnt])
            rle_str = string[i]
            rle_cnt = 1
    ans_l.append([rle_str, rle_cnt])
    return ans_l

rle_s=rle(s1)

ans=rle_s[0][1]*3
left=rle_s[0][1]

for s, i in rle_s[1:]:
    if left==1 and i==1:
        ans*=2
    elif left==1 and i==2:
        ans*=2
    elif left==2 and i==1:
        ans*=1
    elif left==2 and i==2:
        ans*=3
    left=i

print(ans%mod)

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

def rle(string):
    rle_str = string[0]
    rle_cnt = 1
    ans_l = []
    for i in range(1, len(string)):
        if rle_str == string[i]:
            rle_cnt += 1
        else:
            ans_l.append([rle_str, rle_cnt])
            rle_str = string[i]
            rle_cnt = 1
    ans_l.append([rle_str, rle_cnt])
    return ans_l

rle_s=rle(s1)

if rle_s[0][1]==1:
    ans=3
    left=1
elif rle_s[0][1]==2:
    ans=6
    left=2

for s, i in rle_s[1:]:
    if left==1 and i==1:
        ans*=2
    elif left==1 and i==2:
        ans*=2
    elif left==2 and i==1:
        ans*=1
    elif left==2 and i==2:
        ans*=3
    left=i

print(ans%mod)