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

print(ans)

Submission status: Accepted

Solution code:
# 横か縦か。各時点でn-2 or n-1C2
# str1だけ見ればよい

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

pattern = []
j = 0

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


    
MOD = 10**9 + 7

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

print(ans)

Submission status: Accepted

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

i = 0
ans = 1
tmp = ''

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

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

            tmp = 'Y'
            i += 2
        

        
print(ans%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

i = 0

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

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


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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


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

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

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

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

print(dp)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

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

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


    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 本番後に自力で回答
#
# 左の列から順に見ていく
#
# 例えば、以下の盤面にて、「CCDD」の部分に何が入るかを考える。
#   AACC
#   BBDD
# AAがa色、BBがb色で塗られているとすると、塗り方は
#   aabb  aacc  aabb
#   bbaa  bbaa  bbcc
# の3通り。なので3をかける

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
mod=1e9+7
n=input()
s1=raw_input()
s2=raw_input()
if s1[0]==s2[0]:
	r=3
	i=1
	prev=True
else:
	assert s1[0]==s1[1]!=s2[0]==s2[1]
	r=6
	i=2
	prev=False
while i<n:
	if s1[i]==s2[i]:
		if prev:
			r=r*2%mod
		i+=1
		prev=True
	else:
		assert s1[i]==s1[i+1]!=s2[i]==s2[i+1]
		if prev:
			r=r*2%mod
		else:
			r=r*3%mod
		i+=2
		prev=False
print int(r)

Submission status: Accepted

Solution code:
from itertools import groupby as gb
N = int(input())
a,b = gb(input()),gb(input())
res = -1
for (w,x),(y,z) in zip(a,b):
    if res==-1:
        prev = w!=y
        res = 3 * (1+prev)
    elif prev:
        prev = w!=y
        res *= 1 + prev*2
    else:
        prev = w!=y
        res *= 2
print(res % (10**9+7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
s1 = input()
s2 = input()

mod = 1000000007

if s1[0]==s2[0]:
    i = 1
    ret = 3
else:
    i=2
    ret = 6

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

Submission status: Accepted

Solution code:
def main():

    S = list(input())
    checklist = [0 for i in range(26)]
    for i in S:
        checklist[ord(i) - ord("a")] += 1
    ans = True

    for i in checklist:
        if i > 1:
            ans = False

    if not ans:
        print(-1)
        return 0
    else:
        ans = False
        for i in range(len(checklist)):
            if checklist[i] == 0:
                for i in S:
                    print(i, end="")
                print(chr(i + ord("a")), end = "")
                print()
                ans = True
                break

        if not ans:
            new_S = []
            for i in S:
                new_S.append(ord(i))

            for i in range(len(new_S) - 1):
                if new_S[i] > new_S[i + 1]:
                    for j in range(i - 1):
                        print(S[j], end = "")
                    print(chr(new_S[i - 1] + 1), end = "")
                    print()
                    ans = True
                    break

            if not ans:
                print(-1)
#main()

def ABC069D():

    H, W = map(int, input().split())
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(N):
        for j in range(a[i]):
            ans.append(i + 1)
    printlist = [[0 for i in range(W)] for j in range(H)]
    k = 0
    for i in range(H):
        for j in range(W):
            printlist[i][j] = ans[k]
            k += 1
        if i % 2 != 0:
            printlist[i] = printlist[i][::-1]

    for i in range(H):
        for j in range(W):
            print(printlist[i][j], end = "")
            if j != W:
                print(" ", end = "")
        print()
    print()
#ABC069D()

import math
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def ABC057D():

    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    v = sorted(v)[::-1]

    anslist = []
    for i in range(A, B + 1):

        anslist.append([sum(v[0:i]) / i, i, v[i - 1]])
    anslist.sort()
    anslist = anslist[::-1]
    ans = anslist[0][0]
    key = anslist[0][2]
    long = anslist[0][1]
    print(ans)
    for i in range(1, len(anslist)):
        if anslist[i][0] == anslist[i - 1][0]:
            ans = anslist[i][0]
            key = anslist[i][2]
            long = anslist[i][1]
        else:
            break
    #print(anslist)
    #print(ans, key, long)
    cnt = 0
    for i in v:
        if i == key:
            cnt += 1

    c = 0
    for i in v[:long]:
        #print(i)
        if i == key:
            c += 1
    #print(c, long)
    ans = 0
    if c == long:
        for i in range(A,  min(B + 1, cnt + 1)):
            ans += cc(cnt, i)
    else:
        ans = cc(cnt, c)
    #print(anslist)
    #print(cnt, c, long)
    print(ans)
#ABC057D()

def ABC104D():
    S = list(input())
    A_cnt = 0
    B_cnt = 0
    C_cnt = 0
    Q_cnt = 0
    ans = 0
    for i in S:
        if i == "A":
            A_cnt += 1
        elif i == "B":
            B_cnt += 1
        elif i == "C":
            C_cnt += 1
        else:
            Q_cnt += 1
    for i in range(Q_cnt + 1):
        for j in range(Q_cnt - i + 1):
            k = Q_cnt - i - j
            if A_cnt + i > 0 and B_cnt + j > 0 and C_cnt + k > 0:
                f_i = math.factorial(i)
                f_j = math.factorial(j)
                f_k = math.factorial(k)
                if f_i == 0:
                    f_i = 1
                if f_j == 0:
                    f_j = 1
                if f_k == 0:
                    f_k = 1
                ans += (A_cnt + i) * (B_cnt + j) * (C_cnt + k) * math.factorial(Q_cnt) // f_i // f_j // f_k
                print(ans, i, j, k, A_cnt + i, B_cnt + j, C_cnt + k)
                print(math.factorial(Q_cnt), f_i, f_j, f_k)
    print(ans)
#ABC104D()

def ARC075():
    N, A, B = map(int, input().split())
    h = [int(input()) for i in range(N)]
    def enogth(T):
        import copy
        this_h = copy.copy(h)
        cnt = 0
        for i in range(N):
            this_h[i] -= B
            key = 0
            if this_h[i] > 0:
                key = this_h[i] / (A - B)
                if int(key) != key:
                    key += 1
                cnt += int(key)
        if cnt <= T:
            return True
        else:
            return False
    def sarch(i: object) -> object:
        print(i)
        if enogth(i):
            if i // 2 == 1:
                return i
            sarch(0 + i // 2)
        else:
            sarch(i + i // 2)
    print(sarch(10 ** 9))
#ARC075()

def ARC082D():
    N = int(input())
    p = list(map(int, input().split()))
    cnt = 0
    if p[N - 1] == N:
        #print(p[N - 1], N)
        p[-2], p[-1] = p[-1], p[-2]
        cnt += 1

    for i in range(N - 1):
        if p[i] == i + 1:
            p[i], p[i + 1] = p[i + 1], p[i]
            cnt += 1
    print(cnt)
#ARC082D()

from queue import Queue
def ABC070D():
    N = int(input())
    a, b, c =map(int, input().split())
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    x = [[] for i in range(N)]
    for i, j in xy:
        x[i - 1].append(j - 1)
        x[j - 1].append(i - 1)

    q = Queue()
    visited = [0 for i in range(N)]

def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    print(speed_lim)
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 1
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 1, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans)
#ABC076D()

def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    a = []
    for i in t:
        a.append(i * 2)
    t = a
    v = list(map(int, input().split()))
    #print(t)
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    #print(speed_lim, len(speed_list), len(speed_lim))
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 0.5
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    #print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 0.5, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    #print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans / 2)
#ABC076D()

def ABC085D():
    N, H = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    a = []
    b = []
    for i, j in ab:
        a.append(i)
        b.append(j)
    a.sort()
    b.sort()
    a = a[::-1]
    b = b[::-1]
    damage = 0
    cnt = 0
    for i in b:
        if i < a[0]:
            break
        damage += i
        cnt += 1
        if damage >= H:
            break
    key = 0
    if damage < H:
        key = (H - damage) / a[0]
        if int(key) != key:
            key += 1
        key = int(key)

    cnt += key

    print(cnt)
#ABC085D()

def ARC068D():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    count_list = []
    cnt = 1
    #print(A)
    for i in range(1, N):
        if A[i] == A[i - 1]:
            cnt += 1
        else:
            count_list.append(cnt)
            cnt = 1
    count_list.append(cnt)
    ans_cnt = 0
    #print(count_list)
    for i in range(len(count_list)):
        if count_list[i] > 2:
            ans_cnt += (count_list[i] % 2) - 1
            count_list[i] %= 2
            if count_list[i] == 0:
                count_list[i] = 2
    #print(ans_cnt)
    count_list = sorted(count_list)[::-1]
    for i in range(len(count_list) - 1):
        if count_list[i] == 2 and count_list[i + 1] == 2:
            ans_cnt += 1
            count_list[i] = 1
            count_list[i + 1] = 1
    count_list = sorted(count_list)[::-1]
    if count_list[0] == 2:
        count_list[0] = 0
    #print(ans_cnt)
    #print(count_list)
    print(sum(count_list))
#ARC068D()

def ARC073D():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]
    wv.sort()
    count_list = []
    cnt = 1
    weight_list = []
    s = 0
    g = 0
    for i in range(N - 1):
        if wv[i][0] != wv[i + 1][0]:
            g = i
            count_list.append(cnt)
            weight_list.append([wv[i][0], s, g, cnt])
            s = i + 1
            g = i + 1
            cnt = 1
        else:
            g = i
            cnt += 1

    count_list.append(cnt)
    weight_list.append([wv[-1][0], s, g, cnt])
    print(weight_list)
    wl = []
    for i in weight_list:
        this_weight = i[0]
        this_list = []
        for j in wv[i[1]:i[2] + 1]:
            this_list.append(j[1])
        this_list = sorted(this_list)[::-1]
        print(this_list)
        wl.append([this_weight, this_list])

def ARC081D():
    pattern = []
    N = int(input())
    S1 = list(input())
    S2 = list(input())
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            pattern.append("X")
        else:
            pattern.append("Y")
            i += 1
        i += 1
    ans_list = []
    for i in range(len(pattern)):
        if i == 0:
            if pattern[i] == "X":
                ans_list.append(3)
            else:
                ans_list.append(6)
        else:
            if pattern[i] == "X":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                else:
                    ans_list.append(1)
            elif pattern[i] == "Y":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                elif pattern[i - 1] == "Y":
                    ans_list.append(3)
    #print(pattern)
    #print(ans_list)
    ans = 1
    for i in ans_list:
        ans *= i
    print(ans % (1000000007))
ARC081D()

Submission status: Accepted

Solution code:
n = int(input())
list_s1 = list(str(input()))
ans = 1
list_s1.append("!")
for i in range(n):
    if i == 0:
        ans *= 3
    elif i == 1:
        ans *= 2
    else:
        if list_s1[i] == list_s1[i-1]:
            ans *= 1
        else:
            if list_s1[i-1] == list_s1[i-2]:
                if list_s1[i] != list_s1[i+1]:
                    ans *= 1
                else:
                    ans *= 3
            else:
                ans *= 2
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
s1 = input()
s2 = input()
i = 0
pat = []
while i < N:
  if s1[i]==s2[i]:
    pat.append('t')
    i += 1
  else:
    pat.append('y')
    i += 2
if pat[0]=='t':
  ans = 3
else:
  ans = 6
pat2 = pat[1:]
l = len(pat)
i = 1
while i < l:
  if pat[i]=='t' and pat[i-1]=='t':
    ans = (ans*2)%(10**9+7)
  elif pat[i]=='t' and pat[i-1]=='y':
    pass
  elif pat[i]=='y' and pat[i-1]=='t':
    ans = (ans*2)%(10**9+7)
  elif pat[i]=='y' and pat[i-1]=='y':
    ans = (ans*3)%(10**9+7)
  i += 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
s1 = input()
s2 = input()
if s1[0] == s2[0]:
    i = 1
    ans = 3
else:
    i = 2
    ans = 6
while i < N:
    if s1[i] == s2[i]:
        if s1[i - 1] == s2[i - 1]:
            ans *= 2
        i += 1
    else:
        if s1[i - 1] == s2[i - 1]:  # 左が縦
            ans *= 2
        else:
            ans *= 3
        i += 2
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = input()
b = input()

ans = 3
i = 0
if a[0] != b[0]:
    i += 1
    ans += 3

while i < n-1:
    if a[i]==b[i]:
        if a[i+1]==b[i+1]:
            ans *= 2
        else:
            ans *= 2
            i += 1
    else:
        if a[i+1]==b[i+1]:
            ans *= 1
        else:
            ans *= 3
            i += 1
    i += 1
    ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

MOD = 1000000007

N = read()
S = input()
T = input()

ans = 1

i = 0
prev = 0

M1 = {0:3, 1:2, 2:1}
M2 = {0:6, 1:2, 2:3}
while i < N:
  if S[i] == T[i]:
    ans = ans * M1[prev] % MOD
    prev = 1
    i += 1
  else:
    ans = ans * M2[prev] % MOD
    prev = 2
    i += 2

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def main():
    n, s1, s2 = int(input()), input(), input()

    com, idx = 1, 0
    while idx < n:
        if idx == 0:
            if s1[idx] == s2[idx]:
                com *= 3
                idx += 1
            else:
                com *= 6
                idx += 2

        elif s1[idx] == s2[idx]:
            if s1[idx-1] == s2[idx-1]:
                com = com * 2 % MOD
            idx += 1
        else:
            if s1[idx-1] == s2[idx-1]:
                com = com * 2 % MOD
            else:
                com = com * 3 % MOD
            idx += 2

    print(com)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if s1[0]==s2[0]:
    ass = 3
    i = 0
else:
    ass = 6
    i = 1
    
while i <= n-2:
    if s1[i]==s2[i]:
        if s1[i+1]==s2[i+1]:
            ass = ass*2
            if ass >= 1000000007:
                ass = ass%1000000007
            i = i+1
        else:
            ass = ass*2
            if ass >= 1000000007:
                ass = ass%1000000007
            i = i+2
    else:
        if s1[i+1]==s2[i+1]:
            ass = ass
            if ass >= 1000000007:
                ass = ass%1000000007
            i = i+1
        else:
            ass = ass*3
            if ass >= 1000000007:
                ass = ass%1000000007
            i = i+2
print(ass)

Submission status: Accepted

Solution code:
n = int(input())

s = raw_input()

arr = []

i = 0
while i < n:
	if i == n-1:
		arr.append('y')
		break

	if s[i] == s[i+1] :
		arr.append('x')
		i += 2

	else :
		arr.append('y')
		i += 1

ans = 3 if arr[0] == 'y' else 6

for i in range(1,len(arr)):
	if arr[i-1] == 'y' and arr[i] == 'y': 
		ans *= 2

	elif arr[i-1] == 'y' and arr[i] == 'x':
		ans *= 2

	elif arr[i-1] == 'x' and arr[i] == 'y':
		ans *= 1

	else :
		ans *= 3
print ans % (10**9 + 7)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7


def main():
    n = int(input())
    s1, s2 = input(), input()

    com = 1
    i, j = 0, 0
    while i < n or j < n:
        if i <= j:
            if s1[i] == s2[j]:
                if i == 0:
                    com = com * 3 % M
                elif s1[i-1] == s2[j-1]:
                    com = com * 2 % M
                i += 1
                j += 1
            else:
                if i == 0:
                    com = com * 3 % M
                else:
                    com = com * 2 % M
                i += 2

        else:
            if j == 0:
                com = com * 2 % M
            elif s1[i-3] != s2[j-1]:
                com *= 1.5
            j += 2

    print(int(com) % M)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

i=0

ans=1

prev=-2

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

elif(i+1<N):

	if(s1[i]==s1[i+1]):
		ans*=6
		i+=2
		prev=1

	else:
		ans*=3
		i+=1
		prev=2


	while(i<N):
	
		if(i+1<N):

			if(prev==1 and s1[i]==s1[i+1]):

				ans*=3
				i+=2
				prev=1

			elif(prev==2 and s1[i]==s1[i+1]):

				ans*=2
				i+=2
				prev=1

			elif(prev==1):

				i+=1
				prev=2

			elif(prev==2):

				ans*=2
				i+=1
				prev=2

		elif(i<N):

			if(prev==1):

				i+=1
				prev=2

			elif(prev==2):

				ans*=2
				i+=1
				prev=2	
			
			
	print(ans%1000000007)

Submission status: Accepted

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

if s1[0]==s2[0]:
	flag=0
	i=1
	ans=3
else:
	flag=1
	i=2
	ans=6	
while i<n:
	if s1[i]==s2[i]:
		if flag==0:
			ans=((ans%p)*2)%p
		else:
			ans = ans%p
		flag=0
		i+=1	
	else:	
		if flag==0:
			ans=((ans%p)*2)%p
		else:
			ans=((ans%p)*3)%p
		flag=1
		i+=2	
print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

# make XYline
xy = ""
for i in range(len(S[0])):
    if S[0][i] == S[1][i]:
        xy += "X"
    elif i==len(S[0])-1:
        break
    elif S[0][i] == S[0][i+1]:
        xy += "Y"

# proceed
if xy[0] == "X":
    ans = 3
else:
    ans = 6

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

        ans = ans%MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
MOD = 10**9+7
ans = 1
prev = None
for c1,c2 in zip(S1,S2):
    if (c1,c2) == prev: continue
    if prev:
        if prev[0] == prev[1]:
            ans *= 2
        else:
            if c1 != c2:
                ans *= 3
    else:
        if c1 == c2:
            ans = 3
        else:
            ans = 6
    prev = (c1,c2)
print(ans % MOD)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
T=input()
mod=1000000007
if S[0]==T[0]:
    ans=3
    p=0
    i=1
else:
    ans=6
    p=1
    i=2
while i<N:
    if S[i]==T[i] and p==0:
        ans = (ans*2)%mod
        i+=1
        p=0
    elif S[i]==T[i] and p==1:
        #ans = (ans*2)%mod
        i+=1
        p=0
    elif S[i]!=T[i] and p==0:
        ans = (ans*2)%mod
        i+=2
        p=1
    elif S[i]!=T[i] and p==1:
        ans = (ans*3)%mod
        i+=2
        p=1  
print(ans)