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())
s = [input() for _ in range(2)]
ans = 1
pre_vertical = False
start = 1
flag = False
if s[0][0] == s[1][0]:
    pre_vertical = True
    ans *= 3
else:
    start = 2
    ans *= 6
for i in range(start, n):
    if flag:
        flag = False
        continue
    if s[0][i] == s[1][i]:
        if pre_vertical:
            ans *= 2
        else:
            ans *= 1
        pre_vertical = True
    else:
        if pre_vertical:
            ans *= 2
        else:
            ans *= 3
        pre_vertical = False
        flag = True
    ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
mod = int(1e9+7)
N = int(input())
S1 = input()
S2 = input()

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

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

print(ans)

Submission status: Accepted

Solution code:
#ABC071 D - Coloring Dominoes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=int(input())
s1=list(input())
s2=list(input())
i=0
mod=1000000007
 
ans=0
p=0
while i<n:
    if s1[i]==s2[i]:
        # 今回パターン1
        if p==0:
            ans=3
        elif p==1:
            ans*=2
            ans=ans%mod
        elif p==2:
            ans*=1
            ans=ans%mod
        i+=1
        p=1
    else:
        # 今回パターン2
        if p==0:
            ans=6
        elif p==1:
            ans*=2
            ans=ans%mod
        elif p==2:
            ans*=3
            ans=ans%mod
        i+=2
        p=2
print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007
N = int(input())
S1 = input()
S2 = input()
if S1[0] == S2[0]:
    ans = 3
    p = 1
    i = 1
else:
    ans = 6
    p = 0
    i = 2

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = [input() for i in range(2)]
prev = 0 #0:横 1:縦
if s[0][0] == s[1][0]:
    res = 3
    i = 1
    prev = 1
else:
    res = 6
    i = 2
while i < n:
    if s[0][i] == s[1][i]:
        if prev:
            res = (res*2) % mod
        i += 1
        prev = 1
    else:
        if prev:
            res = (res*2) % mod
        else:
            res = (res*3) % mod
        i += 2
        prev = 0
print(res)

Submission status: Accepted

Solution code:
n=int(input())
s1=input()
s2=input()
x=[]
f=0
for i in range(n):
    if f==1:
        f=0
    else:
        if s1[i]==s2[i]:
            x.append(0)
        else:
            x.append(1)
            f=1
l=len(x)
#print(x)
if l==1:
    if x[0]==0:
        print(3)
    else:
        print(6)
else:
    if x[0]==0:
        c=3
    else:
        c=6
    for i in range(1,l):
        #print(c)
        if x[i-1]==0:
            c*=2
        else:
            if x[i]==1:
                c*=3
        c%=1000000007

    print(c%1000000007)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
S, _ = input()+'_', input()

A = []

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

p = A[0]
ans = 3 if p==1 else 6
mod = 10**9+7
for a in A[1:]:
    d = 2 if p==1 else (1 if a==1 else 3)
    ans = (ans*d)%mod
    p = a

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
DIV=1000000007
ans=1
import itertools
wasTate=True
first=True
for key,g in itertools.groupby(S):
  if len(list(g))==1:
    # 縦の場合
    if first:
      # 最初は3通り選べる
      ans=((ans%DIV)*3)%DIV
      first=False
    elif wasTate:
      # ここまで縦だった場合は2通り選べる
      ans=((ans%DIV)*2)%DIV
      wasTate=True
    else:
      # ここまで横だった場合は1通りしかない
      wasTate=True
  else:
    # 横の場合
    if first:
      ans=((ans%DIV)*6)%DIV
      # 最初は6通り選べる
      # 11 11 22 22 33 33
      # 22 33 11 33 11 22
      first=False
      wasTate=False
    elif wasTate:
      # ここまで縦だった場合は2通り選べる
      ans=((ans%DIV)*2)%DIV
      wasTate=False
    else:
      # ここまで横だった場合は3通り選べる
      # 1122 1122 1133
      # 2211 2233 2211
      ans=((ans%DIV)*3)%DIV
      wasTate=False
      
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n = int(input())
    s1 = input()
    s2 = input()
    if s1[0] == s2[0]:
        ans = 3
        pre = 0
        i = 1
    else:
        ans = 6
        pre = 1
        i = 2
    while i < n:
        if s1[i] == s2[i]:
            if pre == 0:
                ans *= 2
            pre = 0
            i += 1
        else:
            if pre == 0:
                ans *= 2
            else:
                ans *= 3
            pre = 1
            i += 2
        ans %= md
    print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())
S1 = list(input())
S2 = list(input())
ans = 1
MOD = 1000000007
flag_1 = False

if S1[0] == S2[0]:
    ans *= 3
    flag = 'X'
else:
    ans *= 6
    flag = 'Y'

for i in range(1,N):
    if i == 1 and flag == 'Y':
        continue
    if flag_1:
        flag_1 = False
        continue
    if S1[i] == S2[i]:
        if flag == 'X':
            ans *= 2
        else:
            flag = 'X'
    else:
        if flag == 'X':
            ans *= 2
            flag = 'Y'
        else:
            ans *= 3
        flag_1 = True
    ans %= MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, S: "List[str]"):
    """
    0は縦に入っている1は横に入っていることを表す
    """
    dominos = []
    i = 0
    while i < N:
        if S[0][i] == S[1][i]:
            dominos.append(0)
        else:
            dominos.append(1)
            i += 1
        i += 1

    answer = 3 if dominos[0] == 0 else 6
    for i in range(1,len(dominos)):
        if dominos[i] == 0 and dominos[i-1] == 0:
            answer *= 2
        elif dominos[i] == 1 and dominos[i-1] == 0:
            answer *= 2
        elif dominos[i] == 0 and dominos[i-1] == 1:
            answer *= 1
        elif dominos[i] == 1 and dominos[i-1] == 1:
            answer *= 3
        answer %= MOD
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(2)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
T = input()
ans = 3 if S[0] == T[0] else 6
for i in range(1, N):
    if S[i-1] == T[i-1]:
        ans *= 2
    elif S[i] == S[i-1]:
        pass
    else:
        ans *= 1 if S[i] == T[i] else 3
print(ans % (10**9+7))

Submission status: Accepted

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

ans = 1
prev = 0
i = 0
while i < len(s1):
    if s1[i] == s2[i]:
        ans *= (3 - prev)
        prev = 1
        i += 1
    else:
        if prev == 0:
            ans *= 6
        elif prev == 1:
            ans *= 2
        else:
            ans *= 3
        prev = 2
        i += 2
    ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
s = SRL(2)
i = 0
ans = 1
while i < n:
    if s[0][i] == s[1][i]:
        if i == 0: ans *= 3
        elif s[0][i - 1] == s[1][i - 1]:
            ans *= 2
        i += 1
    else:
        if i == 0: ans *= 6
        elif s[0][i - 1] == s[1][i - 1]:
            ans *= 2
        else:
            ans *= 3
        i += 2
    ans %= mod


print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[list(input()) for _ in range(2)]
    ans=1
    i=0
    while(i<n):
        # 縦に置かれているとき
        if(A[0][i]==A[1][i]):
            if(i==0): ans*=3
            elif(A[0][i-1]==A[1][i-1]): ans*=2
            else: pass
            i+=1
        # 横に置かれているとき
        else:
            if(i==0): ans*=6
            elif(A[0][i-1]==A[1][i-1]): ans*=2
            else: ans*=3
            i+=2

    print(ans%MOD)
resolve()

Submission status: Accepted

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

mod = 1000000007

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

Submission status: Accepted

Solution code:
N = int(input())
s12 = [list(input()), list(input())]
index = 0
left_block = None
point_dict = {"X": {"X": 2, "Y": 1}, "Y": {"X": 2, "Y": 3}}
point = 1
n3 = 0
n2 = 0
n1 = 0
while True:
    if index >= N:
        break
    if left_block:
        if s12[0][index] == s12[1][index]:
            now_block = "X"
            index += 1
        else:
            now_block = "Y"
            index += 2
        point *= point_dict[now_block][left_block]
        left_block = now_block
    else:
        if s12[0][0] == s12[1][0]:
            left_block = "X"
            index += 1
            point *= 3
        else:
            left_block = "Y"
            index += 2
            point *= 6

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

Submission status: Accepted

Solution code:
N = int(input())
grids = [[s for s in input()],[s for s in input()]]
MOD = 1000000007

if grids[0][0] == grids[1][0]:
  prv_row_type = 1
  ans = 3
  posx = 1
else:
  prv_row_type = -1
  ans = 6
  posx = 2

while posx < N:
  if grids[0][posx] ==  grids[1][posx]:
    if prv_row_type == 1: ans  *= 2
    else: ans *= 1
    prv_row_type = 1
    posx += 1
  else:
    if prv_row_type == 1: ans *= 2
    else: ans *= 3
    prv_row_type = -1
    posx += 2

print(ans%MOD)

Submission status: Accepted

Solution code:
N = int(input())
s1 = input()
s2 = input()
p = 0
n = 0
ans = 1
while n < N:
    if p == 1:
        if s1[n] == s2[n]:
            ans *= 2
            n += 1
        else:
            ans *= 2
            n += 2
            p = 2
    elif p == 2:
        if s1[n] == s2[n]:
            # ans *= 1
            n += 1
            p = 1
        else:
            ans *= 3
            n += 2
    else:
        if s1[n] == s2[n]:
            ans *= 3
            n += 1
            p = 1
        else:
            ans *= 6
            n += 2
            p = 2
    ans %= 1000000007
    # print(n, ans)
print(ans)

Submission status: Accepted

Solution code:
#71d
N = int(input())
Sone = list(input())
Stwo = list(input())

mod_by = 7 + 10**9

#最初のだけ別計算
if Sone[0]==Stwo[0]:
    #ドミノは縦置き
    ans = 3
    before_domino = 1
    i = 1
else:
    #ドミノは横置き
    ans = 6 # 3色*3色-3通り(上下同色)
    before_domino = 0
    i = 2

#前のドミノが縦置き(before_domino=1)の場合
#→今のドミノが縦置きなら2通り
#→今のドミノが横置きなら2通り

#前のドミノが横置き(before_domino=0)の場合
#→今のドミノが縦置きなら1通り
#→今のドミノが横置きなら3通り
    
while i < N:
    if Sone[i] == Stwo[i] and before_domino == 1:
        ans *= 2
        before_domino = 1
        i += 1
    elif Sone[i] != Stwo[i] and before_domino == 1:
        ans *= 2
        before_domino = 0
        i += 2
    elif Sone[i] == Stwo[i] and before_domino == 0:
        ans *= 1
        before_domino = 1
        i += 1
    elif Sone[i] != Stwo[i] and before_domino == 0:
        ans *= 3
        before_domino = 0
        i += 2
        
print(ans%mod_by)

Submission status: Accepted

Solution code:
N = int(input())
S1 = list(input())
S2 = list(input())
cnt= 0
ans = 0
flag= 0
while cnt<N:
  if S1[cnt]==S2[cnt]:
    if cnt==0:
      ans+=3
    elif flag==1:
      ans*=2
    elif flag==2:
      ans*=1
    flag=1
    cnt+=1
  elif S1[cnt]!=S2[cnt]:
    if cnt==0:
      ans +=6
    elif flag==1:
      ans*=2
    elif flag==2:
      ans*=3
    flag=2
    cnt+=2
  ans %=(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
t=list(input())
mod=10**9+7
ans=0
if s[0]==t[0]:
    ans=3
else:
    ans=6
for i in range(1,n):
    if s[i]!=s[i-1]:
        if s[i-1]==t[i-1]:
            ans=ans*2%mod
        else:
            if s[i]!=t[i]:
                ans=ans*3%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
cur = 0
ans = []; S = [[] for _ in range(2)]
for i in range(2):
    S[i] = str(input())
#print(S[0][0])
C = []
i = int(0)
while i<=N-1:
    if S[0][i]==S[1][i]:
        C.append(0)
        i +=1
    else:
        C.append(1)
        i +=2
#print(C)
cur = int(1)
for i in range(len(C)):
    if i==0:
        if C[i]==0:
            cur *= 3
        else:
            cur *= 6
    else:
        if not (C[i-1]==1 and C[i]==0):
            if (C[i-1]==1 and C[i]==1):
                cur *=3
            else:
                cur *= 2

ans = cur%mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s1 = input()
s2 = input()

INF = 1000000007

left = None
index = 0
cnt = 0
while index < n:
    # 右側が縦テトリス1つ
    if s1[index] == s2[index]:
        index += 1
        if left is None:
            left = 1
            cnt = 3
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 1
        left = 1

    # 右側が横テトリス2つ
    else:
        index += 2
        if left is None:
            left = 2
            cnt = 6
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 3
        left = 2
    cnt = cnt % INF
print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s1 = str(input().rstrip('\n'))
    s2 = str(input().rstrip('\n'))
    cur = 0
    cnt = 1
    f = True
    lv = True
    while cur < n:
        if s1[cur] == s2[cur]:
            #縦の場合
            if f:
                cnt = (cnt * 3) % mod
                f = False
            else:
                if lv:
                    cnt = (cnt * 2) % mod
                else:
                    cnt = (cnt * 1) % mod
            cur += 1
            lv = True
        elif s1[cur] == s1[cur+1] and s2[cur] == s2[cur+1]:
            #横の場合
            if f:
                cnt = (cnt * 6) % mod
                f = False
            else:
                if lv:
                    cnt = (cnt * 2) % mod
                else:
                    cnt = (cnt * 3) % mod
            cur += 2
            lv = False
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

if S1[0] == S2[0]:
    ans = 3
    tmp = True #直前が縦
    j = 1 #次に見始めるところ
else:
    ans = 6
    tmp = False
    j = 2

while j < N:
    if S1[j] == S2[j]: #縦に並んでいる時
        if tmp: #縦が連続の時
            ans *= 2
        else: #直前が横
            ans *= 1
        tmp = True
        j += 1
    else: #横に並んでいる時
        if tmp: #縦-->横のとき
            ans *= 2
        else: #横が連続の時
            ans *= 3
        tmp = False
        j += 2
    ans %= MOD

print (ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
v=[0]
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: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, S: "List[str]"):
    S1, S2 = S
    prev = 0
    counter = 1
    i = 0
    while i<N:
        if S1[i] == S2[i]:
            if prev == 0:
                counter *= 3
            elif prev == 1:
                counter *= 2
            prev = 1
            i += 1
        else:
            if i > 0:
                if S1[i-1] == S1[i] and S2[i-1] == S2[i-1]:
                    i += 1
                    prev = 2
                    continue
            if prev == 0:
                counter *= 6
            elif prev == 1:
                counter *= 2
            elif prev == 2:
                counter *= 3
            prev = 2
            i += 1
        counter %= MOD
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(2)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, S: "List[str]"):
    S1, S2 = S
    prev = 0
    counter = 1
    i = 0
    while i<N:
        if S1[i] == S2[i]:
            if prev == 0:
                counter *= 3
            elif prev == 1:
                counter *= 2
            prev = 1
            i += 1
        else:
            if i > 0:
                if S1[i-1] == S1[i] and S2[i-1] == S2[i-1]:
                    i += 1
                    continue
            if prev == 0:
                counter *= 6
            elif prev == 1:
                counter *= 2
            elif prev == 2:
                counter *= 3
            prev = 2
            i += 1
        counter %= MOD
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(2)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=1000000007
if n==1:
  ans=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: Accepted

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

if N == 1:
    answer = 3
elif N == 2:
    answer = 6
else:
    answer = 6
    for i in range(2, N):
        if s1[i] == s2[i]:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            else:
                pass
        else:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            elif s1[i - 1] != s1[i]:
                answer = answer * 3 % mod
            else:
                pass

print(answer)

Submission status: Accepted

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

if s1[0] == s2[0]:
  result = 3
  last_pattern = "h"
  place = 1
else:
  result = 6
  last_pattern = "w"
  place = 2
while place < n:
  if last_pattern == "h":
    if s1[place] == s2[place]:
      result *= 2
      last_pattern = "h"
      place += 1
    else:
      result *= 2
      last_pattern = "w"
      place += 2
  else:
    if s1[place] == s2[place]:
      last_pattern = "h"
      place += 1
    else:
      result *= 3
      last_pattern = "w"
      place += 2
print(result % (7 + 10**9))

Submission status: Accepted

Solution code:
n,s,t=open(0)
a=3
for i in range(1,int(n)):
 if i<2or s[i-1]==t[i-1]:a*=2
 elif s[i-1]!=s[i]!=t[i]:a*=3
print(a%(10**9+7))

Submission status: Accepted

Solution code:
from itertools import*
_,*s=open(0)
s=[a[0]!=b[0]for a,b in zip(*map(groupby,s))]
c=3*2**s[0]
for a,b in zip(s,s[1:-1]):c=c*(a+2if b else(1^a)+1)%(10**9+7)
print(c)

Submission status: Accepted

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

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

ans = 0
for i in range(len(Data)):
    if i == 0:
        if Data[i] == 1:
            ans = 3
        else:
            ans = 6
    else:
        if Data[i] == 1:
            if Data[i-1] == 1:
                ans = (ans * 2) % MOD
            else:
                pass 
        else:
            if Data[i-1] == 1:
                ans = (ans * 2) % MOD
            else:
                ans = (ans * 3) % MOD
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())
S = list(input()) + [None]

ans = 1
i = 0
prev = None

while i < n:
    if S[i]==S[i+1]:
        if prev == None:
            ans *= 6
        elif prev == 0:
            ans *= 3
        else:
            ans *= 2
        prev = 0
        i += 2
    else:
        if prev == None:
            ans *= 3
        elif prev == 0:
            ans *= 1
        elif prev == 1:
            ans *= 2
        prev = 1
        i += 1
        
print(ans%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(input())
b=list(input())
ans=1
i=0
f=0
mod=1000000007
while i!=n:
    if i==0:
        if a[i]==b[i]:
            i+=1
            ans*=3
            ans%=mod
            f=1
        else:
            i+=2
            ans*=6
            ans%=mod
            f=2
    else:
        if a[i]==b[i] and f==1:
            i+=1
            ans*=2
            ans%=mod
            f=1
        elif a[i]==b[i] and f==2:
            i+=1
            f=1
        elif a[i]!=b[i] and f==1:
            i+=2
            ans*=2
            ans%=mod
            f=2
        else:
            i+=2
            ans*=3
            ans%=mod
            f=2
print(ans%mod)

Submission status: Accepted

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

if s1[0]==s2[0]: res = 3
else: res = 6

for i in range(1,n):
    if s1[i-1] != s1[i]:
        if s1[i-1] != s2[i-1]:
            if s1[i] != s2[i]: res *= 3
        else: res *= 2

print(res % mod)

Submission status: Accepted

Solution code:
n = int(input())
s1=input()
s2=input()
mod = 10**9+7
l = []
for i in range(0,n-1):
    if s1[i] != s1[i+1]:
        if s1[i] != s2[i]:
            l.append(0)
        else:
            l.append(1)
if s1[n-1]==s2[n-1]:
    l.append(1)
else:
    l.append(0)
if l[0]:
    res = 3
else:
    res = 6

for i in range(1,len(l)):
    if l[i-1] and l[i]:
        res *= 2
    elif l[i-1] and  not l[i]:
        res *= 2
    elif not l[i-1] and not l[i]:
        res *= 3

print(res % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
s="1"+input()
a=[]
for i in range(n):
  if s[i]!=s[i+1]:a+=[1]
  else:a[-1]+=1
x=3*a[0]
for i in range(1,len(a)):
  if a[i-1]==a[i]==1:x*=2
  elif a[i-1]==a[i]==2:x*=3
  elif a[i]==1:x*=1
  else:x*=2
  x%=10**9+7
print(x)

Submission status: Accepted

Solution code:
N=int(input())

A=[[0]*2 for i in range(N)]

for i,x in enumerate(input()):
	A[i][0]=ord(x)
for i,x in enumerate(input()):
	A[i][1]=ord(x)

t=[]
f=True
for x,y in A:
	if f:
		if x==y:
			t.append(0)
		else:
			t.append(1)
			f=False
	else:
		f=True

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


for i in range(1,len(t)):
	if t[i-1]==t[i]==0:
		ans=(ans*2)%(1000000007)
	elif t[i-1]==0 and t[i]==1:
		ans=(ans*2)%(1000000007)
	elif t[i-1]==1 and t[i]==1:
		ans=(ans*3)%(1000000007)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=str(input())
t=str(input())
listed=[]
cnt=0
while cnt<=n-1:
    if s[cnt]==t[cnt]:
        cnt+=1
        listed.append("T")
    elif s[cnt]==s[cnt+1] and t[cnt]==t[cnt+1]:
        cnt+=2
        listed.append("Y")

length=len(listed)
if listed[0]=="T":
    ans=3
elif listed[0]=="Y":
    ans=6
for i in range(0,length-1):
    
    if listed[i]=="Y" and listed[i+1]=="Y":
        ans=ans*3%(10**9+7)
    
    if listed[i]=="Y" and listed[i+1]=="T":
        ans=ans
        
    if listed[i]=="T" and listed[i+1]=="Y":
        ans=ans*2%(10**9+7)
        
        
    if listed[i]=="T" and listed[i+1]=="T":
        ans=ans*2%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
t=input()
p=0
i=0
ans=1
while i<n:
	if s[i]==t[i]:
		if p==0:
			ans*=3
		elif p=="x":
			ans*=2
		p="x"
		ans%=(10**9+7)
		i+=1
	else:
		if p==0:
			ans*=6
		elif p=="x":
			ans*=2
		else:
			ans*=3
		p="y"
		ans%=(10**9+7)
		i+=2
print(ans)