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:
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  3 10:58:30 2018

@author: ashida
"""
N=int(input())

S1=list(input())
S2=list(input())

if len(S1)>1:
    if S1[0]==S1[1]:
        st=2
        ans=6
        flag=1
    else:
        st=1
        ans=3
        flag=-1
else:
    st=1
    ans=3
    flag=-1

while st<N:
    if st+1<N:
        if S1[st]==S1[st+1]:
            if flag<0:
                ans*=2
            else:
                ans*=3
            st+=2
            flag=1
        else:
            if flag<0:
                ans*=2
            else:
                ans*=1
            st+=1
            flag=-1
    else:
        if flag<0:
            ans*=2
        else:
            ans*=1
        st+=1
        
ans=ans%1000000007
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s1=input()
s2=input()
comb=0
tateyoko=''
i=0
while i<n:
  if i==0:
    if s1[0]==s2[0]:
      comb+=3
      tateyoko='tate'
      i+=1
    else:
      comb+=6
      tateyoko='yoko'
      i+=2
  elif s1[i]==s2[i]:
    i+=1
    if tateyoko=='tate':
      comb*=2
      comb%=1000000007
    else:
      tateyoko='tate'
  else:
    i+=2
    if tateyoko=='tate':
      tateyoko='yoko'
      comb*=2
      comb%=1000000007
    else:
      comb*=3
      comb%=1000000007
print(comb)

Submission status: Accepted

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

ds = []

i = 0
while i < N:
    if S1[i] == S2[i]:
        ds.append('X')
        i += 1
    else:
        ds.append('Y')
        i += 2

n = 0
if ds[0] == 'X':
    n = 3
else:
    n = 6
for i in range(1, len(ds)):
    if ds[i] == 'X':
        if ds[i - 1] == 'X':
            n *= 2 % 1000000007
        else:
            n *= 1 % 1000000007
    else:
        if ds[i - 1] == 'X':
            n *= 2 % 1000000007
        else:
            n *= 3 % 1000000007
print(n % 1000000007)

Submission status: Accepted

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

P = 1000000007
prev = None
i = 0
ans = 1
while i < N:
    split = S1[i] != S2[i]
    if prev is None:
        ans = 6 if split else 3
    elif prev:
        if split:
            ans = ans*3%P 
    else:
        ans = ans*2%P
    prev = split
    i += 2 if split else 1
print(ans)

Submission status: Accepted

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

M = 1000000007

c = 0
i = 0
result = 1

while i < N:
    if S1[i] == S2[i]:
        if c == 0:
            result = (result * 3) % M
        elif c == 1:
            result = (result * 2) % M
        elif c == 2:
            result = (result * 1) % M
        c = 1
        i += 1
    else:
        if c == 0:
            result = (result * 3 * 2) % M
        elif c == 1:
            result = (result * 2) % M
        elif c == 2:
            result = (result * 3) % M
        c = 2
        i += 2

print(result)

Submission status: Accepted

Solution code:
def mul_mod(x, y):
    return x * y % 1000000007


N = int(input())
S1 = input()
S2 = input()
L = []
i = 0
while i < N-1:
    if S1[i] == S1[i+1]:
        L.append(2)
        i += 2
    else:
        L.append(1)
        i += 1
if i == N-1:
    L.append(1)
ans = 1
if L[0] == 1:
    ans = 3
else:
    ans = 6
for i in range(1, len(L)):
    if L[i] == 1:
        if L[i-1] == 1:
            ans = mul_mod(ans, 2)
    else:
        if L[i-1] == 1:
            ans = mul_mod(ans, 2)
        else:
            ans = mul_mod(ans, 3)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(input())
b = list(input())
ans = 1
mod = 10**9 + 7
i = 0
while i <= n-1:
  
  if i == 0:
    if a[i] == b[i]:
      ans *= 3
      i += 1
    elif not a[i] == b[i]:
      ans *= 6
      i += 3
  else:
    if a[i-1] == b[i-1]:
      if a[i] == b[i]:
        ans *= 2
        i += 1
      else:
        ans *= 2
        i += 2
    elif not a[i-1] == b[i-1]:
      if not a[i] == b[i]:
        ans *= 3
        i += 2
      else:
        i += 1

print(ans % mod)

Submission status: Accepted

Solution code:
n = int(input())
S = list(input())
input()
MOD = 10**9+7

x = []
p = S[0]
c = 1
for s in S[1:]:
    if s == p:
        c += 1
    else:
        x.append(c)
        c = 1
    p = s
x.append(c)

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

Submission status: Accepted

Solution code:
MOD = 1000000007

def m():
    N = int(input())
    if N == 1:
        return 3
    s = str(input())
    s2 = str(input())
    a = []
    past = s[0]
    point = 0
    while point < len(s):
        if s[point] == s[point+1]:
            a.append('y')
            point += 2
        else:
            a.append('x')
            point += 1

        if point == len(s) -1:
            a.append('x')
            break

    ans = 0
    if a[0] == 'x':
        ans = 3
    else:
        ans = 6

    for j in range(1, len(a)):
        if a[j-1] == 'x' and a[j] == 'x':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'x':
            ans *=1 % MOD
        elif a[j-1] == 'x' and a[j] == 'y':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'y':
            ans *=3 % MOD

    return ans % MOD
print(m())

Submission status: Accepted

Solution code:
MOD = 1000000007

def m():
    N = int(input())
    if N == 1:
        return 3
    s = str(input())
    s2 = str(input())
    a = []
    past = s[0]
    point = 0
    while point<len(s):
        if point == N-1:
            a.append('x')
            point+=1
        elif s[point] == s[point+1]:
            a.append('y')
            point+=2
        else:
            a.append('x')
            point+=1

    ans = 0
    if a[0] == 'x':
        ans = 3
    else:
        ans = 6

    for j in range(1, len(a)):
        if a[j-1] == 'x' and a[j] == 'x':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'x':
            ans *=1 % MOD
        elif a[j-1] == 'x' and a[j] == 'y':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'y':
            ans *=3 % MOD

    return ans % MOD

print(m())

Submission status: Accepted

Solution code:
def someone_ans():
    n=int(input())
    a=input()
    b=input()
    c=[]
    i=0
    while i<n:
        if i == n-1:
            c.append(1)
            i+=1
        elif a[i] == a[i+1]:
            c.append(0)
            i +=2
        else:
            c.append(1)
            i+=1

    if c[0] ==0: count=6
    else: count=3
    for i in range(len(c)-1):
        if c[i]==1:count*=2
        elif c[i]==0 and c[i+1]==0: count*=3
    return count % 1000000007

# print(m())
print(someone_ans())

Submission status: Accepted

Solution code:
P=10**9+7
N=int(input())
S1=input()
S2=input()
L=[1]
k=0
P=10**9+7
for i in range(1,N):
    if S1[i]!=S1[i-1]:
        L.append(0)
        k+=1
    L[k]+=1
M=len(L)
S=1
if L[0]==1:
    S=3
else:
    S=6
for i in range(1,M):
    if L[i-1]==1:
        S=(S*2)%P
    else:
        if L[i]==2:
            S=(S*3)%P
print(S)

Submission status: Accepted

Solution code:
def read():
    return int(input())


def readlist():
    return list(map(int, input().split()))


def readmap():
    return map(int, input().split())


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

if S1[0] == S2[0]:
    ans = 3
    same = True
    n = 1
else:
    ans = 6
    same = False
    n = 2

while n < N:
    if S1[n] == S2[n]:
        n += 1
        if same:
            ans = (ans * 2) % MOD
        else:
            same = True
    else:
        n += 2
        if same:
            ans = (ans * 2) % MOD
            same = False
        else:
            ans = (ans * 3) % MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
dominos = []
yokoflag = 0
for u, l in zip(S1, S2):
    if u == l:
        dominos.append(1)
    else:
        if yokoflag == 0:
            yokoflag = 1
            continue
        else:
            dominos.append(2)
            yokoflag = 0
combi = 1
if dominos[0] == 1:
    combi = 3
else: combi = 6
for i in range(1, len(dominos)):
    if dominos[i-1] == 1 and dominos[i] == 1:
        combi *= 2
    elif dominos[i-1] == 1 and dominos[i] == 2:
        combi *= 2
    elif dominos[i-1] == 2 and dominos[i] == 1:
        combi *= 1
    elif dominos[i-1] == 2 and dominos[i] == 2:
        combi *= 3
    combi = combi % 1000000007
print(combi)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
a = []
while(S != ""):
  if len(S) != 1 and S[0] == S[1]:
    a.append(2)
    S = S[2:]
  else:
    a.append(1)
    S = S[1:]
if a[0] == 1:
  ans = 3
else:
  ans = 6
for i in range(0,len(a)-1):
  if a[i] == 1:
    ans *= 2
    ans %= 1000000007
  else:
    if a[i+1] == 2:
      ans *= 3
      ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
i = 0
T = []
while i < N:
    if S1[i]==S2[i]:
        T.append("C")
    else:
        T.append("R")
        i += 1
    i += 1
Ans = 3 if T[0]=="C" else 6
for i in range(1,len(T)):
    if T[i-1] == "C":
        if T[i] == "C":
            Ans *= 2
        else:
            Ans *= 2
    else:
        if T[i] == "C":
            Ans *= 1
        else:
            Ans *= 3
    Ans %= 10**9+7
print(Ans)

Submission status: Accepted

Solution code:
n=int(input())
a=input()
b=input()
c=[]
i=0
while i<n:
    if i==n-1:
        c.append(1)
        i+=1
    elif a[i]==a[i+1]:
        c.append(0)
        i+=2
    else:
        c.append(1)
        i+=1
if c[0]==0: count=6
else: count=3
    
for i in range(len(c)-1):
    if c[i]==1: count*=2
    elif c[i]==0 and c[i+1]==0: count*=3
print(count%1000000007)

Submission status: Accepted

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

cnt=0
stat=0
ans=1
if S1[cnt]==S2[cnt]:
  cnt+=1
  ans*=3
else:
  cnt+=2
  stat=1
  ans*=6

while cnt!=N:
  if stat:
    if S1[cnt]==S2[cnt]:
      stat=0
      cnt+=1
    else:
      ans*=3
      ans%=mod
      cnt+=2
  else:
    if S1[cnt]==S2[cnt]:
      cnt+=1
      ans*=2
      ans%=mod
    else:
      cnt+=2
      ans*=2
      ans%=mod
      stat=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
y = input()
if x[0]==y[0]: num,flag,place = 3,True,1
else: num,flag,place = 6,False,2
while place!=n:
	if flag:
		num = (num*2)%(10**9+7)
		if x[place]!=y[place]:
			flag = False
			place += 2
		else: place+=1
	else:
		if x[place]==y[place]:
			flag = True
			place += 1
		else:
			num = (num*3)%(10**9+7)
			place += 2
print(num)

Submission status: Accepted

Solution code:
N = int(input())
S_1 = input()
S_2 = input()
ans = 1
i = 0
while True:
    if i >= N:
        break
    if i == 0:
        if S_1[i] == S_2[i]:
            ans *= 3
            i += 1
        else:
            ans *= 6
            i += 2
    else:
        if S_1[i-1] == S_2[i-1] and S_1[i] == S_2[i]:
            ans *= 2
            i += 1
        elif S_1[i-1] != S_2[i-1] and S_1[i] == S_2[i]:
            ans *= 1
            i += 1
        elif S_1[i-1] == S_2[i-1] and S_1[i] != S_2[i]:
            ans *= 2
            i += 2
        elif S_1[i-1] != S_2[i-1] and S_1[i] != S_2[i]:
            ans *= 3
            i += 2
    ans = ans % 1000000007
print(ans)

Submission status: Accepted

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

if s1[0] == s2[0]:
    now = True
    ans = 3
    i = 1
else:
    now = False
    ans = 6
    i = 2

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

Submission status: Accepted

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

l=[]
flag=-1
for i in range(N):
	if S1[i]==S2[i]:
		l.append("X")
		flag=0
	else:
		if i==0:
			l.append("Y")
		elif S1[i-1]!=S1[i]:
			l.append("Y")
		else:
			pass

ans=-1
for ind,i in enumerate(l):
	if ind==0:
		if i=="X":
			ans=3
		else:
			ans=6
	else:
		if i=="Y" and l[ind-1]=="X":
			ans*=2
		elif i=="Y" and l[ind-1]=="Y":
			ans*=3
		elif i=="X" and l[ind-1]=="Y":
			ans*=1
		elif i=="X" and l[ind-1]=="X":
			ans*=2

print ans%1000000007

Submission status: Accepted

Solution code:

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


def head(u):
    if u[0] == u[1]:
        return 3
    else:
        return 6

def conn(u, v):
    if u[0] == u[1]:
        """
        AX
        AX

        or

        AX
        AY
        """
        return 2
    else:
        if v[0] == v[1]:
            """
            AX
            BX
            """
            return 1
        else:
            if u[0] == v[0] and u[1] == v[1]:
                """
                AA
                BB
                """
                return 1
            else:
                """
                AY
                BX
                """
                return 3

m = 1
u = None
for v in zip(s, t):
    if u is None:
        m = head(v) 
    else:
        m = (m * conn(u, v)) % 1000000007
    u = v
print(m)

Submission status: Accepted

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

MOD = int(1e9) + 7

tate = "tate"
yoko = "yoko"

i = 0
ans = 0
pre = ""
if s1[i] == s2[i]:
    ans = 3
    i += 1
    pre = tate
else:
    ans = 6
    i += 2
    pre = yoko

while i < N:
    if s1[i] == s2[i]:
        if pre == tate:
            ans *= 2
        elif pre == yoko:
            ans *= 1
        i += 1
        pre = tate
    else:
        if pre == tate:
            ans *= 2
        elif pre == yoko:
            ans *= 3
        i += 2
        pre = yoko
    ans %= MOD
print(ans)

Submission status: Accepted

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

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

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

while i < (N-1):
	if S1[i] == S1[i+1]:
		i += 1
		if prev_flag == 2:
			ans *= 3
		else:
			ans *= 2

		prev_flag = 2

	else:
		if prev_flag == 1:
			ans *= 2

		prev_flag = 1

	i += 1

if i == (N-1) and prev_flag == 1:
	ans *= 2

print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
s1 = input()
s2 = input()
MOD = 1000000007

dp = [0] * (N + 1)
if s1[0] == s2[0]:
    dp[0] = 3
    i = 1
else:
    dp[0] = 6
    i = 2
p1, p2 = s1[0], s2[0]
j = 0
while i < N:
    c1, c2 = s1[i], s2[i]
    if c1 == c2:
        if p1 == p2:
            dp[j+1] = dp[j] * 2 % MOD
        else:
            dp[j+1] = dp[j]
        i += 1
    elif c1 != c2:
        if p1 == p2:
            dp[j+1] = dp[j] * 2 % MOD
        else:
            dp[j+1] = dp[j] * 3 % MOD
        i += 2
    j += 1
    p1, p2 = c1, c2

print(dp[j])

Submission status: Accepted

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

i = 0
ans = 1
MOD = int(1e9) + 7
before = True  # 縦 or 横
while i < N:
    # 縦
    if S1[i] == S2[i]:
        if i == 0:
            ans = 3
        else:
            if before:
                ans *= 2
                ans %= MOD
            else:
                ans *= 1
        before = True
        i += 1
    # 横
    else:
        if i == 0:
            ans = 6
        else:
            if before:
                ans *= 2
            else:
                ans *= 3
                ans %= MOD
        before = False
        i += 2
print(ans)

Submission status: Accepted

Solution code:
YOKO = 0
TATE = 1

MOD = 1000000007

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

if s1[0] == s2[0]:
    state = TATE
    n_pattern = 3
    i = 1
else:
    state = YOKO
    n_pattern = 6
    i = 2

while i < n:
    current = int(s1[i] == s2[i])
    if state == TATE:
        n_pattern *= 2
        if n_pattern >= MOD:
            n_pattern = n_pattern % MOD
    else:
        if current == YOKO:
            n_pattern *= 3
            if n_pattern >= MOD:
                n_pattern = n_pattern % MOD

    state = current
    if state == TATE:
        i += 1
    else:
        i += 2
print(n_pattern % MOD)

Submission status: Accepted

Solution code:
N = int(input())
S_1 = list(input())
S_2 = list(input())



if S_1[0] == S_2[0]:
    res = 3
    flag = 0
    i = 1
else:
    res = 6
    flag = 1
    i = 2

while i != N:
    if S_1[i] == S_2[i]:
        if flag == 0:
            res *= 2 
        else:
            res *= 1
            flag = 0
        i += 1

    else:
        if flag == 0:
            res *= 2
            flag = 1
        else:
            res *= 3
        i += 2
        
ans = res%1000000007

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product, groupby
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10
MOD = 1000000007


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

    pre_is_v = S1[0] == S2[0]
    ans = 3 if pre_is_v else 6
    i = 1 if pre_is_v else 2
    while i < N:
        is_v = S1[i] == S2[i]
        if pre_is_v and not is_v:
            ans = (ans * 2) % MOD
        elif pre_is_v and is_v:
            ans = (ans * 2) % MOD
        elif not pre_is_v and not is_v:
            ans = (ans * 3) % MOD

        pre_is_v = is_v
        i += 1 if is_v else 2

    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
 
result = 3
if N != 1:
    i=1
    while i < N:
        if i==1:
            result *= 2
        elif S1[i-1]==S2[i-1]:
            result *=2
        elif S1[i-1]!=S1[i]:
            if S1[i] != S2[i]:
                result *= 3
        i += 1
 
print(result%1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
"""
#


def solve(line1, line2):
    seq = []
    if len(line1) == 0:
        return 0
    elif len(line1) == 1:
        return 3
    else:
        prev_mark = line1[0]
        for m in line1[1:]:
            if prev_mark is None:
                prev_mark = m
                continue
            if m == prev_mark:
                seq.append('h')
                prev_mark = None
            else:
                seq.append('v')
                prev_mark = m
        if prev_mark:
            seq.append('v')

    if len(seq) == 1:
        return 6
    if seq[0] == 'h':
        ans = 6
        prev_p = 'h'
    else:
        ans = 3
        prev_p = 'v'

    for d in seq[1:]:
        if prev_p == 'h' and d == 'h':
            ans *= 3
            prev_p = 'h'
        elif prev_p == 'h' and d == 'v':
            prev_p = 'v'
        elif prev_p == 'v' and d == 'h':
            ans *= 2
            prev_p = 'h'
        else:
            ans *= 2
            prev_p = 'v'
    return ans % 1000000007




def main():
    n = int(input())
    line1 = input()
    line2 = input()
    result = solve(line1, line2)
    print(result)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 3
left = None
j = 0
while j < N:
    if S1[j] == S2[j]:
        if left == 'V':
            ans *= 2

        left = 'V'
        j += 1
    else:
        if left == 'H':
            ans *= 3
        else:
            ans *= 2
        left = 'H'
        j += 2

print(ans % 1000000007)

Submission status: Accepted

Solution code:
import sys
N = int(raw_input())
row1 = raw_input()
row2 = raw_input()

power2 = 0
power3 = 0
# special handling for 1st column.
if row1[0] == row2[0]:
    power3 += 1
    i = 1
    previous_tate = True
else:
    power2 += 1
    power3 += 1
    i = 2
    previous_tate = False

while i < N:
    if row1[i] == row2[i]:
        # tate
        i += 1
        if previous_tate:
            power2 += 1
        previous_tate = True
    else:
        i += 2
        if not previous_tate:
            power3 += 1
        else:
            power2 += 1
        previous_tate = False
print (pow(2, power2) * pow(3, power3)) % 1000000007

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
mod = 10 ** 9 + 7
table = []
y = 0
for i in range(len(s1)):
    if s1[i] == s2[i]:
        table.append("x")
    else:
        if y == 0:
            table.append("y")
            y += 1
        else:
            y -= 1
if table[0] == "x":
    ans = 3
else:
    ans = 6

for i in range(len(table))[1:]:
    if table[i] == "x":
        if table[i - 1] == "x":
            ans *= 2 % mod
        else:
            pass
    else:
        if table[i - 1] == "x":
            ans *= 2 % mod
        else:
            ans *= 3 % mod
print(ans % mod)

Submission status: Accepted

Solution code:
# 01 -> 3
# 02 -> 6
# 11 -> 2
# 12 -> 2
# 21 -> 1
# 22 -> 3
n=int(input())
s1 = list(input())
s2 = list(input())
s1p="!"
s2p="!"
arr=[]
for i in range(n):
    if s1[i]==s2[i]:
        arr.append(1)
    elif s1[i]==s1p:
        arr.append(2)
    s1p=s1[i]
    s2p=s2[i]
#print(arr)
prv=0
ans=1
for a in arr:
    if prv==0 and a==1:
        ans*=3
        ans%=1000000007
    elif prv==0 and a==2:
        ans*=6
        ans%=1000000007
    elif prv==1:
        ans*=2
        ans%=1000000007
    elif prv==2 and a==2:
        ans*=3
        ans%=1000000007
    prv=a
print(ans)

Submission status: Accepted

Solution code:
def calc_vh(S):
  res = []
  N = len(S)
  pos = 0
  while pos < N:
    if(pos == N-1 or S[pos+1] != S[pos]):
      res.append("v")
      pos += 1
    else:
      res.append("h")
      pos += 2
  return res

N = int(input())
S = input()
S2 = input()

vh = calc_vh(S)
if vh[0]=="v":
  res = 3
else:
  res = 6
length = len(vh)
multiple = {("v", "v"): 2, ("v", "h"): 2, ("h", "v"): 1, ("h", "h"): 3}

for pos in range(1, length):
  v = vh[pos-1], vh[pos]
  res *= multiple[v]

print(res %  1000000007 )

Submission status: Accepted

Solution code:
N = int(input())
S = str(input())
_ = input()

l = []
i = 0

while(i < N):
    if i == N-1:
        l.append(1)
        i += 1
        continue

    if S[i] == S[i + 1]:
        l.append(2)
        i += 2
    else:
        l.append(1)
        i += 1

acc = 1
for j in range(len(l)):
    if j == 0:
        if (l[j] == 1):
            acc *= 3
            continue
        else:
            acc *= 6
            continue

    if l[j-1] == 1:
        acc *= 2
    else:
        if (l[j] == 1):
            acc *= 1
        else:
            acc *= 3

print(acc % 1000000007)

Submission status: Accepted

Solution code:

N = int(input())
S1 = input()
S2 = input()
S1 += "0"
old_shape = ""

if S1[0] == S1[1]:
    ans = 6
    old_shape = "yoko"
    i = 2
else:
    ans = 3
    old_shape = "tate"
    i = 1

while i < N:
    if S1[i] == S1[i+1]:
        if old_shape == "tate":
            ans = (ans*2)%1000000007
            
        else:
            ans = (ans*3)%1000000007
            
        i += 2
        old_shape = "yoko"
    
    else:
        if old_shape == "tate":
            ans = (ans*2)%1000000007
        
        i += 1
        old_shape = "tate"

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
S = S1 + "0"
ans = 3
status = ""
i = 0
while i<N:
    if S[i]==S[i+1]:
        if status == "y":
            ans *= 3
        else:
            ans *= 2
        status = "y"
        i += 2
    else:
        if status == "t":
            ans *= 2
        status = "t"
        i += 1
    ans %= 1000000007
print(ans)

Submission status: Accepted

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

result = 3
if N != 1:
    i=1
    while i < N:
        if S1[i-1] == S2[i-1]:
            result *= 2
        elif S1[i-1] != S1[i]:
            if S1[i] != S2[i]:
                result *= 3
        elif i == 1:
            result *= 2
        i += 1

print(result%1000000007)

Submission status: Accepted

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

if(S1[0]==S2[0]):
    c*=3
    i=1
    t=0
else:
    c*=6
    i=2
    t=1
while i<N:
    if(S1[i]==S2[i]):
        if(t==0):
            c*=2
            t=0
        else:
            c*=1
            t=0
        i+=1
    else:
        if(t==0):
            c*=2
            t=1
        else:
            c*=3
            t=1
        i+=2
print(c%1000000007)

Submission status: Accepted

Solution code:
N=input()
s1=input()+"000"
s2=input()+"000"
ans=3
status=1
place=0
while True:
    if s1[place]=="0":
        break
    if status==1:
        if s1[place]==s2[place]:
            status=3
            place+=1
        else:
            ans=ans*2
            status=2
            place+=2
    elif status==2:
        if s1[place]==s2[place]:
            status=3
            place+=1
        else:
            ans=ans*3
            place+=2
    elif status==3:
        ans=ans*2
        if s1[place]==s2[place]:
            place+=1
        else:
            status=2
            place+=2
print(ans%1000000007)

Submission status: Accepted

Solution code:
n = int(raw_input())
s1 = raw_input()
s2 = raw_input()
used = 0
pat = 1
i = 0
while i < n:
    if s1[i] == s2[i]:
        pat = pat*(3 - used) % (10**9+7)
        used = 1
        i += 1
    else:
        if used == 0:
            pat = pat*6 % (10**9+7)
        else:
            pat = pat*(used + 1) % (10**9+7)
        used = 2
        i += 2
print pat

Submission status: Accepted

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

mod=1000000007
if s1[0]==s2[0]:
    anser=3
    p=1
else:
    anser=6
    p=2

while p<n:
    if s1[p]==s2[p]:
        if s1[p-1]==s2[p-1]:
            anser*=2
        p+=1
    else:
        if s1[p-1]==s2[p-1]:
            anser*=2
        else:
            anser*=3
        p+=2
    anser%=mod
print(anser)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
data = []
i = 0
while i < N:
    try:
        if S1[i] == S1[i + 1]:
            data.append(2)
            i += 2
        else:
            data.append(1)
            i += 1
    except IndexError:
        data.append(1)
        break
ans = 6 if data[0] == 2 else 3
for j in range(len(data[1:])):
    if data[j] == 1:
        ans *= 2
    elif data[j + 1] == 2:
        ans *= 3
    ans %= 1000000007
print(ans)

Submission status: Accepted

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

    mod_ = 1000000007
    n = N
    if S1[0] == S2[0]:
        fill = 3
        i = 1
    else:
        fill = 6
        i = 2

    while i < N:
        if S1[i] == S2[i]:
            if S1[i-1] == S2[i-1]:
                fill *= 2
            i += 1
        else:
            if S1[i-1] == S2[i-1]:
                fill *= 2
            else:
                fill *= 3
            i += 2

    print(fill % mod_)

main()

Submission status: Accepted

Solution code:
def D_Coloring_Dominoes(N, S1, S2):
    from collections import deque
    S1, S2 = deque(S1), deque(S2)

    def decisionBlock(s1, s2):
        # s1,s2の先頭ドミノが縦に1個か横に2個のブロックになっているかを判定
        if s1[0] == s2[0]:
            block = 'X'  # 解説の"X","Y"の決め方を踏襲
            s1.popleft()
            s2.popleft()
        elif s1[0] == s1[1] and s2[0] == s2[1]:
            block = 'Y'
            s1.popleft()
            s1.popleft()
            s2.popleft()
            s2.popleft()
        else:
            tmp = 'NotBlock'  # 入力の制約上ここに来ないはず
        return block

    combination = 0

    # 最左端のブロックの塗り方の組み合わせを算出しておく
    firstblock = decisionBlock(S1, S2)
    if firstblock == 'X':
        combination += 3
    else:
        combination += 6

    # 残りのブロックの塗り方の組み合わせを求める
    leftblock = firstblock
    while S1 != deque([]):
        block = decisionBlock(S1, S2)
        if (leftblock, block) == ('X', 'X'):
            combination *= 2
        elif (leftblock, block) == ('Y', 'X'):
            combination *= 1
        elif (leftblock, block) == ('X', 'Y'):
            combination *= 2
        elif (leftblock, block) == ('Y', 'Y'):
            combination *= 3
        leftblock = block
    return combination%(10**9+7)

N = int(input())
S1 = input()
S2 = input()
print(D_Coloring_Dominoes(N, S1, S2))

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


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


def read_str():
    return input()


M = 10 ** 9 + 7


def main():
    n = read_int()
    a = [read_str(), read_str()]
    res = 1
    last_vertical = None
    i = 0
    while i < n:

        vertical = a[0][i] == a[1][i]
        if i == 0:
            if vertical:
                res = 3
            else:
                res = 6
        else:
            if vertical:
                if last_vertical:
                    res *= 2
            else:
                if last_vertical:
                    res *= 2
                else:
                    res *= 3
        last_vertical = vertical
        if vertical:
            i += 1
        else:
            i += 2
        res %= M
    print(res)


main()

Submission status: Accepted

Solution code:
num=raw_input()
tmp=raw_input()
tmp2=raw_input()
bef="none"
n_state=0
af_state=0
if len(tmp)==1:
    out=3
else:
    if tmp[0]==tmp[1]:
        out=6
        n_state=1
        init=2
    else:
        out=3
        init=1
    #out=3

    for i in range(init,len(tmp)):
        if tmp[i]!=bef:
            #print "aaa"
            if i<int(num)-1:
                if tmp[i]==tmp[i+1]:
                    if n_state==0:
                        out=out*2
                    else:
                        out=out*3
                        n_state=0
                else:
                    if n_state==0:
                        out=out*2
                    else:
                        out=out*1
                        n_state=0
            else:
                if n_state==0:
                    out=out*2
                else:
                    out=out*1
                    n_state=0
        else:
            n_state=1
        bef=tmp[i]
print out % 1000000007