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() for _ in range(2)]
mod = 10 ** 9 + 7

dp = [0 for _ in range(n)]
tate = [s[0][i] == s[1][i] for i in range(n)]

if tate[0]:
    dp[0] = 3
    x = 1
else:
    dp[0] = dp[1] = 6
    x = 2

while x < n:
    if tate[x-1] and tate[x]:
        dp[x] = (dp[x-1] * 2) % mod
    elif tate[x-1]:
        dp[x] = (dp[x-1] * 2) % mod
        dp[x+1] = dp[x]
        x += 1
    elif tate[x-1] == False and tate[x]:
        dp[x] = dp[x-1]
    else:
        dp[x] = (dp[x-1] * 3) % mod
        dp[x+1] = dp[x]
        x += 1
    x += 1
    
print(dp[n-1])

Solution (Python):
n = int(input())
s = [input() for _ in range(2)]

ans = 1
mod = 1000000007
count = 0
flag = True

while count < n:
    if count == 0:
        if s[0][count] == s[1][count]:
            ans *= 3
            count += 1
        else:
            ans *= 3 * 2
            count += 2
            flag = False
    else:
        if flag:
            if s[0][count] == s[1][count]:
                ans *= 2
                count += 1
            else:
                ans *= 2 * 1
                count += 2
                flag = False
        else:
            if s[0][count] == s[1][count]:
                ans *= 1
                count += 1
                flag = True
            else:
                ans *= 3
                count += 2
    ans %= mod

print(ans)

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


if S1[0] == S2[0] :
    ret = 3
    pre = False
    i = 1
else :
    ret = 6
    pre = True
    i = 2

while i < N :
    cur = (S1[i] != S2[i])
    if not pre :
        ret *= 2
    elif pre and cur :
        ret *= 3
    
    ret %= mod
    
    if cur :
        i += 2
    else :
        i += 1
    pre = cur
    
print(ret)

Solution (Python):
def solve():
    N = int(input())
    S1 = input()
    S2 = input()
    MOD = 1000000007
    
    pattern = []
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            pattern.append(0)
            i += 1
        else:
            pattern.append(1)
            i += 2
    
    ans = 3 if pattern[0] == 0 else 6
    for i in range(1, len(pattern)):
        if pattern[i] == 0:
            if pattern[i - 1] == 0:
                ans = ans * 2 % MOD
        else:
            if pattern[i - 1] == 0:
                ans = ans * 2 % MOD
            else:
                ans = ans * 3 % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
seq = [[],[]]
seq[0] = input()
seq[1] = input()
i = 0

ans = 3
cnt_vert = 0
cnt_hor = 0
m = 1000000007

while i < len(seq[0]):
    if seq[0][i] == seq[1][i]: 
        if cnt_vert == 0:
            mult = 1
        elif cnt_vert > 0:
            mult = 2
        else:
            raise ValueError("wtf?")
        cnt_vert += 1
        cnt_hor = 0

    else:
        if cnt_hor == 0:
            mult = 2
        elif cnt_hor > 0:
            mult = 3
        else:
            
            raise ValueError("wtf hor")
        cnt_vert = 0
        cnt_hor += 1
        i += 1
    
    i += 1
    ans *= mult
    if ans > m:
        ans = ans % m
print(ans)

Solution (Python):

m = 1000000007

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

state = ""
ans = 1
for n in range(N):
    s1, s2 = S1[n], S2[n]

    if s1 == s2:
        if state == "":
            ans = (ans*3) % m
        elif state == "tate":
            ans = (ans*2) % m
        state = "tate"
    else:
        if state == "yoko_continue":
            state = "yoko"
            continue
        elif state == "":
            ans = (ans*3*2) % m
        elif state == "tate":
            ans = (ans*2) % m
        elif state == "yoko":
            ans = (ans*3) % m
        state = "yoko_continue"

print(ans)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


MOD = 1000000007  


def solve(N: int, S: "List[str]"):
    ans = 1
    pdtype = 0
    i = 0
    while i < N:
        dtype = 2 if S[0][i] != S[1][i] else 1
        ans = {
            (0, 1): lambda: 3,
            (0, 2): lambda: 6,
            (1, 1): lambda: ans * 2,
            (1, 2): lambda: ans * 2,
            (2, 1): lambda: ans,
            (2, 2): lambda: ans * 3,
        }[pdtype, dtype]() % MOD
        i += dtype
        pdtype = dtype
    print(ans)


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):
n = int(input().strip())
s1 = input().strip()
s2 = input().strip()
mod = 1000000007
vert = False
hor1 = False
hor2 = False

if s1[0] == s2[0]:
    ans = 3
    vert = True
else:
    ans = 6
    hor1 = True
for i in range(1, n):
    if s1[i] == s2[i]:
        if vert:
            ans = (ans * 2) % mod
        vert = True
        hor1 = False
        hor2 = False
    else:
        if vert:
            ans = (ans * 2) % mod
            vert = False
            hor1 = True
            hor2 = False
        elif hor1:
            vert = False
            hor1 = False
            hor2 = True
        elif hor2:
            ans = (ans * 3) % mod
            vert = False
            hor1 = True
            hor2 = False
print(ans)

Solution (Python):
N=int(input())
S1=input()
S2=input()
pr=10**9+7
t=0
a=1
c=0
while t<N:
    if S1[t]==S2[t]:
        a=a*(3-c)%pr
        t+=1
        c=1
    else:
        if c==0:
            a=6
        elif c==1:
            a=a*2%pr
        else:
            a=a*3%pr
        t+=2
        c=2
print(a)

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter


MOD = 10**9+7

N = int(input())
S = []
for _ in range(2):
    s = input()
    S.append(s)

i = 0
if S[0][i] == S[1][i]:
    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
        else: ans *= 1
        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):
n = int(input())
s = [input() for _ in range(2)]

ans = 1
law = 10 ** 9 + 7

i = 0
while i < n:
    if s[0][i] == s[1][i]:
        if i == 0:
            ans *= 3
        else:
            ans *= 3 - len({s[0][i-1], s[1][i-1]})
        i += 1
    else:
        if i == 0:
            ans *= 6
        else:
            if s[0][i-1] == s[1][i-1]:
                ans *= 2
            else:
                ans *= 3
        i += 2
    ans %= law
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
s1 = input()
s2 = input()

r = 0
ans = 1

pre_is_x = True
while r < N:
    if r == 0:
        if s1[r] == s2[r]:
            
            ans *= 3
            r += 1
            pre_is_x = True
        else:
            
            ans *= 6
            r += 2
            pre_is_x = False
    

    elif s1[r] == s2[r]:
        
        if pre_is_x == True:
            
            ans *= 2
        else:
            
            ans *= 1
        r += 1
        pre_is_x = True
    else:
        
        if pre_is_x == True:
            
            ans *= 2
        else:
            
            ans *= 3
        r += 2
        pre_is_x = False

print(ans % mod)

Solution (Python):

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

i = 0
count = 0
prestate = -1
while i < N:
    if i == 0:
        if m[0][0] != m[1][0]:
            count = 6
            prestate = 0
            i += 2
        else:
            count = 3
            prestate = 1
            i += 1
    else:
        if m[0][i] == m[1][i]: 
            if prestate == 1:
                count *= 2
                count %= int(1e9+7)
            i += 1
            prestate = 1
        else:
            if prestate == 0:
                count *= 3
            else:
                count *= 2
            count %= int(1e9+7)
            i += 2
            prestate = 0
            
print(count)

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

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

ans = 1
index =0
if s1[0] == s2[0]:
  ans *= 3
  index = 1
else:
  ans *= 3 * 2
  index = 2
  
while index < n:
  if s1[index-1] == s2[index-1]:
    ans *= 2
    if s1[index] == s2[index]:
      index += 1
    else:
      index += 2
      
  else:
    if s1[index] == s2[index]:
      index += 1
    else:
      ans *= 3
      index += 2
  
  ans %= MOD
      
print(ans)

Solution (Python):
n = int(input())
m = [0]
s1 = list(input())
s2 = list(input())
for i in range(n):
    if s1[i] == s2[i]:
        m.append(1)
    else:
        if i % 2 == 0:
            m.append(2)

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

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

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

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

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


def is_vertical(i):
    return s[0][i] == s[1][i]


i = 0
if is_vertical(i):
    ans = 3
    prev_is_vertical = True
    i += 1
else:
    ans = 3 * 2
    prev_is_vertical = False
    i += 2

while i < n:
    if is_vertical(i):
        if prev_is_vertical:
            ans *= 2
        else:
            ans *= 1
        prev_is_vertical = True
        i += 1

    else:
        if prev_is_vertical:
            ans *= 2
        else:
            ans *= 3
        prev_is_vertical = False
        i += 2

    ans %= mod

print(ans)

Solution (Python):
n=int(input())
mass=[input()]
mass.append(input())
MOD=10**9+7
if mass[0][0]==mass[1][0]:
    ans=3
    x=0
    y=1
    yoko=False
else:
    ans=6
    x=0
    y=2
    yoko=True
while y<n:
    if x==0:
        if mass[x][y]==mass[x+1][y]:
            if yoko:
                y+=1
            else:
                ans*=2
                y+=1
            yoko=False
        else:
            if yoko:
                ans*=3
            else:
                ans*=2
            yoko=True
            y+=2
print(ans%MOD)

Solution (Python):
n=int(input())
mass=[input()]
mass.append(input())
MOD=10**9+7
if mass[0][0]==mass[1][0]:
    ans=3
    x=0
    y=1
    yoko=False
else:
    ans=6
    x=0
    y=2
    yoko=True
while y<n:
    if x==0:
        if mass[x][y]==mass[x+1][y]:
            yoko=False
            if mass[0][y-1]==mass[1][y-1]:
                ans*=2
                y+=1
            else:
                y+=1
        else:
            if yoko:
                ans*=3
            else:
                ans*=2
            yoko=True
            y+=2
print(ans%MOD)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    mod = 1000000007

    N = int(input())
    d = input().rstrip()
    input()
    domino = []
    i = 0
    
    if len(d)==1:
        print(3)
        exit()
    if len(d)==2:
        print(6)
        exit()
    while 1:
        if d[i]==d[i+1]:
            domino.append(0)
            i += 2
        else:
            domino.append(1)
            i += 1
        if i==len(d)-1:
            domino.append(1)
            break
        if i==len(d):
            break
    if domino[0]:
        res = 3
    else:
        res = 6
    for i in range(1, len(domino)):
        if domino[i-1]:
            res *= 2
        else:
            if not domino[i]:
                res *= 3
    print(res%mod)
            

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
N = int(input())
a = input()
b = input()
ans = 0
i = 0
beforeState = True
while i < N:
    if i == 0:
        if a[i] == b[i]:
            ans = 3
            beforeState = True
        else:
            ans = 6
            i += 1
            beforeState = False
    else:
        if a[i] == b[i]:
            if beforeState:
                ans *= 2
            else:
                ans *= 1
            beforeState = True
        else:
            if beforeState:
                ans *= 2
            else:
                ans *= 3
            beforeState = False
            i += 1
    ans = ans%MOD
    i += 1
print(ans)

Solution (Python):







MOD = 10**9+7
N = int(input())
S1 = input()
S2 = input()
pre1 = S1[0]
pre2 = S2[0]

if pre1 != pre2:
    ans = 6
else:
    ans = 3
for s1, s2 in zip(S1[1:], S2[1:]):
    if pre1 == s1 and pre2 == s2:
        pass
    elif pre1 != pre2 and s1 != s2:
        
        ans *= 3
    elif pre1 != pre2 and s1 == s2:
        
        pass
    elif pre1 == pre2 and s1 != s2:
        
        ans *= 2
    elif pre1 == pre2 and s1 == s2:
        
        ans *= 2

    if ans >= MOD:
        ans %= MOD

    pre1, pre2 = s1, s2


print(ans % MOD)

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

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


s = set()


ans = 1

if S1[0] == S2[0]:
    ans *= 3
    ans %= mod
    s.add(S1[0])
else:
    ans *= 3 * 2
    ans %= mod
    s.add(S1[0])
    s.add(S2[0])

for i in range(1, N):
    
    if S1[i] == S2[i]:
        if S1[i - 1] == S2[i - 1]:
            ans *= 2
            ans %= mod
        s.add(S1[i])
    
    
    elif S1[i] not in s and S1[i - 1] == S2[i - 1]:
        ans *= 2
        ans %= mod
        s.add(S1[i])
        s.add(S2[i])
    elif S1[i] not in s:
        ans *= 3
        ans %= mod
        s.add(S1[i])
        s.add(S2[i])

print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    S1=input()
    S2=input()
    L=[0]
    
    
    i=0
    for _ in range(N):
        if S1[i]==S2[i]:
            L.append(1)
            i+=1
        else:
            L.append(2)
            i+=2
        if i>=N:
            break
    ans=1
    
    for i in range(1,len(L)):
        if L[i-1]==0:
            if L[i]==1:
                ans*=3
            else:
                ans*=6
        elif L[i-1]==1:
            ans*=2
        else:
            if L[i]==1:
                continue
            else:
                ans*=3
        ans%=mod
    print(ans)
        
    

main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n = II()
    s1 = S()
    s2 = S()
    i = 0
    f = 0
    if s1[i] == s2[i]:
        ans = 3
        i += 1
        f = 1
    else:
        ans = 6
        i += 2
    while i < n:
        if s1[i] == s2[i]:
            ans *= 2 if f else 1
            ans %= mod
            i += 1
            f = 1
            continue
        i += 2
        ans *= 2 if f else 3
        f = 0
        ans %= mod
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
S = []
for _ in range(2):
    s = str(input())
    S.append(s)

count = 0
mod = (10**9) +7

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

while count < n-1:
    if (S[0][count] == S[1][count]) and (S[0][count+1] == S[1][count+1]):
        ans = ans * 2
        ans = ans % mod
        count += 1
    elif S[0][count] == S[1][count]:
        ans = ans * 2
        ans = ans % mod
        count += 1
    elif count >= n-2:
        break
    elif S[0][count+2] == S[1][count+2]:
        ans = ans
        count += 2
    else:
        ans = ans * 3
        ans = ans % mod
        count += 2
print(ans)

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

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

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

L = []

for i in range(n):
    if s1[i] == s2[i]:
        L.append(0)
    else:
        if i == n-1:
            continue
        if s1[i] == s1[i+1]:
            L.append(1)

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

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

L = []

for i in range(n):
    if s1[i] == s2[i]:
        L.append(0)
    else:
        if i == n-1:
            continue
        if s1[i] == s1[i+1]:
            L.append(1)

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

Solution (Python):

n = int(input())
mod = 10**9 + 7
s = input()
t = [1]
for i in range(1,n):
  if s[i-1] == s[i]:
    t[-1] += 1
  else:
    t.append(1)

l = len(t)
if t[0] == 2:
  ans = 6
else:
  ans = 3
for j in range(1,l):
  if t[j-1] == 1:
    ans *= 2
    ans %= mod
  elif t[j] == 2:
    ans *= 3
    ans %= mod
print(ans)

Solution (Python):
def main():
    n=int(input())
    domino=[list(input()) for i in range(2)]
    mod=10**9+7

    if domino[0][0]==domino[1][0]:
        dp=[3]
        i=1
        before=True
    else:
        dp=[6]
        i=2
        before=False

    while i<n:
        if domino[0][i]==domino[1][i]:
            if before:
                nex=dp[-1]*2%mod
                dp.append(nex)
            else:
                nex=dp[-1]%mod
                dp.append(nex)
            before=True
            i+=1
        else:
            if before:
                nex=dp[-1]*2%mod
                dp.append(nex)
            else:
                nex=dp[-1]*3%mod
                dp.append(nex)
            before=False
            i+=2
    print(dp[-1])
if __name__=='__main__':
    main()

Solution (Python):
def main():
    width = int(input())
    grid = [input() for _ in range(2)]
    mod = 1000000007
    index = 0
    answer = 0
    former_grid = 0  
    while index < width:
        if index == 0:
            if grid[0][index] == grid[1][index]:
                answer = 3
                former_grid = 1
            else:
                answer = 6
                former_grid = 0
                index += 1
        else:
            if former_grid:
                
                answer = answer * 2 % mod
                if not grid[0][index] == grid[1][index]:
                    index += 1
                    former_grid = 0
            else:
                
                if grid[0][index] == grid[1][index]:
                    former_grid = 1
                else:
                    answer = answer * 3 % mod
                    index += 1
        index += 1
    print(answer)


if __name__ == '__main__':
    main()

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

if s1[0] == s2[0]:
    ans = 3
    q = 1
else:
    ans = 6
    q = -1

for i in range(1, n):
    x = s1[i]
    y = s2[i]
    if x == y:
        if q == 0:
            q = 1
        elif q == 1:
            ans *= 2
    else:
        if q == -1:
            q = 0
        elif q == 0:
            ans *= 3
            q = -1
        else:
            ans *= 2
            q = -1
    ans %= mod
print(ans%mod)

Solution (Python):
MOD = 10 ** 9 + 7
N = int(input())
S1 = input().strip()
S2 = input().strip()
compress = []
before = 0
for i in range(N):
    if before == 2:
        before = 0
        continue
    if S1[i] == S2[i]:
        compress.append(1)
        before = 1
    else:
        compress.append(2)
        before = 2

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

print(ans % MOD)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
S = [S1,S2]
mod = 10**9+7
ans = 1
i = 0
prev = None
while i < N:
    if S[0][i] == S[1][i]:
        i += 1
        if prev is None:
            ans *= 3
        elif prev:
            ans *= 2
        else:
            ans *= 1
        prev = True
    else:
        i += 2
        if prev is None:
            ans *= 6
        elif prev:
            ans *= 2
        else:
            ans *= 3
        prev = False
    ans %= mod
print(ans%mod)

Solution (Python):
mo=10**9+7
n=int(input())+1
s=input()+' '

S=[]
p=s[0]
i=0
while i<n-1:
    c=s[i+1]
    if c==p:
        S+=[2]
        i+=2
    else:
        S+=[1]
        i+=1
    if i<n:
        p=s[i]

p=S.pop()
if p==1:
    ans=3
else:
    ans=6
while S:
    c=S.pop()
    if (p,c)==(1,1):
        ans*=2
    elif (p,c)==(1,2):
        ans*=2
    elif (p,c)==(2,2):
        ans*=3
    elif (p,c)==(2,1):
        ans*=1
    ans%=mo
    p=c
print(ans)

Solution (Python):
n = int(input())
l = [list(input()) for i in range(2)]

mod = 10**9+7

ans = 1
check = 0
count = 0
while count < n:
    if l[0][count] == l[1][count]:
        if count == 0:
            ans *= 3
            count += 1
            check = 1
        else:
            if check == 1:
                ans *= 2
                ans %= mod
                count += 1
            elif check == 2:
                count += 1
                check = 1
    else:
        if count == 0:
            ans *= 6
            count += 2
            check = 2
        else:
            if check == 1:
                ans *= 2
                ans %= mod
                count += 2
                check = 2
            else:
                ans *= 3
                ans %= mod
                count += 2
print(ans%mod)

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

prev = 0  

pattern = 1
skip = False
for s1, s2 in zip(S1, S2):
    if skip:
        skip = False
        continue

    if s1 == s2:
        block = 1
    else:
        block = 2
        skip = True

    if prev == 0:
        if block == 1:
            pattern = pattern * 3 % mod
            prev = 1
        else:
            pattern = pattern * 6 % mod
            prev = 2

    elif prev == 1:
        if block == 1:
            pattern = pattern * 2 % mod
            prev = 1
        else:
            pattern = pattern * 2 % mod
            prev = 2

    elif prev == 2:
        if block == 1:
            prev = 1
        else:
            pattern = pattern * 3 % mod
            prev = 2

print(pattern)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10**9+7
n = int(readline())
u = readline().rstrip().decode('utf-8')
d = readline().rstrip().decode('utf-8')

i = 0
ans = 1
touch = 0
while True:
    if i >= n:
        break
    if u[i] == d[i]:
        ans *= 3-touch
        touch = 1
        i += 1
    else:
        if touch == 2:
            ans *= 3
            i+=2
        else:
            ans *= (3-touch)*(2-touch)
            touch = 2
            i += 2

print(ans%mod)

Solution (Python):
import sys

input = sys.stdin.readline


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

    ans = 1
    now = 0
    i = 0
    while i < N:
        if S1[i] != S2[i]:
            if now == 0:
                ans *= 6
            elif now == 1:
                ans *= 2
            else:
                ans *= 3
            now = 2
            i += 2
        else:
            if now == 0:
                ans *= 3
            elif now == 1:
                ans *= 2
            else:
                ans *= 1
            now = 1
            i += 1

    print(ans % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
mod = 10**9+7
dp = [-1] * (n)
if s1[0] == s2[0]:
    dp[0] = 1 
else:
    dp[0] = 2
for i in range(n-1):
    if dp[i] == -1:
        continue
    if s1[i] == s2[i]:
        dp[i+1] = (dp[i] * 2) % mod
        continue
    if i+2 >= n:
        break
    if s1[i+2] == s2[i+2]:
        dp[i+2] = dp[i]
    else:
        dp[i+2] = (dp[i] * 3) % mod

ans = dp[-1] if dp[-1] != -1 else dp[-2]
print((ans * 3) % mod)

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


l=[]
for i in range(N):
    if i>=1:
        if S[0][i]==S[0][i-1]:
            continue

    if S[0][i]==S[1][i]:
        l.append("x")
    else:
        l.append("y")
ans = 1

for i in range(len(l)):
    if i==0:
        if l[i]=="x":
            ans *= 3
        else:
            ans *= 6
        continue
    if l[i]=="x":
        if l[i-1]=="x":
            ans *= 2
        else:
            ans *= 1
    else:
        if l[i-1]=="x":
            ans *= 2
        else:
            ans *= 3
ans = ans%MOD
print(ans)

Solution (Python):
N=int(input())
A=input()
B=input()
C=[]
count=1
for i in range(N-1):
  if A[i]!=A[i+1]:
    C.append(count)
    count=1
  else:
    count+=1
if N==1:
  print(3)
  exit()
  
if A[-1]==A[-2]:
  C.append(2)
else:
  C.append(1)

ans=3
if C[0]==2:
  ans*=2
d=len(C)
for i in range(1,d):
  if C[i]==1 and C[i-1]==2:
    ans*=1
    ans%=10**9+7
  elif C[i]==2 and C[i-1]==2:
    ans*=3
    ans%=10**9+7
  else:
    ans*=2
    ans%=10**9+7
print(ans%(10**9+7))

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

s1 = list(input())
s2 = list(input())

kind = 0
next_step = 0

pre = 0
step = 0
for _ in range(n):
  if next_step > n-1:
    break
  w1 = s1[next_step]
  w2 = s2[next_step]
  if next_step > 0:
    if w1 == w2:
      next_step += 1
      if pre == 0:
        kind *= 2
      else:
        kind *= 1
      pre = 0
    else:
      next_step += 2
      if pre == 0:
        kind *= 2
      else:
        kind *= 3
      pre = 1
  else:
    if w1 == w2:
      kind += 3
      next_step += 1
      pre = 0
    else:
      kind += 6
      next_step += 2
      pre = 1

mod = 1000000007
print(kind%mod)

Solution (Python):
import sys


def main():
    N = int(input())
    S = [list(str(input())) for _ in range(2)]
    dp = [0 for _ in range(N)]
    MOD = 10**9+7
    
    if S[0][0] == S[1][0]:
        dp[0] = 3
        for i in range(1,N):
            if S[0][i-1] != S[0][i]:
                if S[0][i-1] == S[1][i-1]:
                    dp[i] = (dp[i-1]*2)%MOD
                else:
                    if S[0][i] == S[1][i]:
                        dp[i] = dp[i-1]
                    else:
                        dp[i] = (dp[i-1]*3)%MOD
            else:
                dp[i] = dp[i-1]
    else:
        dp[0] = dp[1] = 6
        for i in range(2,N):
            if S[0][i-1] != S[0][i]:
                if S[0][i-1] == S[1][i-1]:
                    dp[i] = (dp[i-1]*2)%MOD
                else:
                    if S[0][i] == S[1][i]:
                        dp[i] = dp[i-1]
                    else:
                        dp[i] = (dp[i-1]*3)%MOD
            else:
                dp[i] = dp[i-1]
                
    print(dp[-1]%MOD)

if __name__ == "__main__":
    main()