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())
s1=input()
s2=input()
l=[]
old="hoge"
for i in range(n):
    if s1[i]==s2[i]:
        l.append(0)
    elif s1[i]!=old:
        l.append(1)
    old=s1[i]
ans=1
flag=2
INF=10**9+7
for i in l:
    if flag==1:
        if i==1:ans=ans*3%INF
    elif flag==0:ans=ans*2%INF
    else:
        if i==0:ans*=3
        else:ans*=6
    flag=i
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
s = input()
t = input()

MOD = 10**9+7
if s[0] == t[0]:
    ans = 3
    i = 1
    yoko = 0
else:
    ans = 6
    i = 2
    yoko = 1


while i < n:
    if yoko:
        if s[i] == t[i]:
            i += 1
            yoko = 0
        else:
            ans *= 3
            i += 2
            yoko = 1
    else:
        if s[i] == t[i]:
            ans *= 2
            i += 1
            yoko = 0
        else:
            ans *= 2
            i += 2
            yoko = 1
    ans %= MOD
print(ans)

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

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

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

while col < n:
    if s[0][col] == s[1][col]:
        if s[0][col - 1] == s[1][col - 1]:
            ans *= 2
        col += 1
    else:
        if s[0][col - 1] == s[1][col - 1]:
            ans *= 2
        else:
            ans *= 3
        col += 2

    ans %= MOD

print(ans)

Solution (Python):
N = int(input())
S1 = input()
_ = input()
nums = [0]*N
ans = 3
c = 1
mod = 1000000007
for i in range(N-1):
    if S1[i] == S1[i + 1]:
        nums[i], nums[i + 1] = c,c
        c += 1

for i in range(N-1):
    if i > 0 and nums[i] == nums[i + 1] and nums[i] != 0 and nums[i - 1] != 0:
        ans *= 3 
    elif nums[i] == nums[i + 1] and nums[i] != 0:
        ans *= 2
    elif nums[i] == nums[i + 1] == 0:
        ans *= 2
    ans %= mod
print(ans)

Solution (Python):

import sys
from collections import deque
INF = float("inf")

MOD = 1000000007  


def solve(N: int, S: "List[str]"):

    counter = 1
    s1, s2 = S
    pre = 0
    i = 0
    while i < N:
        if s1[i] == s2[i]:
            counter *= 3-pre
            counter %= MOD
            i += 1
            pre = 1
        else:
            if pre == 0:
                counter *= 6
                counter %= MOD
            elif pre == 1:
                counter *= 2
                counter %= MOD
            else:
                counter *= 3
                counter %= MOD

            i += 2
            pre = 2

    print(counter)

    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):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







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


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def main():
    N = i_inpl()
    S1, S2 = input(), input()

    l = []
    i = 0
    while True:
        if S1[i] == S2[i]:
            l.append("X")
        else:
            l.append("Y")
            i += 1
        i += 1
        if i >= N:
            break

    if l[0] == "X":
        ans = 3
    else:
        ans = 6

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

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

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

com = 1
pre = "e"
flag = True
for i in range(n):
    if s1[i] == s2[i]:
        if pre == "e":
            com *= 3
        elif pre == "v":
            com *= 2
            com %= mod
        else:
            pass
        pre = "v"
    else:
        if flag == True:
            if pre == "e":
                com *= 6
            elif pre == "v":
                com *= 2
                com %= mod
            else:
                com *= 3
                com %= mod
            flag = False
        else:
            flag = True
        pre = "h"
print(com)

Solution (Python):
n=int(input())
s1=input()
s2=input()
g=["c"]
i=0
while i<n:
    if s1[i]==s2[i]:
        g.append("a")
        i+=1
    else:
        g.append("b")
        i+=2
ans=1
mod=10**9+7
for i in range(len(g)-1):
    if g[i]=="c":
        if g[i+1]=="a":
            ans=(ans*3)%mod
        else:
            ans=(ans*6)%mod
    elif g[i]=="a":
        ans=(ans*2)%mod
    else:
        if g[i+1]=="b":
            ans=(ans*3)%mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from math import *

N = int(input())
s, t = input(), input()
mod = 10**9+7
ans = 1
pre = -1
for a, b in zip(s, t):
    if pre == 0:
        ans *= 2
        if a == b:
            pre = 0
        else:
            pre = 1
    elif pre == 1:
        pre = 2
    elif pre == 2:
        if a == b:
            pre = 0
        else:
            ans *= 3
            pre = 1
    else:
        if a == b:
            ans *= 3
            pre = 0
        else:
            ans *= 6
            pre = 1
    ans %= mod
print(ans)

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

Solution (Python):
INF=10**9+7
n=int(input())
s1=input()
s2=input()
ans=1
v=0
h=0
i=0
while i!=n:
    if v==0 and h==0:
        if s1[i]==s2[i]:
            ans=3
            v=1
            i=i+1
        else:
            ans=3*2
            h=1
            i=i+2
    elif v==1:
        if s1[i]==s2[i]:
            ans=(ans*2)%INF
            i=i+1
        else:
            ans=(ans*2)%INF
            v=0
            h=1
            i=i+2
    elif h==1:
        if s1[i]==s2[i]:
            v=1
            h=0
            i=i+1
        else:
            ans=(ans*3)%INF
            i=i+2
print(ans)

Solution (Python):
MOD  = 1000000007

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

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

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

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

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
MOD = 10 ** 9 + 7
if S1[0] == S2[0]:
  ans = 3
  i = 1
  f = True
else:
  ans = 6
  i = 2
  f = False

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

print(ans)

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

ans = 1
for i in range(N):
    if i == 0:
        if S1[i]==S2[i]:
            c = 3
        else:
            c = 6
    else:
        if S1[i-1]==S1[i]:
            c = 1
        else:
            if S1[i-1]==S2[i-1]:
                c = 2
            elif S1[i]==S2[i]:
                c = 1
            else:
                c = 3
    ans *= c
    ans %= mod
print(ans)

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


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())
S1=input()
S2=input()
MOD=10**9+7
i=0
tmp=3
ans=1
if 1<N and S1[0]==S1[1]:
    tmp=6
while(i<N):
    if S1[i]==S2[i]:
        ans*=tmp
        ans%=MOD
        tmp=2
    else:
        i+=1
        ans*=tmp
        ans%=MOD
        tmp=1
        if i+2<N and S1[i+1]==S1[i+2]:
            tmp=3
    i+=1
print(ans)

Solution (Python):
n = int(input())
s = input()
s1 = []
mod = 1000000007
i = 0
while i < n-1:
    if s[i]==s[i+1]:
        s1.append(0)
        i += 1
    else:
        s1.append(1)
    i += 1

if s[n-2]!=s[n-1]:
    s1.append(1)

if n==1:
    s1.append(1)

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

print(ans%mod)

Solution (Python):


def main():
    num = int(input())
    data = [list(input()) for i in range(2)]

    kari = []
    pre = ''

    for i in range(num):
        now_data = data[0][i]
        if pre == '':
            pre = now_data
        elif now_data == pre:
            kari.append(1)
            pre = ''
        else:
            kari.append(0)
            pre = now_data
    if pre != '':
        kari.append(0)

    if kari[0]:
        ans = 6
    else:
        ans= 3
    mod = 10 ** 9 + 7
    pre_kari = kari[0]
    for i in range(1, len(kari)):
        now_kari = kari[i]
        if pre_kari and now_kari:
            ans = (ans * 3) % mod
        elif pre_kari and not now_kari:
            pass
        elif not pre_kari and not now_kari:
            ans = (ans * 2) % mod
        else:
            ans = (ans * 2) % mod
        pre_kari = now_kari


    print(ans % mod)





if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s1 = list(input())
s2 = list(input())
code = []

i = 0
while i < len(s1):
  if s1[i] == s2[i]:
    code.append('S')
    i += 1
  else:
    code.append('D')
    i += 2

mod = 1000000007
if code[0] == 'S':
  ptn = 3
else:
  ptn = 6
for i in range(1, len(code)):
  x, y = code[i-1], code[i]

  if x == 'S' and y == 'S':
    ptn = (ptn * 2) % mod
  elif x == 'S' and y == 'D':
    ptn = (ptn * 2) % mod
  elif x == 'D' and y == 'D':
    ptn = (ptn * 3) % mod
  elif x == 'D' and y == 'S':    
    ptn = ptn
print(ptn)

Solution (Python):
N = int(input())
S = ["0"+input() for _ in range(2)]

mod = 10**9 + 7
dp = [0]*(N+1)

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

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

print(dp[N])

Solution (Python):
n=int(input())
s1=input()
s2=input()
if n==1:
    print(3)
    exit()
s=""
i=0
while i<n:
    if s1[i]==s2[i]:
        s+="1"
        i+=1
    else:
        s+="2"
        i+=2
ans=0
if s[0]=="1":
    ans+=3
else:
    ans+=6
before=s[0]
for j in range(1,len(s)):
    if before=="1":
        if s[j]=="1":
            ans*=2
        else:
            ans*=2
    else:
        if s[j]=="2":
            ans*=3
    before=s[j]
print(ans%(10**9+7))

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int, S: "List[str]"):
    ret = 1
    status = 0
    i = 0
    while i < N:
        
        if status == 1:
            ret *= 2
        if S[0][i] == S[1][i]:
            if status == 0:
                ret *= 3
            status = 1
        else:
            if status == 0:
                ret *= 3 * 2
            elif status == 2:
                ret *= 3
            status = 2
            i += 1
        i += 1
        ret %= MOD
    ret %= MOD
    print(ret)
    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):
n = int(input())
s, t = input(), input()
p = ''
i = 0
while i < n:
    if s[i] == t[i]:
        p += 'X'
    else:
        p += 'Y'
        i += 1
    i += 1
ans = (3 if p[0] == 'X' else 6)
for i in range(1, len(p)):
    if p[i] == 'X':
        if p[i - 1] == 'X':
            ans *= 2
        else:
            ans *= 1
    else:
        if p[i - 1] == 'X':
            ans *= 2
        else:
            ans *= 3
print(ans % (10 ** 9 + 7))

Solution (Python):
DIV=10**9+7
N=int(input())
ST=[input(), input()]
PST=[]
ptr=0
while ptr < N:
    
    if ST[0][ptr] == ST[1][ptr]:
        ptr += 1
        PST.append(0)
    
    else:
        ptr += 2
        PST.append(1)



res = 3 if PST[0] == 0 else 6
for i in range(len(PST)-1):
    if PST[i] == 0 and PST[i+1] == 0:
        res = (res*2)%DIV
    elif PST[i] == 0 and PST[i+1] == 1:
        res = (res*2)%DIV
    elif PST[i] == 1 and PST[i+1] == 0:
        res = res
    elif PST[i] == 1 and PST[i+1] == 1:
        res = (res*3)%DIV

print(res)

Solution (Python):
n=int(input())
s1=list(input())
s2=list(input())
x=-1
if s1[0]==s2[0]:
  ct=3;k=1;p=1
else:
  ct=6;k=2;p=2
for i in range(k,n):
  if x!=i:
    if s1[i]==s2[i]:
      if p==1:
        ct*=2;p=1
      else:
        ct*=1;p=1
    else:
      x=i+1
      if p==1:
        ct*=2;p=2
      else:
        ct*=3;p=2
    ct%=(10**9+7)
print(ct)

Solution (Python):
n = int(input())
s = input()
t = input()
pointer = 0
ans = [1,0]
mod = 1000000007
while pointer < n:
	if s[pointer] == t[pointer]:

		pointer += 1
		if ans[1] == 0:
			ans[0] = ans[0] *3
		elif ans[1] == 1:
			ans[0] = ans[0] *2
		
		ans[1] = 1

	else:

		pointer += 2
		if ans[1] == 0:
			ans[0] = ans[0] *6
		elif ans[1] == 1:
			ans[0] = ans[0] *2
		elif ans[1] == 2:
			ans[0] = ans[0] *3
		
		ans[1] = 2

print(ans[0] % mod)

Solution (Python):











import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()
    T = ST()
    contin = False
    equal = False
    if S[0] == T[0]:
        ans = 3
        equal = True
    else:
        ans = 6
        contin = False
    start = 1 + (S[0] != T[0])
    for s, t in zip(S[start:], T[start:]):
        if s == t:
            if equal:
                ans *= 2
            else:
                pass
            equal = True
        else:
            if contin:
                if equal:
                    ans *= 2
                else:
                    ans *= 3
                contin = False
                equal = False
            else:
                contin = True
        ans %= mod
        
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):


from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys

sys.setrecursionlimit(10**6)



def main():
    input()
    x=[len(list(v))for k,v in groupby(input())]
    if x[0]==1:
        ans=3
    else:
        ans=6
    mod=10**9+7
    for i in range(1,len(x)):
        if x[i-1]==1 and x[i]==1:
            ans*=2%mod
        elif x[i-1]==1 and x[i]==2:
            ans*=2%mod
        elif x[i-1]==2 and x[i]==2:
            ans*=3%mod
    print(ans%mod)
if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

MOD = 1000000007

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
T = sys.stdin.readline().rstrip()

ans = 1

next_h = 6

next_v = 3
i = 0
while i < N:
    s, t = S[i], T[i]
    if s != t:
        
        ans *= next_h
        next_h = 3
        next_v = 1
        i += 2
    else:
        
        ans *= next_v
        next_h = 2
        next_v = 2
        i += 1
    ans %= MOD

print(ans)

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

mod=1000000007

str=""
i=0
while i<N:
	if S1[i]==S2[i]:
		str+="t"
		i+=1
	else:
		str+="y"
		i+=2


l=len(str)

ans=1
if str[0]=="t": ans*=3
else: ans*=6

for i in range(l-1):
	now=str[i]
	next=str[i+1]
	if now=="t" and next=="y":
		ans*=2
	elif now=="t" and next=="t":
		ans*=2
	elif  now=="y" and next=="y":
		ans*=3
	elif  now=="y" and next=="t":
		ans*=1
	ans%=mod

print ans

Solution (Python):
n = int(input())
a = input()
b = input()
if a[0]==b[0]:
    ans = 3
else:
    ans = 6
l = []
k = 0
while k<n:
    if k==n-1:
        l.append(1)
        k += 1
    elif a[k]==a[k+1]:
        l.append(0)
        k += 2
    else:
        l.append(1)
        k += 1
for i in range(1,len(l)):
    if l[i]==1 and l[i-1]==1:
        ans *= 2
    elif l[i]==0 and l[i-1]==1:
        ans *= 2
    elif l[i]==0 and l[i-1]==0:
        ans *= 3
print((ans)%(10**9+7))

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

li = []
c = 0
for i in range( len(S) ):
  if ( c < len(S)-1):
    if S[c]==S[c+1]:
      li.append(2)
      c +=2
    else:
      li.append(1)
      c+=1
  else:
    li.append(1)
    c+=1
  if (c==len(S)):
    break

if (li[0]==1):
  s = 3
else:
  s = 6

MOD = 1000000007
for i in range( len(li)-1 ):
  if ( li[i]==1 and li[i+1]==1 ):
    s = (s*2)%MOD
  if ( li[i]==1 and li[i+1]==2 ):
    s = (s*2)%MOD
  if ( li[i]==2 and li[i+1]==1 ):
    s = s
  if ( li[i]==2 and li[i+1]==2 ):
    s = (s*3)%MOD
print ( s%MOD )

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
mod = 1000000007
j = 0
if S1[0] == S2[0]:
    ans = 3
else:
    ans = 6
while 1:
    if S1[j] == S2[j]:
        j += 1
        if j >= N:
            break
        ans = (ans*2)%mod
    else:
        j += 2
        if j >= N:
            break
        if S1[j] != S2[j]:
            ans = (ans*3)%mod
print(ans)

Solution (Python):
from functools import reduce
import math

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    S1 = list(_ for _ in input())
    S2 = list(_ for _ in input())
    S1_used = [-1]*N
    S2_used = [-1]*N
    
    if S1[0] == S2[0]:
        ans = 3
    else:
        ans = 6
    for i in range(1,N):
        if S1[i] != S1[i-1] and S1[i] != S2[i]:
            if S1[i-1] == S2[i-1]:
                ans *=2
            else:
                ans *=3
        elif S1[i] != S1[i-1] and S1[i] == S2[i]:
            if S1[i-1] == S2[i-1]:
                ans *=2
    print(ans%MOD)
if __name__ == '__main__':
    main()

Solution (Python):

import sys
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  

def solve(N: int, S: "List[str]"):
    conv = []
    i = 0
    while i < N:
        c, o = (0, 1) if S[0][i] == S[1][i] else (1, 2)
        conv.append(c)
        i += o

    ret = 3 if conv[0] == 0 else 6
    for b, c in zip(conv, conv[1:]):
        if b == 0 and c == 0:
            ret *= 2
        elif b == 0 and c == 1:
            ret *= 2
        elif b == 1 and c == 0 :
            ret *= 1
        elif b == 1 and c == 1:
            ret *= 3
    return ret % MOD

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) ]  
    result = solve(N, S)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = [''] * 2
S[0] = input()
S[1] = input()

MOD = 10 ** 9 + 7

if S[0][0] == S[1][0]:
    ans = 3
    row = True
    skip = False
else:
    ans = 6
    row = False
    skip = True
for i in range(1, N):
    if not skip:
        if S[0][i] == S[1][i]:
            if row:
                ans *= 2
            else:
                ans *= 1
            row = True
        else:
            if row:
                ans *= 2
            else:
                ans *= 3
            row = False
            skip = True
        ans %= MOD
    else:
        skip = False

print(ans)

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

i = 1
if S1[0] == S2[0]:
    ans = 3
    state = 0
else:
    i+= 1
    ans = 6
    state = 1
mod  = 10**9 + 7
while N > i:
    if S1[i] != S2[i] and state == 0:
        ans *= 2
        i+=2
        state = 1
    elif S1[i] != S2[i] and state == 1:
        ans *= 3
        i+=2
    elif S1[i] == S2[i] and state == 0:
        ans *= 2
        i+= 1
    elif S1[i] == S2[i] and state == 1:
        ans *= 1
        i+=1
        state = 0

    ans %= mod
print(ans)

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

skip = False
double = False
for i in range(N):
    if skip:
        skip = False
        continue
    if i == 0:
        if S1[i] == S2[i]:
            ans = 3
        else:
            ans = 6
            skip = True
            double = True
    else:
        if S1[i] == S2[i]:
            if double:
                ans *= 1
            else:
                ans *= 2
            double = False            
        else:
            if double:
                ans *= 3
            else:
                ans *= 2
            skip = True
            double = True


ans = ans % 1000000007
print(ans)

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

s1 = input()
s2 = input()
dirct = []
i = 0
while i<n:
    if s1[i] ==s2[i]:
        dirct.append(True)
        i+=1
        continue
    else:
        i+=2
        dirct.append(False)
        continue
dp = [0]*52
MAX = 1000000007
for i in range(len(dirct)):
    if i == 0:
        if dirct[0]:
            dp[0]=3
        else:
            dp[0]=6
        continue
    
    if dirct[i] and dirct[i-1]:
        dp[i] = (dp[i-1]*2)%MAX
        continue
    
    if dirct[i] and (not dirct[i-1]):   
        dp[i] = dp[i-1]
        continue
    
    if (not dirct[i]) and dirct[i-1]:
        dp[i] = (dp[i-1]*2)%MAX
        continue
    
    if (not dirct[i]) and (not dirct[i-1]):
        dp[i] = (dp[i-1]*3)%MAX

print(dp[len(dirct)-1]%MAX)

Solution (Python):
n = int(input())
a = input().rstrip()
b = input().rstrip()
pattern = []
l = 0
while l < n:
    if a[l] == b[l]:
        pattern.append(1)
        l += 1
    else:
        pattern.append(0)
        l += 2

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

Solution (Python):
N = int(input())
A = input()
B = input()
ans = 3
for i in range(len(A) - 1):
  if A[i] == B[i] and A[i + 1] == B[i + 1]:
    ans *= 2
  if A[i] == B[i] and A[i + 1] != B[i + 1]:
    ans *= 2
  if A[i] != B[i] and A[i + 1] != B[i + 1] and A[i] != A[i + 1]:
    ans *= 3
  if A[i] != B[i] and A[i + 1] != B[i + 1] and A[i] == A[i + 1] and i == 0:
    ans *= 2
  ans %= 1000000007
print(ans)

Solution (Python):
mod = 10 ** 9 + 7
N = int(input())
S = input()
T = input()

ans = 1
if S[0] == T[0]:
    flag = 'tate'
    ans *= 3
else:
    flag = 'yoko'
    ans *= 6
    
for i in range(1, N):
    if S[i] == T[i]:
        if flag == 'tate':
            ans *= 2
            flag = 'tate'
        elif flag == 'yoko' or flag == 0:
            flag = 'tate'
    else:
        if flag == 'tate':
            ans *= 2
            flag = 'yoko'
        elif flag == 'yoko':
            flag = 0
        elif flag == 0:
            ans *= 3
            flag = 'yoko'

print(ans % mod)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(str, input().strip())) for _ in range(2)]
    MOD = 10**9 + 7

    D = []
    flag = False
    for i in range(N):
        if A[0][i] != A[1][i] and flag:
            D.append('h')
            flag = False
        elif A[0][i] != A[1][i]:
            flag = True
        else:
            D.append('v')

    if D[0] == 'h':
        ans = 6
    else:
        ans = 3

    for i in range(1, len(D)):
        if D[i-1] == 'v' and D[i] == 'h':
            ans *= 2
        elif D[i-1] == 'v' and D[i] == 'v':
            ans *= 2
        elif D[i-1] == 'h' and D[i] == 'h':
            ans *= 3
        else:
            ans *= 1

    return ans % MOD


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

Solution (Python):
N = int(input())
S_1 = list(input())
S_2 = list(input())
if S_1[0] == S_2[0]:
	before_style = 1
	pattern = 3
	i = 1
else:
	before_style = 2
	pattern = 6
	i = 2
	

while i < N:
	if S_1[i] == S_2[i]:
		if before_style == 1:
			before_style = 1
			i += 1			
			pattern *= 2
		else:
			before_style = 1
			i += 1	
			pattern *= 1		
	else:
		if before_style == 1:
			before_style = 2
			i += 2
			pattern *= 2
		else:
			before_style = 2
			i += 2
			pattern *= 3


print(pattern % 1000000007)

Solution (Python):
N=int(input())
mod=1000000007
S=input()
data=[]
exist=set()
for s in S:
    if s in exist:
        data[-1]+=1
    elif s not in exist:
        data.append(1)
        exist|={s,}
if data[0]==1:
    ans=3
elif data[0]==2:
    ans=6
for i in range(1,len(data)):
    if (data[i-1],data[i])==(1,1):ans=(ans*2)%mod
    elif (data[i-1],data[i])==(1,2):ans=(ans*2)%mod
    elif (data[i-1],data[i])==(2,1):ans=ans
    elif (data[i-1],data[i])==(2,2):ans=(ans*3)%mod
print(ans)

Solution (Python):
def coloring_dominoes(N: int, S1: str, S2: str)->int:
    MOD = 1000000007

    if S1[0] == S2[0]:
        offset = 1
        ret = 3
        before_dir = S1[0] == S2[0]
    else:
        offset = 2
        ret = 3 * 2
        before_dir = S1[0] == S2[0]

    i = offset
    while i < N:
        current_dir = S1[i] == S2[i]

        if before_dir and current_dir:
            ret *= 2
            i += 1
        elif before_dir and not current_dir:
            ret *= 2 * 1
            i += 2
        elif not before_dir and current_dir:
            ret *= 1
            i += 1
        else:
            ret *= 3
            i += 2

        ret %= MOD
        before_dir = current_dir

    return ret


if __name__ == "__main__":
    N = int(input())
    S1 = input()
    S2 = input()
    ans = coloring_dominoes(N, S1, S2)
    print(ans)

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

N = int(input())
S = [input() for _ in range(2)]
P = []
for i in range(2):
    note = 0
    s = ""
    for j in range(N):
        if S[i][j] == note:
            continue
        s += S[i][j]
        note = S[i][j]
    P.append(s)
f = []
for j in range(len(P[0])):
    t = P[0][j]; b = P[1][j]
    if t == b:
        f.append(1)
    else:
        f.append(0)

if f[0] == 1:
    ans = 3
else:
    ans = 6
for j in range(1,len(P[0])):
    if f[j] == 1:
        if f[j-1] == 1:
            ans *= 2
        else:
            pass
    else:
        if f[j-1] == 1:
            ans *= 2
        else:
            ans *= 3
    ans %= mod

print(ans)