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
# Your code here!
N=int(input())
s=[[]*N for i in range(2)]
s[0]=input()
s[1]=input()

prev=0#タテなら1 ヨコなら-1
ans=1
i=0
while i!=N:
    if s[0][i]==s[1][i]:
        if prev==1:
            ans=ans*2
        elif prev==-1:
            pass
        else:
            ans=ans*3
        prev=1
    else:
        if prev==1:
            ans=ans*2
        elif prev==-1:
            ans=ans*3
        else:
            ans=ans*6
        prev=-1
        i+=1
    i+=1
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
"""
abb
acc  6

ab
ab   6

bbc
aac  3

bbaa
ccdd  2
"""

n = int(input())
u = input()
d = input()

bef = -1 #0:vert,  1:horizon

ans = 1
ind = 0
mod = 1000000007
while (True):
    if u[ind] == d[ind]:
        ind += 1
        if bef == -1:
            ans *= 3
        elif bef == 0:
            ans *= 2
            ans %= mod
        else:
            ans *= 1
            ans %= mod
        bef = 0

    else:
        ind += 2
        if bef == -1:
            ans *= 6
        elif bef == 0:
            ans *= 2
            ans %= mod
        else:
            ans *= 3
            ans %= mod
        bef = 1
    # print(ans)
    if ind > n-1:
        break
print(ans)

Submission status: Accepted

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

A = []
cur = 0
while cur < N:
    if S1[cur] == S2[cur]:
        A.append("X")
        cur += 1
    else:
        A.append("Y")
        cur += 2

ans = 3 if A[0] == "X" else 6
for i in range(1, len(A)):
    if A[i - 1] == "X":
        ans *= 2
    elif A[i] == "Y":
        ans *= 3
    ans %= 1000000007

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    a = LI()
    d = defaultdict(lambda:0)
    for i in a:
        d[i] += 1
    d = list(d.values())
    d.sort()
    ans = 0
    for i in range(len(d)-k):
        ans += d[i]
    print(ans)
    return

#B
def B():
    n,z,w = LI()
    a = LI()
    if n == 1:
        print(abs(a[0]-w))
        return
    ans = max(abs(a[-1]-w),abs(a[-2]-a[-1]))
    print(ans)
    return

#C
def C():
    n = I()
    s1 = S()
    s2 = S()
    dp = [[[0]*3 for j in range(3)] for i in range(n+1)]
    if s1[0] == s2[0]:
        dp[1] = [[1 if i == j else 0 for j in range(3)] for i in range(3)]
    else:
        dp[1] = [[0 if i == j else 1 for j in range(3)] for i in range(3)]
    for i in range(1,n):
        ni = i+1
        if s1[i] == s2[i]:
            for j in range(3):
                for k in range(3):
                    if k == j:continue
                    for l in range(3):
                        if l == j:continue
                        dp[ni][j][j] += dp[i][k][l]
        else:
            if i and s1[i] == s1[i-1]:
                for j in range(3):
                    for k in range(3):
                        dp[ni][j][k] = dp[i][j][k]
            else:
                for j in range(3):
                    for k in range(3):
                        if k == j:continue
                        for l in range(3):
                            if l == j:continue
                            for m in range(3):
                                if m == k:continue
                                dp[ni][j][k] += dp[i][l][m]
    ans = 0
    for i in range(3):
        for j in range(3):
            ans += dp[n][i][j]
    print(ans%mod)
    return

#D
def D():

    return

#E
def E():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
# ARC081D - Coloring Dominoes (ABC071D)
def main():
    N = int(input())
    S1 = input().rstrip()
    S2 = input().rstrip()
    MOD = 10 ** 9 + 7
    a, b = S1[0], S2[0]
    ans = 3 if a == b else 6
    for i, j in zip(S1[1:], S2[1:]):
        if a != i and b != j:
            if a == b:
                ans *= 2
            else:
                ans *= 1 if i == j else 3
            ans %= MOD
        a, b = i, j
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
mod = 10**9 + 7
ans = 0
if s1[0] == s2[0]:
    ans = 3
    for i in range(1,n):
        if s1[i] == s2[i]:
            if s1[i-1] == s2[i-1]:
                ans *= 2

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

        else:
            if s1[i] == s1[i-1] and s2[i] == s2[i-1]:
                continue
            elif s1[i-1] == s2[i-1]:
                ans *= 2
            else:
                ans *= 3
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)
N = int(input())
S1 = input()
S2 = input()
now = 0
ans = 1
flag = False
for i in range(N):
    if flag:
        flag = False
        continue
    s11 = S1[i]
    s21 = S2[i]
    if s11 == s21:
        ans = (ans * (3 - now)) % MOD
        now = 1
    else:
        flag = True
        if now == 0:
            ans = (ans * 6) % MOD
        elif now == 1:
            ans = (ans * 2) % MOD
        else:
            ans = (ans * 3) % MOD
        now = 2
print(ans)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s1 = input()
s2 = input()
ans = 0
flg = 0
fact = [1]*53
for i in range(1,53):
    fact[i] = fact[i-1]*i

def comb(n,r):
    return fact[n] // fact[n-r] // fact[r]

if s1[0] == s2[0]:
    ans += 3
    flg = 0
    i = 1
else:
    ans += comb(3,2)*2
    ans %= mod
    flg = 1
    i = 2
while i < n:
    if flg == 0 and s1[i] == s2[i]:
         ans *= 2
         ans %= mod
         i += 1
    elif flg == 1 and s1[i] == s2[i]:
        ans *= 1
        flg = 0
        i += 1
    elif flg == 0 and s1[i] != s2[i]:
        ans *= 2
        ans %= mod
        flg = 1
        i += 2
    elif flg == 1 and s1[i] != s2[i]:
        ans *= 3
        ans %= mod
        i += 2
print(ans)

Submission status: Accepted

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

def main():
    MOD = 1000000007
    N = int(input())
    s = []
    s.append(list(input().strip()))
    s.append(list(input().strip()))

    # pre 0:たて 1:よこ
    i = 0
    if s[0][i] == s[1][i]:
        pre = 0
        ans = 3
        i += 1
    else:
        pre = 1
        ans = 6
        i += 2
    
    while i < N:
        # print(i)
        if s[0][i] == s[1][i]:
            if pre == 0:
                ans *= 2
            else:
                ans *= 1
            i += 1
            pre = 0
        else:
            if pre == 0:
                ans *= 2
            else:
                ans *= 3
            i += 2
            pre = 1
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int, S: "List[str]"):
    i = 0
    res = 1
    before = 0 # 0: h, 1: v
    while i < N:
        if S[0][i] == S[1][i]:
            if i == 0:
                res = 3
            elif before == 0:
                res = res * 2 % MOD
            else:
                res = res
            before = 0
            i += 1
        else:
            if i == 0:
                res = 6
            elif before == 0:
                res = res * 2 % MOD
            else:
                res = res * 3 % MOD
            before = 1
            i += 2
    print(res)
    return


# Generated by 1.1.4 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:
def solve(n, s):
    i = 0
    v_or_h = []
    cmb = 1
    while i < n:
        # a
        # a
        if s[0][i] == s[1][i]:
            v_or_h.append('v')
            i += 1
        # aa
        else:
            v_or_h.append('h')
            i += 2

    length = len(v_or_h)

    for j in range(length):
        if v_or_h[j] == 'v':
            if j == 0:
                cmb *= 3
            else:
                if v_or_h[j-1] == 'v':
                    cmb *= 2
                else:
                    pass
        else:
            if j == 0:
                cmb *= 6
            else:
                if v_or_h[j-1] == 'v':
                    cmb *= 2
                else:
                    cmb *= 3

    return cmb % 1000000007


if __name__ == '__main__':
    n = int(input())
    s = []
    for _ in range(2):
        s.append(input())
    print(solve(n, s))

Submission status: Accepted

Solution code:
N=int(input())
S=(input(),input())
a=1
i=0
s=0
mod=10**9+7
while i<N:
    if S[0][i]==S[1][i]:
        if s==0:
            a=3 if i==0 else (a*2)%mod
        s=0
    else:
        if s==0:
            a=6 if i==0 else (a*2)%mod
        else:
            a=6 if i==0 else (a*3)%mod
        s=1
        i+=1
    i+=1
print(a)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
code = []
mod = 10**9+7
index = 0
while index < N:
    if S1[index] == S2[index]:
        code.append("A")
        index += 1
    else:
        code.append("B")
        index += 2

if code[0] == "A":
    ans = 3
else:
    ans = 6

for i in range(1, len(code)):
    if code[i-1] == "A" and code[i] == "A":
        ans = ans*2 % mod
    elif code[i-1] == "A" and code[i] == "B":
        ans = ans*2 % mod
    elif code[i-1] == "B" and code[i] == "A":
        continue
    else:
        ans = ans*3 % mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

def solve(n, s1, s2):
    if s1[0] != s2[0]:
        ans = 6
        i = 2
        prev_solid = False
    else:
        ans = 3
        i = 1
        prev_solid = True
    shape_factor_mapping = {
        (True, True): 2,
        (True, False): 2,
        (False, True): 1,
        (False, False): 3
    }
    while i < n:
        solid = (s1[i] == s2[i])
        factor = shape_factor_mapping[prev_solid, solid]
        ans = (factor * ans) % MOD
        i += 2 - solid
        prev_solid = solid
    return ans

n = int(input())
s1 = input()
s2 = input()
print(solve(n, s1, s2))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def scan_domino(a: list, b: list):
    n = len(a)
    cnt = 0
    domino = ""

    while cnt < n:
        if a[cnt] == b[cnt]:
            domino += "x"
            cnt += 1
        else:
            domino += "y"
            cnt += 2

    return domino


def cnt_pattern(domino, mod):
    ans = 3 if domino[0] == "x" else 6
    for dleft, dright in zip(domino[:-1], domino[1:]):
        if dleft == "x" and dright == "x":
            ans *= 2
        elif dleft == "x" and dright == "y":
            ans *= 2
        elif dleft == "y" and dright == "x":
            ans *= 1
        else:
            ans *= 3

        ans %= mod

    return ans


n = ni()
a = lc()
b = lc()

MOD = 10**9 + 7

domino = scan_domino(a, b)
pats = cnt_pattern(domino, MOD)

print(pats)

Submission status: Accepted

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


def main():
    n = int(input())
    s = [input() for _ in range(2)]
    mod = 10 ** 9 + 7
    ans = 1
    i = 0

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

    while i < n:
        if s[0][i] == s[1][i]:
            if s[0][i - 1] == s[1][i - 1]:
                ans *= 2

            i += 1
        else:
            if s[0][i - 1] == s[1][i - 1]:
                ans *= 2
            else:
                ans *= 3

            i += 2

        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = [input() for _ in range(2)]
mod = 10**9+7
is_2 = False
cnt = 1
li = []
for ind,i in enumerate(S[0]):
    if(is_2):
        is_2 = False
        continue
    if(ind==N-1):
        li.append(1)
        break
    if(S[0][ind+1]==i):
        li.append(2)
        is_2=True
    else:
        li.append(1)

for ind,i in enumerate(li):
    if(ind==0):
        if(i==1):
            cnt *= 3
        else:
            cnt *= 6
    else:
        if(li[ind-1]==1):
            cnt *= 2
        elif(li[ind-1]==i and i==2):
            cnt *= 3
    cnt%=mod
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

S1 = input()
S2 = input()

dom_list = []
flag=False
for i in range(N):
    if S1[i]==S2[i]:
        dom_list.append(0)
    else:
        if flag:
            dom_list.append(1)
            flag=False
        else:
            flag=True

D = [0]*len(dom_list)
if dom_list[0]==0:
    D[0]=3
else:
    D[0]=6

mod = 10**9 + 7

for i in range(1,len(dom_list)):
    if dom_list[i]==0:
        if dom_list[i-1]==0:
            D[i]=D[i-1]*2
            D[i]%=mod
        else:
            D[i]=D[i-1]
    else:
        if dom_list[i-1]==0:
            D[i]=D[i-1]*2
            D[i]%=mod
        else:
            D[i]=3*D[i-1]
            D[i]%=mod

print(D[len(dom_list)-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce

# 入力
N = int(input())
S1 = input()
S2 = input()

MOD = 1000000007


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# (1x2)x2 と (2x1) を1ブロックとみなして、色の塗り方の組合せを数え上げる
ans, _ = reduce(
    lambda acc, s:
        (3 * acc[0], 3) if acc[1] == 0 and s[0] == s[1] else
        (6 * acc[0], 1) if acc[1] == 0 and s[0] != s[1] else
        (acc[0], 2) if acc[1] == 1 else
        (acc[0], 3) if acc[1] == 2 and s[0] == s[1] else
        (3 * acc[0], 1) if acc[1] == 2 and s[0] != s[1] else
        (2 * acc[0], 3) if acc[1] == 3 and s[0] == s[1] else
        (2 * acc[0], 1),
    zip(S1, S2),
    (ModInt(1), 0)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

# 入力
N = int(input())
S1 = input()
S2 = input()

MOD = 1000000007


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# (1x2)x2 と (2x1) を1ブロックとみなして、色の塗り方の組合せを数え上げる
ans, _ = reduce(
    lambda acc, s: (
        (3 * acc[0], 3) if acc[1] == 0 and s[0] == s[1] else
        (6 * acc[0], 1) if acc[1] == 0 and s[0] != s[1] else
        (acc[0], 2) if acc[1] == 1 else
        (acc[0], 3) if acc[1] == 2 and s[0] == s[1] else
        (3 * acc[0], 1) if acc[1] == 2 and s[0] != s[1] else
        (2 * acc[0], 3) if acc[1] == 3 and s[0] == s[1] else
        (2 * acc[0], 1)
    ),
    zip(S1, S2),
    (ModInt(1), 0)
)

# 出力
print(ans)

Submission status: Accepted

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

ans=1
i=0
b=0
while i<n:
    if s1[i]==s2[i]:
        if b==0:
            ans*=3
        elif b==1:
            ans*=2
        else:
            ans*=1
        b=1
        i+=1
    else:
        if b==0:
            ans*=6
        elif b==1:
            ans*=2
        else:
            ans*=3
        b=2
        i+=2
    ans=ans%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:

MOD = int(1e9) + 7

def main():
    buf = input()
    N = int(buf)
    S = []
    for i in range(2):
        buf = input()
        S.append(buf)
    last_pattern = None # 1: 1 x 2, 2: 2 x 1
    combination = 1
    point = 0
    while point < N:
        if S[0][point] == S[1][point]: # 1 x 2
            if last_pattern is None: # first column
                combination *= 3
            elif last_pattern == 1:
                combination *= 2 # 2 possible colors
            else: # last_pattern == 2
                combination *= 1 # 1 possible color
            last_pattern = 1
            point += 1
        else: # 2 x 1
            if last_pattern is None: # first column
                combination *= 6
            elif last_pattern == 1:
                combination *= 2 # 2 possible color combinations
            else: # last_pattern == 2
                combination *= 3 # 3 possible color combinations
            last_pattern = 2
            point += 2
        combination %= MOD
    print(combination)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
t = input()
ans = 1
i = 0
while i <= n-1:
    if s[i] == t[i]:
        if i == 0:
            ans *= 3
        else:
            if before == "yoko":
                pass
            else:
                ans *= 2
        i += 1
        before = "tate"

    else:
        if i == 0:
            ans *= 6
        else:
            if before == "yoko":
                ans *= 3
            else:
                ans *= 2
        i += 2
        before = "yoko"
    ans %= 1000000007
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

S1, S2 = s1[0], s2[0]

for s, _ in zip(s1, s2):
    if S1[-1] != s:
        S1 += s
        S2 += _

TATE, YOKO = 0, 1

if S1[0] == S2[0]:
    prev = TATE
    cum = 3
else:
    prev = YOKO
    cum = 6

for i in range(1, len(S1)):
    if S1[i] == S2[i]:
        now = TATE
    else:
        now = YOKO
    if now == TATE:
        if prev == YOKO:
            pass
        else:
            cum *= 2
        prev = TATE
    elif now == YOKO:
        if prev == YOKO:
            cum *= 3
        else:
            cum *= 2
        prev = YOKO

    cum %= (1000000007)
print(int(cum))

Submission status: Accepted

Solution code:
n=int(input())
s1=input()
s2=input()
if s1[0]==s2[0]:
  pos=1
  ans=3
  flag=0
else:
  pos=2
  ans=6
  flag=1
while pos<n:
  if flag==0:
    if s1[pos]==s2[pos]:
      ans*=2
      pos+=1
      flag=0
    else:
      ans*=2
      pos+=2
      flag=1
  else:
    if s1[pos]==s2[pos]:
      ans*=1
      pos+=1
      flag=0
    else:
      ans*=3
      pos+=2
      flag=1
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
s1 = input()
s2 = input()
p = 0
ans = 1
while p < N:
      # 
      if s1[p] == s2[p]:
            if p == 0:
                  ans *= 3
            else:
                  # 手前が縦なら2通り選べる
                  if s1[p-1] == s2[p-1]:
                        ans *= 2
                  # 手前が横なら残っている色しか選べない
                  else:
                        ans *= 1
                  
            p += 1      
      elif s1[p] != s2[p]:
            if p == 0:
                  ans *= 6
            else:
              # 手前が縦の場合、上下の入れ替えで2通り
              if s1[p-1] == s2[p-1]:
                ans *= 2
              elif s1[p-1] != s2[p-1]:
                # 手前が横の場合、3通り？
                ans *= 3
            p += 2

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

Submission status: Accepted

Solution code:
from itertools import*
input()
mod=10**9+7

x=[len(list(v))for k,v in groupby(input())]
if x[0]==1:
    ans=3
else:
    ans=6
if len(x)==1:
    print(ans)
else:
    for i in range(1,len(x)):
        if x[i-1]==1 and x[i]==1:
            ans*=2%mod
        elif x[i-1]==2 and x[i]==2:
            ans*=3%mod
        elif x[i-1]==1 and x[i]==2:
            ans*=2%mod
    print(ans%mod)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

#ドミノの並べ方は縦1個おきか(X)、2個横に並べるか(Y)のどちからをつなげていくしかない
#端から見ていけばXかYかで塗り方は定まる

n = int(input())
s1 = list(input())
s2 = list(input())
ans = 1
XY = 0
i,j=0,0
while  i<n:
    if s1[i] == s2[j]:
        if XY == "X":
            ans *= 2
            ans %= mod
            i +=1
            j +=1
        elif XY =="Y":
            i += 1
            j += 1
            XY ="X"
        else:
            ans *= 3
            ans %= mod
            i += 1
            j += 1
            XY ="X"
    else:
        if XY =="X":
            ans *= 2
            ans %= mod
            XY ="Y"
            i += 2
            j += 2
        elif XY =="Y":
            ans *= 3
            ans %= mod
            i += 2
            j += 2
        else:
            ans *= 6
            ans %=mod
            i += 2
            j += 2
            XY ="Y"
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
mod = 10**9 + 7
ans = 1
prv = 0
if S1[0] == S2[0]:
    ans *= 3
    prv = 1
else:
    ans *= 6
    prv = 2
for i in range(1, N):
    if prv == 2:
        prv = 3
        continue
    else:
        if S1[i] == S2[i]:
            if prv == 3:
                ans %= mod
                prv = 1
            else:
                ans *= 2
                ans %= mod
                prv = 1
        
        else:
            if prv == 3:
                ans *= 3
                ans %= mod
                prv = 2
            else:
                ans *= 2
                ans %= mod
                prv = 2
                
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

i = 0
j = 0
ans = 1
while i<n:
    if n-i>1 and s[i+1]==s[i]:
        if j == 0:
            ans *= 6
        elif j == 1:
            ans *= 2
        else:
            ans *= 3
        j = 2
        i+=2
    else:
        if j == 0:
            ans *= 3
        elif j == 1:
            ans *= 2
        j = 1
        i += 1
    ans %= 10**9+7

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ss = input()

i = 0
state = 0
ans = 1
while i<n:
    if n-i>1:
        if s[i+1]==s[i]:
            if state == 0:
                ans *= 6
            elif state == 1:
                ans *= 2
            else:
                ans *= 3
            state = 2
            i+=2
        else:
            if state == 0:
                ans *= 3
            elif state == 1:
                ans *= 2
            else:
                ans *= 1
            state = 1
            i+=1
    else:
        if state == 0:
            ans *= 3
        elif state == 1:
            ans *= 2
        else:
            ans *= 1
        state = 1
        i += 1
    ans %= 10**9+7

print(ans)

Submission status: Accepted

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

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