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

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int, S: "List[str]"):
    i = 0
    res = 1
    before = 0 
    while i < N:
        if S[0][i] == S[1][i]:
            if i == 0:
                res = 3
            elif before == 0:
                res = res * 2 % MOD
            else:
                res = res
            before = 0
            i += 1
        else:
            if i == 0:
                res = 6
            elif before == 0:
                res = res * 2 % MOD
            else:
                res = res * 3 % MOD
            before = 1
            i += 2
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = [ next(tokens) for _ in range(2) ]  
    solve(N, S)

if __name__ == '__main__':
    main()

Solution (Python):
def solve(n, s):
    i = 0
    v_or_h = []
    cmb = 1
    while i < n:
        
        
        if s[0][i] == s[1][i]:
            v_or_h.append('v')
            i += 1
        
        else:
            v_or_h.append('h')
            i += 2

    length = len(v_or_h)

    for j in range(length):
        if v_or_h[j] == 'v':
            if j == 0:
                cmb *= 3
            else:
                if v_or_h[j-1] == 'v':
                    cmb *= 2
                else:
                    pass
        else:
            if j == 0:
                cmb *= 6
            else:
                if v_or_h[j-1] == 'v':
                    cmb *= 2
                else:
                    cmb *= 3

    return cmb % 1000000007


if __name__ == '__main__':
    n = int(input())
    s = []
    for _ in range(2):
        s.append(input())
    print(solve(n, s))

Solution (Python):
N=int(input())
S=(input(),input())
a=1
i=0
s=0
mod=10**9+7
while i<N:
    if S[0][i]==S[1][i]:
        if s==0:
            a=3 if i==0 else (a*2)%mod
        s=0
    else:
        if s==0:
            a=6 if i==0 else (a*2)%mod
        else:
            a=6 if i==0 else (a*3)%mod
        s=1
        i+=1
    i+=1
print(a)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
code = []
mod = 10**9+7
index = 0
while index < N:
    if S1[index] == S2[index]:
        code.append("A")
        index += 1
    else:
        code.append("B")
        index += 2

if code[0] == "A":
    ans = 3
else:
    ans = 6

for i in range(1, len(code)):
    if code[i-1] == "A" and code[i] == "A":
        ans = ans*2 % mod
    elif code[i-1] == "A" and code[i] == "B":
        ans = ans*2 % mod
    elif code[i-1] == "B" and code[i] == "A":
        continue
    else:
        ans = ans*3 % mod

print(ans)

Solution (Python):
MOD = 1000000007

def solve(n, s1, s2):
    if s1[0] != s2[0]:
        ans = 6
        i = 2
        prev_solid = False
    else:
        ans = 3
        i = 1
        prev_solid = True
    shape_factor_mapping = {
        (True, True): 2,
        (True, False): 2,
        (False, True): 1,
        (False, False): 3
    }
    while i < n:
        solid = (s1[i] == s2[i])
        factor = shape_factor_mapping[prev_solid, solid]
        ans = (factor * ans) % MOD
        i += 2 - solid
        prev_solid = solid
    return ans

n = int(input())
s1 = input()
s2 = input()
print(solve(n, s1, s2))

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

sys.setrecursionlimit(10 ** 7)

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


def scan_domino(a: list, b: list):
    n = len(a)
    cnt = 0
    domino = ""

    while cnt < n:
        if a[cnt] == b[cnt]:
            domino += "x"
            cnt += 1
        else:
            domino += "y"
            cnt += 2

    return domino


def cnt_pattern(domino, mod):
    ans = 3 if domino[0] == "x" else 6
    for dleft, dright in zip(domino[:-1], domino[1:]):
        if dleft == "x" and dright == "x":
            ans *= 2
        elif dleft == "x" and dright == "y":
            ans *= 2
        elif dleft == "y" and dright == "x":
            ans *= 1
        else:
            ans *= 3

        ans %= mod

    return ans


n = ni()
a = lc()
b = lc()

MOD = 10**9 + 7

domino = scan_domino(a, b)
pats = cnt_pattern(domino, MOD)

print(pats)

Solution (Python):



def main():
    n = int(input())
    s = [input() for _ in range(2)]
    mod = 10 ** 9 + 7
    ans = 1
    i = 0

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

    while i < n:
        if s[0][i] == s[1][i]:
            if s[0][i - 1] == s[1][i - 1]:
                ans *= 2

            i += 1
        else:
            if s[0][i - 1] == s[1][i - 1]:
                ans *= 2
            else:
                ans *= 3

            i += 2

        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    n = int(input())
    s = [input() for _ in range(2)]
    mod = 10 ** 9 + 7
    ans = 1
    i = 0

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

    while i < n:
        if s[0][i] == s[1][i]:
            if s[0][i - 1] == s[1][i - 1]:
                ans *= 2

            i += 1
        else:
            if s[0][i - 1] == s[1][i - 1]:
                ans *= 2
            else:
                ans *= 3

            i += 2

        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = [input() for _ in range(2)]
mod = 10**9+7
is_2 = False
cnt = 1
li = []
for ind,i in enumerate(S[0]):
    if(is_2):
        is_2 = False
        continue
    if(ind==N-1):
        li.append(1)
        break
    if(S[0][ind+1]==i):
        li.append(2)
        is_2=True
    else:
        li.append(1)

for ind,i in enumerate(li):
    if(ind==0):
        if(i==1):
            cnt *= 3
        else:
            cnt *= 6
    else:
        if(li[ind-1]==1):
            cnt *= 2
        elif(li[ind-1]==i and i==2):
            cnt *= 3
    cnt%=mod
print(cnt)

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

S1 = input()
S2 = input()

dom_list = []
flag=False
for i in range(N):
    if S1[i]==S2[i]:
        dom_list.append(0)
    else:
        if flag:
            dom_list.append(1)
            flag=False
        else:
            flag=True

D = [0]*len(dom_list)
if dom_list[0]==0:
    D[0]=3
else:
    D[0]=6

mod = 10**9 + 7

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

print(D[len(dom_list)-1])

Solution (Python):
N = int(input())
S = input()
T = input()
res = 3*(1+(S[0]!=T[0]))
if N == 1:
    print(res)
    exit()
if N == 2:
    print(6)
    exit()
for i in range(1,N-1):
    if S[i-1] == S[i-1+1] and T[i-1] == T[i-1+1] and S[i-1+2] == T[i-1+2]:
        res *= 1
    elif S[i-1+1] == S[i-1+2] and T[i-1+1] == T[i-1+2] and S[i-1] == T[i-1]:
        res *= 2 
    elif S[i-1] == T[i-1] and S[i-1+1] == T[i-1+1] and S[i-1+2] == T[i-1+2]:
        res *= 2
    elif S[i-1+1] == S[i-1+2] and T[i-1+1] == T[i-1+2] and S[i-1] != T[i-1]:
        res *= 3
    elif S[i-1] == S[i-1+1] and T[i-1] == T[i-1+1] and S[i-1+2] != T[i-1+2]:
        res *= 1
    elif S[i-1] != T[i-1] and S[i-1+1] == T[i-1+1] and S[i-1+2] == T[i-1+2]:
        res *= 1
    elif S[i-1] == T[i-1] and S[i-1+1] == T[i-1+1] and S[i-1+2] != T[i-1+2]:
        res *= 2
    else:
        res *= 1
    res %= 10**9+7
if S[-1]==T[-1] and S[-2]==T[-2]:
    res *= 2
    res %= 10**9+7
print(res)

Solution (Python):
from functools import reduce


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

MOD = 1000000007


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))



ans, _ = reduce(
    lambda acc, s:
        (3 * acc[0], 3) if acc[1] == 0 and s[0] == s[1] else
        (6 * acc[0], 1) if acc[1] == 0 and s[0] != s[1] else
        (acc[0], 2) if acc[1] == 1 else
        (acc[0], 3) if acc[1] == 2 and s[0] == s[1] else
        (3 * acc[0], 1) if acc[1] == 2 and s[0] != s[1] else
        (2 * acc[0], 3) if acc[1] == 3 and s[0] == s[1] else
        (2 * acc[0], 1),
    zip(S1, S2),
    (ModInt(1), 0)
)


print(ans)

Solution (Python):
from functools import reduce


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

MOD = 1000000007


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))



ans, _ = reduce(
    lambda acc, s: (
        (3 * acc[0], 3) if acc[1] == 0 and s[0] == s[1] else
        (6 * acc[0], 1) if acc[1] == 0 and s[0] != s[1] else
        (acc[0], 2) if acc[1] == 1 else
        (acc[0], 3) if acc[1] == 2 and s[0] == s[1] else
        (3 * acc[0], 1) if acc[1] == 2 and s[0] != s[1] else
        (2 * acc[0], 3) if acc[1] == 3 and s[0] == s[1] else
        (2 * acc[0], 1)
    ),
    zip(S1, S2),
    (ModInt(1), 0)
)


print(ans)

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

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

Solution (Python):

MOD = int(1e9) + 7

def main():
    buf = input()
    N = int(buf)
    S = []
    for i in range(2):
        buf = input()
        S.append(buf)
    last_pattern = None 
    combination = 1
    point = 0
    while point < N:
        if S[0][point] == S[1][point]: 
            if last_pattern is None: 
                combination *= 3
            elif last_pattern == 1:
                combination *= 2 
            else: 
                combination *= 1 
            last_pattern = 1
            point += 1
        else: 
            if last_pattern is None: 
                combination *= 6
            elif last_pattern == 1:
                combination *= 2 
            else: 
                combination *= 3 
            last_pattern = 2
            point += 2
        combination %= MOD
    print(combination)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
t = input()
ans = 1
i = 0
while i <= n-1:
    if s[i] == t[i]:
        if i == 0:
            ans *= 3
        else:
            if before == "yoko":
                pass
            else:
                ans *= 2
        i += 1
        before = "tate"

    else:
        if i == 0:
            ans *= 6
        else:
            if before == "yoko":
                ans *= 3
            else:
                ans *= 2
        i += 2
        before = "yoko"
    ans %= 1000000007
print(ans)

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

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

S1, S2 = s1[0], s2[0]

for s, _ in zip(s1, s2):
    if S1[-1] != s:
        S1 += s
        S2 += _

TATE, YOKO = 0, 1

if S1[0] == S2[0]:
    prev = TATE
    cum = 3
else:
    prev = YOKO
    cum = 6

for i in range(1, len(S1)):
    if S1[i] == S2[i]:
        now = TATE
    else:
        now = YOKO
    if now == TATE:
        if prev == YOKO:
            pass
        else:
            cum *= 2
        prev = TATE
    elif now == YOKO:
        if prev == YOKO:
            cum *= 3
        else:
            cum *= 2
        prev = YOKO

    cum %= (1000000007)
print(int(cum))

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

Solution (Python):
N = int(input())
s1 = input()
s2 = input()
p = 0
ans = 1
while p < N:
      
      if s1[p] == s2[p]:
            if p == 0:
                  ans *= 3
            else:
                  
                  if s1[p-1] == s2[p-1]:
                        ans *= 2
                  
                  else:
                        ans *= 1
                  
            p += 1      
      elif s1[p] != s2[p]:
            if p == 0:
                  ans *= 6
            else:
              
              if s1[p-1] == s2[p-1]:
                ans *= 2
              elif s1[p-1] != s2[p-1]:
                
                ans *= 3
            p += 2

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

Solution (Python):
from itertools import*
input()
mod=10**9+7

x=[len(list(v))for k,v in groupby(input())]
if x[0]==1:
    ans=3
else:
    ans=6
if len(x)==1:
    print(ans)
else:
    for i in range(1,len(x)):
        if x[i-1]==1 and x[i]==1:
            ans*=2%mod
        elif x[i-1]==2 and x[i]==2:
            ans*=3%mod
        elif x[i-1]==1 and x[i]==2:
            ans*=2%mod
    print(ans%mod)

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)




n = int(input())
s1 = list(input())
s2 = list(input())
ans = 1
XY = 0
i,j=0,0
while  i<n:
    if s1[i] == s2[j]:
        if XY == "X":
            ans *= 2
            ans %= mod
            i +=1
            j +=1
        elif XY =="Y":
            i += 1
            j += 1
            XY ="X"
        else:
            ans *= 3
            ans %= mod
            i += 1
            j += 1
            XY ="X"
    else:
        if XY =="X":
            ans *= 2
            ans %= mod
            XY ="Y"
            i += 2
            j += 2
        elif XY =="Y":
            ans *= 3
            ans %= mod
            i += 2
            j += 2
        else:
            ans *= 6
            ans %=mod
            i += 2
            j += 2
            XY ="Y"
print(ans)

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

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

Solution (Python):
n = int(input())
s = input()

i = 0
j = 0
ans = 1
while i<n:
    if n-i>1 and s[i+1]==s[i]:
        if j == 0:
            ans *= 6
        elif j == 1:
            ans *= 2
        else:
            ans *= 3
        j = 2
        i+=2
    else:
        if j == 0:
            ans *= 3
        elif j == 1:
            ans *= 2
        j = 1
        i += 1
    ans %= 10**9+7

print(ans)

Solution (Python):
n = int(input())
s = input()
ss = input()

i = 0
state = 0
ans = 1
while i<n:
    if n-i>1:
        if s[i+1]==s[i]:
            if state == 0:
                ans *= 6
            elif state == 1:
                ans *= 2
            else:
                ans *= 3
            state = 2
            i+=2
        else:
            if state == 0:
                ans *= 3
            elif state == 1:
                ans *= 2
            else:
                ans *= 1
            state = 1
            i+=1
    else:
        if state == 0:
            ans *= 3
        elif state == 1:
            ans *= 2
        else:
            ans *= 1
        state = 1
        i += 1
    ans %= 10**9+7

print(ans)

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

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

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

print(ans)

Solution (Python):



N = int(input())
txt = input()

pattern = []
j = 0

while j < N:
  if j == N-1 or txt[j] != txt[j+1]:
    pattern.append(1)
    j += 1
  else:
    pattern.append(2)
    j += 2


    
MOD = 10**9 + 7

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

print(ans)

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

i = 0
ans = 1
tmp = ''

for _ in range(N):
    if i < N:
        if S1[i] == S2[i]:
            if tmp == '':
                ans *= 3
            elif tmp == 'X':
                ans *= 2
            else:
                ans *= 1   

            tmp = 'X'
            i += 1
      
    if i < N - 1:
        if S1[i] == S1[i+1] and S2[i] == S2[i+1]:
            if tmp == '':
                ans *= 6
            elif tmp == 'X':
                ans *= 2
            else:
                ans *= 3

            tmp = 'Y'
            i += 2
        

        
print(ans%1000000007)

Solution (Python):
N=int(input())
S1=input()
S2=input()
dominos=[]
index=0
while index<N:
    if S1[index]==S2[index]:
        dominos.append(0)
        index+=1
    else:
        dominos.append(1)
        index+=2
if dominos[0]==0:start=3
else:start=6
for k,c in enumerate(dominos):
    if k==0:continue
    elif dominos[k-1]==0:
        start*=2
    elif c:start*=3
    start%=10**9+7
print(start)

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

i = 0

if S[0] != T[0]:
    ans = 6
    i += 2
    flag = 1
else:
    ans = 3
    i += 1
    flag = 0

while i <= N-1:
    if S[i] != T[i] and flag == 1:
        ans *= 3
        i += 2
        flag = 1
    elif S[i] != T[i] and flag == 0:
        ans *= 2
        i += 2
        flag = 1
    elif S[i] == T[i] and flag == 1:
        ans *= 1
        i += 1
        flag = 0
    elif S[i] == T[i] and flag == 0:
        ans *= 2
        i += 1
        flag = 0


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

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

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

Solution (Python):
n=input()
s=input()+"2"
p=input()
a=[0]
i=0
d=1
while i<len(p):
    if s[i]==s[i+1]:
        if a[-1]==0:
            d*=6
        if a[-1]==1:
            d*=2
        if a[-1]==2:
            d*=3
        a.append(2)
        i+=2
    else:
        if a[-1]==0:
            d*=3
        if a[-1]==1:
            d*=2
        a.append(1)
        i+=1
print(d%(10**9+7))

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

l=[]
k=0
i=0
while i<n:
    if s[i]==t[i]:
        if k==0:
            l.append(3)
        elif k==1:
            l.append(2)
        else:
            l.append(1)
        k=1
        i+=1
    else:
        if k==0:
            l=l+[3,2]
        elif k==1:
            l=l+[2,1]
        else:
            l=l+[3,1]
        k=2
        i+=2
ans=1
for i in range(n):
    ans*=l[i]
print(ans%mod)

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

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


i = 0
while i < N - 1:
	if S[i] == S[i + 1]:
		d.append(2)
		i += 1
	else:
		d.append(1)
	i += 1

if N - 1 - i == 0:
	d.append(1)
n = len(d)

if d[0] == 1:
	dp = 3
else:
	dp = 6

for i in range(n - 1):
	if d[i] == 1:
		dp = dp * 2
	elif d[i] == 2 and d[i + 1] == 2:
		dp = dp * 3
	else:
		pass
	dp = dp % 1000000007

print(dp)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
N = int(input())
s = input()
t = input()
X = True
Y = False
MOD = 10**9+7
if s[0] == t[0]:
    i = 1
    ans = 3
    prev = X
else:
    i = 2
    ans = 6
    prev = Y
while i < N:
    if s[i] == t[i]:
        if prev:
            ans = (ans*2) % MOD
        else:
            ans = ans % MOD
        i += 1
        prev = X
    else:
        if prev:
            ans = (ans*2) % MOD
        else:
            ans = (ans*3) % MOD
        i += 2
        prev = Y
print(ans)

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

Solution (Python):
N = int(input())
S = input()
T = input()
cnt = 0
ans = 0
tateyoko = ''
if S[0] == T[0]:
  ans += 3
  cnt += 1
  tateyoko = 'tate'
else:
  ans += 6
  cnt += 2
  tateyoko = 'yoko'
while cnt < N:
  if tateyoko == 'tate':
    if S[cnt] != T[cnt]:
      ans *= 2
      cnt += 2
      tateyoko = 'yoko'
    else:
      ans *= 2
      cnt += 1
  else:
    if S[cnt] != T[cnt]:
      ans *= 3
      cnt += 2
    else:
      cnt += 1
      tateyoko = 'tate'
print(ans%1000000007)

Solution (Python):
N,S,T=int(input()),input(),input()
A=[int(S[i]==T[i])for i in range(N) if not i or S[i-1]!=S[i]]
a,d=6-3*A[0],len(A)-1
if d:
 for i in range(d):
  b,c=A[i+1],A[i]
  a*=3+2*c*b-2*b-c
print(a%(10**9+7))

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

ans = 1

for i in range(N) :
    if i == 0 :
        if s1[i] == s2[i] :
            ans *= 3
            state = 0
        else :
            ans *= 6
            state = 1
    else :
        if (s1[i] == s1[i-1]) and (s2[i] == s2[i-1]) :
            continue
        if s1[i] == s2[i] :
            if state == 0 :
                ans *= 2
            else :
                ans *= 1
            state = 0
        else :
            if state == 0 :
                ans *= 2
            else :
                ans *= 3
            state = 1
    ans %= 10**9+7

print(ans)

Solution (Python):


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

    m = 10 ** 9 + 7
    v = (S1[0] == S2[0])
    r, i = 0, 0
    if v:
        r = 3
        i = 1
    else:
        r = 6
        i = 2

    while i < N:
        if S1[i] == S2[i]:
            if v:
                r *= 2
                r %= m
            v = True
            i += 1
        else:
            if v:
                r *= 2
                r %= m
            else:
                r *= 3
                r %= m
            v = False
            i += 2


    print(r)


if __name__ == '__main__':
    main()

Solution (Python):















import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

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

i = 0
prev = None
ans = 1
while i < N:
    if S1[i] == S2[i]:
        if prev is None:
            ans *= 3
        if prev == 'ver':
            ans *= 2
        if prev == 'hor':
            pass
        prev = 'ver'
        i += 1
    else:
        if prev is None:
            ans *= 6
        if prev == 'ver':
            ans *= 2
        if prev == 'hor':
            ans *= 3
        prev = 'hor'
        i += 2
    ans %= MOD
print(ans)

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

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

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

H = ''
for i in range(N):
    if S1[i] == S2[i]:
        H += 't'
    else:
        H += 'Y'
H = H.replace('YY','y')
K = len(H)
if K == 1 :
    print(3*N)
    sys.exit()
if H[0] == 'y':
    ans = 6
    prev = 'y'
else:
    ans = 3
    prev = 't'
for i in H[1:]:
    if prev == 'y':
        if i == 'y':
            ans = ans*3 %mod
    else:
        ans = ans*2 %mod
    prev = i
print(ans%mod)