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



Sample input:
3
aab
ccb


Sample output:
6

Submission status: Accepted

Solution code:
from math import factorial

N = int(input())
S1 = input()
S2 = input()
S = list(zip(S1,S2))

new = []
z = 0
while z != len(S):
    if S[z][0] == S[z][1]:
        new.append("V")
    else:
        new.append("H")
        z += 1
    z += 1

if new[0] == "H":
    result = 6
else:
    result = 3
    
for i in range(len(new)-1):
    if new[i] == "H" and new[i+1] == "H":
        result = (result * 3) % 1000000007
    elif new[i] == "H" and new[i+1] == "V":
        result = (result * 1) % 1000000007
    elif new[i] == "V":
        result = (result * 2) % 1000000007
print(result)

Submission status: Accepted

Solution code:
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n,  = read_line(int)

m = 1000000007

domino = []
domino.append(input())
domino.append(input())

# print(domino[0])
# print(domino[1])

def compress(line):
    x = [line[0]]
    for c in line[1:]:
        if x[-1] != c:
            x.append(c)
    return x

domino[0] = compress(domino[0])
domino[1] = compress(domino[1])

xs = []
for i in range(len(domino[0])):
    xs.append(domino[0][i] != domino[1][i])
# print(xs)

patterns = None
if xs[0]:
    patterns = 6
else:
    patterns = 3

lastX = xs[0]
for x in xs[1:]:
    if x:
        # T -> T
        if lastX:
            patterns *= 3
        else:
            # F -> T
            patterns *= 2
    else:
        # T -> F
        if lastX:
            patterns *= 1
        else: # F -> F
            patterns *= 2
    lastX = x

print(patterns % m)

# T -> T

# 6 * 4 = 24

# 0|1120
# 1|2002

# 0
# 2

# 1
# 0

# 1
# 2

# 2
# 0

# 2
# 1


# F -> T

# 3 * 2 = 6

# 0|12
# 0|21
# 
# 1|02
# 1|20
# 
# 2|10
# 2|01


# T -> F

# 6 * 1 = 6

# 0|2
# 1|2

# 0|1
# 2|1

# 1|2
# 0|2

# 1|0
# 2|0

# 2|1
# 0|1

# 2|0
# 1|0

# F -> F

# 3 * 2 = 6

# 0 | 12
# 1 | 02
# 2 | 01

Submission status: Accepted

Solution code:
mod = 1000000007
N = int(input())
S = input()
T = input()
a = 1
b = 0 ###前が横だったら0 縦だったら1
i = 0
while i < N:
	if i == 0: ###初期処理
		if N == 1:
			a *= 3
			break
		if N == 2:
			a *= 6
			break
		else:
			if S[0] == S[1]:
				a *= 6
				i += 2
				b = 0
			else:
				a *= 3
				i += 1
				b = 1
	if i == N-1:
		if b == 0: ###前が横で次が縦
			a *= 1
			i += 1
			b = 1
			break
		if b == 1: ###前が縦で次も縦
			a *= 2
			i += 1
			b = 1
			break
	if S[i] == S[i+1]:
		if b == 0: ###前が横で次も横
			a *= 3
			i += 2
			b = 0
			continue
		if b == 1: ###前が縦で次が横
			a *= 2
			i += 2
			b = 0
			continue
	else:
		if b == 0: ###前が横で次が縦
			a *= 1
			i += 1
			b = 1
			continue
		if b == 1: ###前が縦で次も縦
			a *= 2
			i += 1
			b = 1
			continue
print(a % mod)

Submission status: Accepted

Solution code:
N = int(input())						# 5
a = list(input())
#b = [int(i) for i in input().split()]	# 1 2 3 4 5 ...

MOD = 1000000007

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




b=[]
bSkip = False

for i in range(N):
	if bSkip:
		bSkip = False
		continue
	if i==N-1:
		b.append(1)
	else:
		if a[i] == a[i+1]:
			b.append(2)
			bSkip = True
		else:
			b.append(1)

#print(b)


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


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


print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
count = 1
j = 0
if s1[0] == s2[0]:
  count *= 3
else:
  count *= 6 
  j += 1
while j < n-1:
  if s1[j] == s2[j]:
    if s1[j+1] == s2[j+1]:
      count *= 2
      count %= 1000000007
    else:
      count *= 2
      count %= 1000000007
      j += 1
  else:
    if s1[j+1] == s2[j+1]:
      count *= 1
      count %= 1000000007
    else:
      count *= 3
      count %= 1000000007
      j += 1
  j += 1
print(count)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
t=input()
p=i=0
if s[0]==t[0]:
    r=3
    p=1
    i+=1
else:
    r=6
    p=2
    i+=2
while i<n:
    if s[i]==t[i]:
        r=r*(3-p)%1000000007
        p=1
        i+=1
    else:
        r=r*(p+1)%1000000007
        p=2
        i+=2
print(r)

Submission status: Accepted

Solution code:
def d():
    N  = int(input())
    S1 = input()
    S2 = input()
    from collections import deque
    s = deque(S1)
    S = ''
    for _ in range(N):
        if len(s) >= 2:
            if s[0] == s[1]:
                S += 'Z'
                s.popleft()
                s.popleft()
            else:
                S += 'I'
                s.popleft()
        elif len(s) == 1:
            S += 'I'
            s.popleft()
        else:
            break
    res = 6 if S[0] == 'Z' else 3
    for i in range(len(S)-1):
        if S[i:i+2] == 'II':
            res *= 2
        if S[i:i+2] == 'IZ':
            res *= 2
        if S[i:i+2] == 'ZI':
            res *= 1
        if S[i:i+2] == 'ZZ':
            res *= 3
    print(res % 1000000007)

d()

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
mod = 1000000007 

t = 0
dominoes = []
while (t<n):
    if(s1[t]==s2[t]):
        dominoes.append("X")
        t+=1
    else:
        dominoes.append("Y")
        t+=2

ans = 3 if(dominoes[0]=="X") else 6
for i, d in enumerate(dominoes):
    if(i==0):
        temp = d
        continue
    if(temp=="X" and d == "X"):
        ans *= 2 % mod
    elif(temp=="X" and d == "Y"):
        ans *= 2 % mod
    elif(temp=="Y" and d == "Y"):
        ans *= 3 % mod
    temp = d

print(ans % mod)

Submission status: Accepted

Solution code:
mod = 1000000007

N = int(input())
u = input()
d = input()

c = 1
t = 0

if u[t] == d[t]:
    t += 1
    c *= 3
    lh = 'l'
else:
    t += 2
    c *= 6
    lh = 'h'

while t < N:
    if u[t] == d[t]:
        t += 1
        if lh == 'l':
            c = (c * 2) % mod
        lh = 'l'
    else:
        t += 2
        if lh == 'l':
            c = (c * 2) % mod
        else:
            c = (c * 3) % mod
        lh = 'h'
print(c)

Submission status: Accepted

Solution code:
def main():
    """
    2 * N, square
    N domino
    domino, 2 * 1 or 1 * 2

    [pattern 1]
    aabb
    ccdd
    (a, d) and (b, c) => 2 colors
    (a, d) and c and b => 3 colors
    (c, b) and a and d => 3 colors

    [pattern 2]
    aab
    ccb
    => 3 colors

    [pattern 3]
    abc
    abc
    2 or 3 colors

    このような塗り方が何通りあるかを
    mod 1000000007 で求めてください．
    """
    N = int(input())
    S1 = input()
    S2 = input()

    a = 1
    before = "f"
    # f irst
    # v ertical
    # h orizontal
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            # v
            if before == "f":
                a *= 3
            elif before == "v":
                a *= 2
            else:
                pass
            before = "v"
            i += 1
        else:
            # h
            if before == "f":
                # 3 P 2
                a *= 6
            elif before == "v":
                a *= 2
            else:
                a *= 3
            before = "h"
            i += 2

    print(a % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import deque


MOD = 10 ** 9 + 7

def main():
    n = int(input())
    ds = [input(), input()]

    total = 1
    i = 0

    while i < n:
        if ds[0][i] == ds[1][i]: # vertical segment
            if i == 0: # first element, 3 colors
                x = 3
            else:
                if ds[0][i - 1] == ds[1][i - 1]: # previous segment vertical, 2 colors
                    x = 2
                else:
                    x = 1
        else: # horizontal segment
            if i == 0: # first element, 3 * 2 = 6 colorings
                x = 6 
            else:
                if ds[0][i - 1] == ds[1][i - 1]: # previous segment vertical, 2 colors
                    x = 2
                else:
                    x = 3

            i += 1

        total = (total * x) % MOD

        i += 1

    print(total)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = input()
S1 = list(raw_input())
S2 = list(raw_input())

if N == 1:
    ans = 3
else:
    if S1[0] == S1[1]:
        index = 2
        ans   = 6
        vertical = False
    else:
        index = 1
        ans = 3
        vertical = True
    while True:
        if (N - index) == 1:
            if vertical:
                ans *= 2
            index += 1
        elif (N - index) == 0:
            break
        else:
            if S1[index] == S1[index+1]:
                index += 2
                if vertical:
                    ans *= 2
                else:
                    ans *= 3
                vertical = False
            else:
                index += 1
                if vertical:
                    ans *= 2
                vertical = True

print(ans % 1000000007)

Submission status: Accepted

Solution code:
# Coloring Dominoes
N = int(input())
s1 = input()
s2 = input()

if (s1[0]==s2[0]):
    c = 3
else:
    c = 6


for i in range(N-1):
    if (s1[i]==s2[i]):
        c*=2
    else:
        if (s1[i]!=s1[i+1]):
            if (s1[i+1]!=s2[i+1]):
                c*=3
print(c%1000000007)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
max = 1000000007

ans = 1
pt = 0
beforestate = 0 
if s1[0] == s2[0]:
    ans = 3
    pt = 1
    beforestate = 0 #tate
else :
    ans = 6
    pt = 2
    beforestate = 1 #yoko

while pt < n:
    if beforestate == 0 and s1[pt] == s2[pt]:
        ans = ans * 2 % max
        beforestate = 0
        pt += 1
    elif beforestate == 1 and s1[pt] == s2[pt]:
        beforestate = 0
        pt += 1
    elif beforestate == 0 and s1[pt] != s2[pt]:
        ans = ans * 2 % max
        beforestate = 1
        pt += 2
    elif beforestate == 1 and s1[pt] != s2[pt]:
        ans = ans * 3 % max
        beforestate = 1
        pt += 2

print(ans)

Submission status: Accepted

Solution code:
n = input()
n = int(n)
s_1 = input()
s_2 = input()
s_list = []

nagasa = len(s_1)
i = 0
while i < nagasa:
    if s_1[i] == s_2[i]:
        s_list.append(0)
        i += 1
    else:
        s_list.append(1)
        i += 2

if s_list[0]==0:
    kotae = 3
else:
    kotae = 3*2
    
mod = 1000000007
mod = 1000000007
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

for i in range(len(s_list)-1):
    if s_list[i]==0:
        kotae = mul(kotae,2)
    elif s_list[i]==1 and s_list[i+1]==0:
        pass
    else:
        kotae = mul(kotae,3)
print(kotae)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()  # aab
S2 = input()  # ccb

ans_pt = []
ans = 1
i = 0
while i < N:
    if S1[i] == S2[i]:
        ans_pt.append("H")
        i += 1
    else:
        ans_pt.append("W")
        i += 2

if ans_pt[0] == "W":
    ans = ans*6
else:
    ans = ans*3

for i in range(1, len(ans_pt)):
    if ans_pt[i-1] == "W" and ans_pt[i] == "W":
        ans = ans*3
    elif ans_pt[i-1] == "W" and ans_pt[i] == "H":
        ans = ans*1
    elif ans_pt[i-1] == "H" and ans_pt[i] == "W":
        ans = ans*2
    else:
        ans = ans*2

print(ans % 1000000007)

Submission status: Accepted

Solution code:
N = int(input())
s1 = input()
s2 = input()
index = 0
ans = 3
def multi(x,y):
    return x*y % (10**9+7)
if s1[index] != s2[index]:
    ans = 6
    index += 2
else:
    index += 1
while index < N:
    if s1[index] == s2[index]:
        if s1[index-1] == s2[index-1]:
            ans = multi(ans, 2)
        index += 1
    else:
        if s1[index-1] == s2[index-1]:
            ans = multi(ans, 2)
        else:
            ans = multi(ans, 3)
        index += 2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = [input() for i in range(2)]

c = 0
if S[0][0] == S[1][0]:
    n = 3
    s = 'tate'
    c += 1
else:
    n = 6
    s = 'yoko'
    c += 2

while c < N:
    if S[0][c] == S[1][c]:
        if s == 'tate':
            n *= 2
            c += 1
        else:
            s = 'tate'
            c += 1
    else:
        if s == 'tate':
            n *= 2
            s = 'yoko'
            c += 2
        else:
            n *= 3
            c += 2

print(n % 1000000007)

Submission status: Accepted

Solution code:
#! -*- coding:utf-8 -*-
n = int(input())
s1 = list(map(str,list(input())))
s2 = list(map(str,list(input())))

flag = 0
a = 0

x = 1
for i in range(n):
    if a == 1:
        a = 0
    elif flag == 0 and s1[i] == s2[i]:
        x *= 3
        flag = 1
    elif flag == 0 and s1[i] != s2[i]:
        x *= 3 * 2
        a = 1
        flag = 2
    elif flag == 1 and s1[i] == s2[i]:
        x *= 2
        flag = 1
    elif flag == 1 and s1[i] != s2[i]:
        x *= 2 * 1
        a = 1
        flag = 2
    elif flag == 2 and s1[i] == s2[i]:
        x *= 1
        flag = 1
    elif flag == 2 and s1[i] != s2[i]:
        x *= 3
        a = 1
        flag = 2
print(x%1000000007)

Submission status: Accepted

Solution code:
n = input()
st1 = raw_input()
st2 = raw_input()
m = 1
mod = 1000000007
pat = 0 # or 1,2
bl = False
for i in range(n):
  #print m
  if pat == 2 and bl:
    bl = False
    continue
  if st1[i] == st2[i] and pat == 0:
    m = m*3%mod
    pat = 1
  elif st1[i] == st2[i] and pat == 1:
    m = m*2%mod
    pat = 1
  elif st1[i] == st2[i] and pat == 2:
    pat = 1
  elif st1[i] != st2[i] and pat == 0:
    m = m*6%mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat == 1:
    m = m*2%mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat == 2:
    m = m*3%mod
    pat = 2
    bl = True
print m

Submission status: Accepted

Solution code:
n = int(raw_input())
d1 = raw_input()
d2 = raw_input()

ans = 3
flag = 0
for i in range(n):
    if flag == -1:
        flag = 1
        continue
    if i < n-1 and d1[i] == d1[i+1]:
        if flag == 1:
            ans *= 3
        elif flag in [0, 2]:
            ans *= 2
        flag = -1
    elif d1[i] == d2[i]:
        if flag in [0, 1]:
            ans *= 1
        else:
            ans *= 2
        flag = 2
    else:
        'error'
print ans % 1000000007

Submission status: Accepted

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

if s1[0] == s2[0]:
    res = 3
    state = 'v'
else:
    res = 6
    state = 'h1'


for i in range(1, n):
    if s1[i] == s2[i]: # if vertical
        if state == 'v':
            res = 2 * res % 1000000007
        else:
            pass

        state = 'v'

    else: # if horizontal
        if state == 'h1':
            state = 'h2'

        elif state == 'h2':
            res = 3 * res % 1000000007
            state = 'h1'

        elif state == 'v':
            res = 2 * res % 1000000007
            state = 'h1'

print(res)

Submission status: Accepted

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

n = raw_input()
n = int(n)

s1 = raw_input()
s2 = raw_input()

ans = 1

mod = 1000000007

i = 0

if s1[i] == s2[i]:
    ans = ans * 3
    i += 1
else:
    ans = ans * 6
    i += 2

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

print ans

Submission status: Accepted

Solution code:
N = int(input())
S = [input(), input()]
MOD = 1000000007

i = 0
ans = 3
prev_n = 0
while i < N:
    if S[0][i] == S[1][i]:
        n = 1
        i += 1
    else:
        n = 2
        i += 2
    if prev_n == 0 and n == 2:
        ans *= 2
    elif prev_n == 1:
        ans = (ans * 2) % MOD
    elif prev_n == 2 and n == 2:
        ans = (ans * 3) % MOD
    prev_n = n
print(ans)

Submission status: Accepted

Solution code:
#coding=UTF-8
hou=1000000007

N=int(input())

Sone=input()
Stwo=input()

tateyoko=[]
idx=0
owari=len(Sone)
while idx < owari:
    if Sone[idx] == Stwo[idx]:
        #tate
        tateyoko.append(1)
        idx=idx+1
    else:
        #yoko
        tateyoko.append(2)
        idx=idx+2

ans=1
mae=None
for mono in tateyoko:
    if mono==1:
        #tate
        if mae==None:
            kake=3
        elif mae==1:
            kake=2
        else:
            kake=1
    else:
        #yoko
        if mae==None:
            kake=6
        elif mae==1:
            kake=2*1
        else:
            kake=1+2

    mae=mono
    ans=(ans*kake)%hou

print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(raw_input())
S=[]
for n in xrange(2):
    S.append(raw_input().strip())

M=1000000007
if N==1:
    cnt = 3
else:
    if S[0][0]==S[1][0]:
        cnt = 3
        i=1
        ant=1
    else:
        cnt = 6
        i = 2
        ant = 0
    while i<N:
        if S[0][i]==S[1][i]:
            if ant==1:
                cnt = (cnt +cnt)%M
            else:
                ant=1
            i += 1
        else:
            if ant==0:
                cnt = (cnt *3)%M
            else:
                cnt = (cnt + cnt)%M
                ant = 0
            i += 2
print cnt

Submission status: Accepted

Solution code:
n=int(raw_input())
a=raw_input()
b=raw_input()
res = 1
i=0
s=0
M=1000000007
if a[i]==b[i] :
    res = 3
    i+=1
    s=1
else :
    res = 6
    i+=2
    s=2
while i<n :
    if a[i]==b[i] :
        if s==1 :
            res *= 2
            res %= M
        i+=1
        s=1
    else :
        if s==1 :
            res *= 2
            res %= M
        else :
            res *= 3
            res %= M
        i+=2
        s=2
print res

Submission status: Accepted

Solution code:
import sys


def inp(t): return t(sys.stdin.readline().strip())


def inpm(t): return map(t, sys.stdin.readline().split())


def inpl(t): return list(map(t, sys.stdin.readline().split()))


n = inp(int)
a = [inp(str), inp(str)]
dp = [0] * n

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

while i < n:
    if a[0][i - 1] == a[1][i - 1]:
        if a[0][i] == a[1][i]:
            dp[i] = dp[i - 1] * 2
            i += 1
        else:
            dp[i + 1] = dp[i - 1] * 2
            i += 2
    else:
        if a[0][i] == a[1][i]:
            dp[i] = dp[i - 1]
            i += 1
        else:
            dp[i + 1] = dp[i - 1] * 3
            i += 2

print(dp[n - 1] % 1000000007)

Submission status: Accepted

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

MOD = 1000000007

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
S1 = input()
S2 = input()

MOD = 1000000007
i = 1
ans = 3
tp = 0
if S1[0] != S2[0]:
    i = 2
    ans = 6
    tp = 1
while i < N:
    if S1[i] == S2[i]:
        ans = (ans * [2, 1][tp]) % MOD
        i += 1
        tp = 0
    else:
        ans = (ans * [2, 3][tp]) % MOD
        i += 2
        tp = 1

print(ans)

Submission status: Runtime Error

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

mod = 10**9+7

def judge(x):
    if s1[x] == s2[x]:
        b = 1
        if s1[x-1] == s2[x-1]:
           a = 2
        else:
            a = 1
    else:
        b = 2
        if s1[x-1] == s2[x-1]:
            a = 2
        else:
            a = 3
    return a, b


if s1[0] == s2[0]:
    ans = 3
    index =1
else:
    ans = 6
    index = 2


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


while index != n-1:
    key1, key2 = judge(index)
    index += key2
    ans *= key1
    ans %= mod
    #print(index, ans)

print(ans%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
L=input()
S=input()
T=[]
i=0
while n-2>=i:
	if L[i]==L[i+1]:
		T.append(0)
		i+=2
	else:
		T.append(1)
		i+=1

def f(x,y):
	if x==0 and y==1:
		return 1
	if x==0 and y==0:
		return 3
	if x==1 and y==1:
		return 2
	if x==1 and y==0:
		return 2
if T[0]==0:
	ans=3
else:
	ans=6


for i in range(len(T)-1):
	ans=ans*f(T[i],T[i+1])

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
L=input()
S=input()
T=[]
i=0
while n-2>=i:
	if L[i]==L[i+1]:
		T.append(0)
		i+=2
	else:
		T.append(1)
		i+=1

def f(x,y):
	if x==0 and y==1:
		return 1
	if x==0 and y==0:
		return 3
	if x==1 and y==1:
		return 2
	if x==1 and y==0:
		return 2
if T[0]==0:
	ans=3
else:
	ans=6

print(T)
for i in range(len(T)-1):
	ans=ans*f(T[i],T[i+1])

print(ans)

Submission status: Runtime Error

Solution code:
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=1
cnt=0
i=0
while i<n-1 and cnt<2:
    if a[i]==a[i+1]:
        ans*=a[i]
        i+=2
        cnt+=1
    else:
        i+=1
if cnt==2:
    print(ans)
else:
    print(0)

Submission status: Runtime Error

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

if len(S1) == 1:
    print(3)
else:
    if S1[0] != S2[0]:
        t = 2
        i = 2
        a = 6
    else:
        t = 1
        i = 1
        a = 3
    while True:
        if S1[i] != S2[i]:
            if t == 2:
                a *= 3
            else:
                a *= 2
            i += 2
            t = 2
        else:
            if t == 2:
                a *= 1
            else:
                a *= 2
            i += 1
            t = 1
        a %= 1000000007
        if i == len(S1):
            print(a)
            break

Submission status: Runtime Error

Solution code:
n=int(input())
mod=10**9+7

s1=input()
s2=input()

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

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

while True:
    if i==n-1:
        if l==0:
            ans*=2
            ans%=mod
        break

    if s1[i+1]==s1[i]:
        c=1
        i+=2
    else:
        c=0
        i+=1
    
    if l==0:
        ans*=2
    if l==1 and c==1:
        ans*=3
    
    ans%=mod
    
    l=c
    
print(ans)

Submission status: Runtime Error

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

mod=1000000007

x=0
cnt=1
while x<3:
    if x==0:
        if s1[x]==s2[x]:
            cnt*=3%mod
            x+=1
        else:
            cnt*=6%mod
            x+=2
    else:
        if s1[x-1]==s2[x-1]:
            #x-1:AA 
            #x  :BB CC
            if s1[x]==s2[x]:
                cnt*=2%mod
                x+=1
            #x-1:AA 
            #x  :BC  CB
            #    BC  CB
            else:
                cnt*=2%mod
                x+=2
        else:
            #x-1:AB
            #   :CC
            if s1[x]==s2[x]:
                cnt*=1%mod
                x+=1
            #x-1:AB
            #x  :BA CA BC 
            else:
                cnt*=3%mod
                x+=2

print(cnt%mod)

Submission status: Runtime Error

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

def mult(prev,now):
    if (prev == 1)&(now==0:
        return 1
    else:
        return 2

if n == 1:
    ans = 3
elif n == 2:
    ans = 6
else:
    
    i = 0
    flag = 0
    ans = 6
    
    while (i <= n - 1):
        if s1[i] != s2[i]:
            pat = 1
            i +=2
            flag += 1
        else:
            pat = 0
            flag += 1
            i += 1
            
        if flag == 1:
            prev = pat
            continue
        elif (flag == 2) & (i == 2):
            
            prev = pat
        else:
            now = pat
            ans *= mult(prev,now)
            prev = now
        
print(int(ans))

Submission status: Runtime Error

Solution code:
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)
N = int(input())
S1 = input()
S2 = input()
mod = 10 ** 9 + 7

# False->tate True->yoko
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)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    mod = 1000000007

    N = int(input())
    d = input().rstrip()
    input()
    domino = []
    i = 0
    #横０縦1
    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:
            break
    domino.append(1)
    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()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    mod = 1000000007

    N = int(input())
    d = input().rstrip()
    input()
    domino = []
    i = 0
    #横０縦1
    while 1:
        if d[i]==d[i+1]:
            domino.append(0)
            i += 2
        else:
            domino.append(1)
            i += 1
        if i==len(d)-1:
            break
    domino.append(1)
    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()

Submission status: Runtime Error

Solution code:
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 S[0][count+2] == S[1][count+2]:
        ans = ans
        count += 2
    else:
        ans = ans * 3
        ans = ans % mod
        count += 2
print(ans)

Submission status: Runtime Error

Solution code:
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:
        continue
    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)
# print(dp)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
s2 = input()
if len(s)==2:
    print(3)
    exit()
i = 0

d = []#0が縦、1が横
while i<n:
    try:
        if s[i]==s[i+1]:
            d.append(1)
            i+=1
        else:
            d.append(0)
        i+=1
    except:
        break

ans = 1
#print(d)
if d[0]==0:
    ans = 3
else:
    ans = 6
mod = 10**9+7
for j in range(1,len(d)):
    if d[j]==0:
        if d[j-1]==0:
            ans*=2
    else:
        if d[j-1]==1:
            ans*=3
        else:
            ans*=2####
    ans%=mod
    

    
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
s=list(input())
v=[]
for i in range(1,n):
    if s[i]==s[i-1]:
        del(v[-1])
        v.append(1)
        
    else:
        v.append(0)


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

mod = 1000000007

print(ans%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
S1=input()
S2=input()

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

Submission status: Runtime Error

Solution code:
n=int(input())
S1=input()
S2=input()

if n==1:
  print(3)
else:
  if S1[0]==S2[0]:
    ans,i=3,1
  else:
    ans,i=6,2
  while i<n:
    if S1[i]==S2[i]:
      ans *= 2 if S1[i-1]==S2[i-1] else 1
      i+=1
    else:
      ans *= 2 if S1[i-1]==S2[i-1] else 3
      i+=2
print(ans%(1000000007))