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

        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

P = 10**9 + 7

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

if S1[0] == S1[1]:
  rlt = 6
  f = 1
  i = 2
else:
  rlt = 3
  f = 0
  i = 1
  
while i < N-1:
  if f == 0:
    rlt *= 2
    rlt %= P
    if S1[i] != S1[i+1]:
      i += 1
    else:
      f = 1
      i += 2
  else:
    if S1[i] != S1[i+1]:
      f = 0
      i += 1
    else:
      rlt *= 3
      rlt %= P
      i += 2

if i == N-1 and f == 0:
  rlt *= 2
  rlt %= P

print(rlt)

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
mod = 1000000007
if n == 1:
    print(3)
    exit()
cnt = 3 if s1[0] == s2[0] else 6
for i in range(1, n):
    if s1[i-1] == s1[i]:
        cnt *= 1
        continue
    if s1[i-1] == s2[i-1]:
        cnt = cnt * 2 % mod
    elif s1[i] != s2[i]:
        cnt = cnt * 3 % mod
    else:
        cnt *= 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
dat = []
s = input()
t = input()
i = 0
while i < n:
    if s[i] == t[i]:
        dat.append(0)
        i+=1
    else:
        dat.append(1)
        i+=2
#print(dat)
res = 0
prev = None
if dat[0] == 0:
    res = 3
    prev = 0
else:
    res = 6
    prev = 1
for i in range(1, len(dat)):
    if prev == 0 and dat[i] == 0:
        res *= 2
    elif prev == 0 and dat[i] == 1:
        res *= 2
    elif prev == 1 and dat[i] == 0:
        res *= 1
    elif prev == 1 and dat[i] == 1:
        res *= 3
    prev = dat[i]
print(res % 1000000007)

Submission status: Accepted

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

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

dp = [0] * n
dp[0] = 3 if s1[0] == s2[0] else 6

for i in range(1, n):
    # 横に並んでいる場合は増えない
    if s1[i - 1] == s1[i]:
        dp[i] = dp[i - 1]
        continue
    # 前回縦に並んでいたなら2色から選べる
    if s1[i - 1] == s2[i - 1]:
        dp[i] = dp[i - 1] * 2 % MOD
    # 前回が縦でなく、RGの組み合わせÎならG-B, G-R, B-Rの3通りが選べる
    elif s1[i] != s2[i]:
        dp[i] = dp[i - 1] * 3 % MOD
    else:
        dp[i] = dp[i - 1]

print(dp[-1])

Submission status: Accepted

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

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

dp = [0] * n
dp[0] = 3 if s1[0] == s2[0] else 6

for i in range(1, n):
    if s1[i - 1] == s1[i]:
        dp[i] = dp[i - 1]
        continue
    if s1[i - 1] == s2[i - 1]:
        dp[i] = dp[i - 1] * 2 % MOD
    elif s1[i] != s2[i]:
        dp[i] = dp[i - 1] * 3 % MOD
    else:
        dp[i] = dp[i - 1]

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
s1 = str(input())
s2 = str(input())
MOD = 10 ** 9 + 7
S1, S2 = s1[0], s2[0]
for i in range(1, n):
    if S1[-1] != s1[i]:
        S1 += s1[i]
        S2 += s2[i]
if S1[0] == S2[0]:
    ans = 3
    cnd = 0
else:
    ans = 6
    cnd = 1
for i in range(1, len(S1)):
    if cnd == 0:
        if S1[i] == S2[i]:
            ans *= 2 % MOD
        else:
            ans *= 2 % MOD
            cnd = 1
    else:
        if S1[i] == S2[i]:
            cnd = 0
        else:
            ans *= 3 % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S1 = input()
    S2 = input()
    mod = 10**9 + 7
    if S1[0] != S2[0]:
        r = 6
    else:
        r = 3
    for i in range(1, N):
        if S1[i-1] == S1[i]:
            continue
        if S1[i] == S2[i] and S1[i-1] != S2[i-1]:
            continue
        if S1[i] != S2[i] and S1[i-1] != S2[i-1]:
            r *= 3
            r %= mod
            continue
        r *= 2
        r %= mod
    return r
print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S1 = input()
    S2 = input()
    mod = 10**9 + 7
    v = set()
    v.add(S1[0])
    v.add(S2[0])
    if len(v) == 2:
        r = 6
    else:
        r = 3
    for i in range(1, N):
        if S1[i-1] == S1[i]:
            continue
        if S1[i] == S2[i] and S1[i-1] != S2[i-1]:
            continue
        if S1[i] != S2[i] and S1[i-1] != S2[i-1]:
            r *= 3
            r %= mod
            continue
        r *= 2
        r %= mod
    return r
print(main())

Submission status: Accepted

Solution code:
mod = 1000000007
N = int(input())
S = [list(input()) for _ in range(2)]
i = 0
ans = 1
if S[0][0] == S[1][0]:
  ans = 3
  i = 1
else:
  ans = 6
  i = 2
while i < N:
  if S[0][i-1] == S[1][i-1]:
    if S[0][i] == S[1][i]:
      ans = (ans * 2)%mod
      i += 1
    else:
      ans = (ans * 2)%mod
      i += 2
  else:
    if S[0][i] == S[1][i]:
      i += 1
    else:
      ans = (ans * 3)%mod
      i += 2
print(ans)

Submission status: Accepted

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

dp = [0] * n
mod = 10 ** 9 + 7

if t[0] == b[0]:
    dp[0] = 3
else:
    dp[0] = 6

for i in range(1, n):
    if t[i] == t[i-1]:
        dp[i] = dp[i-1]
    else:
        if t[i-1] == b[i-1]:
            if t[i] == b[i]:
                dp[i] = dp[i-1] * 2 % mod
            else:
                dp[i] = dp[i-1] * 2 % mod
        else:
            if t[i] == b[i]:
                dp[i] = dp[i-1] % mod
            else:
                dp[i] = dp[i-1] * 3 % mod

print(dp[-1])

Submission status: Accepted

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

mod = 1000000007

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

print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial[0] == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


N = n = int(input())
s = [input() for i in range(2)]

ret = []
i = 0
while i < N:
    if s[0][i] == s[1][i]:
        ret.append(1)
        i += 1
    else:
        ret.append(2)
        i += 2
ans = 3*ret[0]
for i in range(1, len(ret)):
    if ret[i-1] == 1 and ret[i] == 1:
        ans *= 2
    elif ret[i-1] == 1 and ret[i] == 2:
        ans *= 2
    elif ret[i-1] == 2 and ret[i] == 1:
        ans *= 1
    elif ret[i-1] == 2 and ret[i] == 2:
        ans *= 3
    ans %= MOD

print(ans)
# print(ret)

Submission status: Accepted

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

# 左から順に見ていく
# 縦に同じものが並んでいた場合、
# ・その直前が横だったら1通り
# ・その直前が縦だったら2通り
# ・最初だけは3通り
# インデックスを1進める
# 縦に違うものが並んでいた場合、(横)
# ・その直前が横だったら3通り
# ・その直前が縦だったら2通り
# ・最初だけは6通り
# インデックスを2進める

N = int(readline())
S1 = readline().rstrip()
S2 = readline().rstrip()

DIV = 1000000007

ans = 1
i = 0
same = True
while i < N:
  if S1[i] == S2[i]:
    if i == 0:
      ans *= 3
    elif not same:
      ans *= 1
    else:
      ans *= 2
    ans %= DIV
    same = True
    i += 1
  else:
    if i == 0:
      ans *= 6
    elif not same:
      ans *= 3
    else:
      ans *= 2
    ans %= DIV
    same = False
    i += 2
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
s = input()
p = input()
ans = 0
f = 0
i = 0
two = False
while i < n:
    if i == 0:
        if s[i] == p[i]:
            ans = 3
        else:
            ans = 6
            i += 1
            two = True
        i += 1
        continue
    if i >= n:break
    if s[i] == p[i]:
        if two:
            pass
        else:
            ans *= 2
        two = False
    else:
        if two:
            ans *= 3
        else:
            ans *= 2
        two = True
        i += 1
    i += 1
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
s = input()
p = input()
ans = 0
f = 0
i = 0
while i < n:
    if i > n:break
    if s[i] == p[i]:
        if i == 0:
            ans = 3
        else:
            if f == 1:
                ans *= 1
            else:
                ans *= 2
        f = 0
    else:
        if i == 0:
            ans = 6
        else:
            if f == 1:
                ans *= 3
            else:
                ans *= 2
        f = 1
        i += 1
    i += 1
    ans %= MOD
print(ans%MOD)

Submission status: Accepted

Solution code:

MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    S = [input() for _ in range(2)]
    d = []
    i = 0
    while i < N:
        if S[0][i] == S[1][i]:
            i += 1
            d.append(0)
        else:
            i += 2
            d.append(1)
    output = 6 if d[0] else 3
    for i in range(len(d)-1):
        if d[i+1] == 0 and d[i] == 0: output *= 2
        elif d[i+1] == 0 and d[i] == 1: continue
        elif d[i+1] == 1 and d[i] == 0: output *= 2
        else: output *= 3
        output %= MOD
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S1 = list(input())
S2 = list(input())

if S1[0] == S2[0]:
    ans = 3
    start = 1
else:
    ans = 6
    start = 2

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

Submission status: Accepted

Solution code:
MOD = 1000000007
n = int(input())
s = input()
t = input()

ans = 3
i = 0
if s[0]==t[0]:
    i += 1
    vert = True
else:
    ans *= 2
    i += 2
    vert = False

while i<n:
    if s[i]==t[i]:
        if vert:
            ans *= 2
            ans %= MOD
        vert = True
        i += 1
    else:
        if vert:
            ans *= 2
        else:
            ans *= 3
        ans %= MOD
        vert = False
        i += 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s1 = input()
s2 = input()

h = 0
mod = 10**9 + 7

ans = 1
prev_pat = 0
while h < len(s1):

    # pattern 1
    if s1[h] == s2[h]:
        if h == 0:
            ans *= 3
        elif prev_pat == 1:
            ans *= 2
        else:  #prev_pat == 2
            ans *= 1
        h += 1
        prev_pat = 1
    elif s1[h] == s1[h + 1]:  # pattern 2
        if h == 0:
            ans *= 6
        elif prev_pat == 1:
            ans *= 2
        else:  #prev_pat == 2
            ans *= 3
        h += 2
        prev_pat = 2
    else:
        print("this line should not be reached")
        exit(0)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
M = 10**9+7
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] == s[i]:
    continue
  if s[i-1] == t[i-1]:
    ans = ans * 2 % M
  elif s[i] != t[i]:
    ans = ans * 3 % M
print(ans)

Submission status: Accepted

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

idea = '''
ABB
ACC
任意の A の選び方に対して B の選び方 2 通り * C の選び方 1 通り

AB
AB
任意の A の選び方に対して B の選び方 2 通り

AABB
CCDD
任意の A,B の選び方に対して、 C,D の選び方 3 通り
1122 1122 1133
2211 2233 2211

AAC
BBC
任意の A,B の選び方に対して、 C の選び方 1 通り

開幕だけちょっと気をつける
'''

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip("\n")
    T = input().strip("\n")
    DP = [0] * N
    mod = 7 + 10 ** 9
    if S[0] == T[0]: DP[0] = 3
    else: DP[0] = 6

    for i in range(1, N):
        if S[i] == S[i-1]: #ドミノが横向き
            DP[i] = DP[i-1]
        else: #ドミノの境目
            if S[i-1] == T[i-1]: #左のドミノが縦向き
                DP[i] = (2 * DP[i-1]) % mod
            else: #左のドミノが横向き
                if S[i] == T[i]: #自身は縦向き
                    DP[i] = DP[i-1]
                else: #横向き
                    DP[i] = (3 * DP[i-1]) % mod
    print(DP[N-1])


    return  0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
ue = input()
sita = input()
narabe = []
flag = False
mod = 10**9 + 7
for i in range(n):
    if ue[i] == sita[i]:
        narabe.append(0)
    elif ue[i] != sita[i]:
        if not flag:
            flag = True
            narabe.append(1)
        elif flag:
            flag = False

dp = [0 for i in range(len(narabe))]
if narabe[0] == 0:
    dp[0] = 3
elif narabe[0] == 1:
    dp[0] = 6
for i in range(1,len(narabe)):
    if narabe[i-1] == 1 and narabe[i] == 1:
        dp[i] = (dp[i-1]*3)%mod
    elif narabe[i-1] == 1 and narabe[i] == 0:
        dp[i] = dp[i-1]
    elif narabe[i-1] == 0 and narabe[i] == 0:
        dp[i] = (dp[i-1]*2)%mod
    elif narabe[i-1] == 0 and narabe[i] == 1:
        dp[i] = (dp[i-1]*2)%mod
        
print(dp[-1])

Submission status: Accepted

Solution code:
N=int(input())
S=[[],[]]
S[0]=list(input())
S[1]=list(input())
p=1000000007
#print(S)

L= [1] if S[0][0]==S[1][0] else []
for i in range(1,N):
  if S[0][i]==S[0][i-1] and S[1][i]==S[1][i-1]:
    L.append(2)
  elif S[0][i]==S[1][i]:
    L.append(1)
#print(L)

for i,num in enumerate(L):
  if i==0:
    if num==1:
      cnt = 3
    else:
      cnt = 6
  else:
    if L[i]==1 and L[i-1]==1:
      cnt = (cnt*2)%p
    elif L[i]==1 and L[i-1]==2:
      cnt = (cnt*1)%p
    elif L[i]==2 and L[i-1]==1:
      cnt = (cnt*2)%p
    else: #2,2
      cnt = (cnt*3)%p
  #print(cnt)
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for _ in range(2)]
MOD = 1000000007
i = 0
res = 1
if s[0][i] == s[1][i]:
    res *= 3
else:
    res *= 3*2
    i += 1
i += 1
while i < n:
    if s[0][i-1] == s[1][i-1]:
        res *= 2
        res %= MOD
        if s[0][i] != s[1][i]:
            i+=1
        i+=1
    else:
        if s[0][i] != s[1][i]:
            res *= 3
            res %= MOD
            i+=1
        i+=1
print(res)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    mat = [list(input()) for _ in range(2)]

    none, single, double = 0, 1, 2
    table = {(none, single): 3, (none, double): 6, (single, single): 2, (single, double): 2, (double, single): 1,
             (double, double): 3}
    prev = none
    ans = 1
    next_skip = False

    for i in range(len(mat[0])):
        if next_skip:
            next_skip = False
            continue

        current = single if mat[0][i] == mat[1][i] else double
        ans *= table[(prev, current)]
        ans %= MOD

        if current == double:
            next_skip = True
        prev = current

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s_1 = input()
s_2 = input()
i = 0
count = 1
while i < n:
  if s_1[i] == s_2[i]:
    if i == 0:
      count *= 3
    elif s_1[i-1] == s_2[i - 1]:
      count *= 2
    i += 1
  else:
    if i == 0:
      count *= 6
    elif s_1[i-1] == s_2[i-1]:
      count *= 2
    else:
      count *= 3
    i += 2
    
print(count % (10**9 + 7))

Submission status: Accepted

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

cnt = 1

for i in range(n):
    if i == 0:
        if s1[i] == s2[i]:
            cnt = cnt * 3
            previous = 'tate'
        else:
            cnt = cnt * 6
            previous = 'yoko1'
    else:
        if s1[i] == s2[i]:   #tate
            if previous == 'tate':
                cnt = cnt * 2
            elif previous == 'yoko2':
                cnt = cnt * 1
                previous = 'tate'
        else:   #yoko
            if previous == 'tate':
                cnt = cnt * 2
                previous = 'yoko1'
            elif previous == 'yoko2':
                cnt = cnt * 3
                previous = 'yoko1'
            elif previous == 'yoko1':
                previous = 'yoko2'
        
print(cnt%1000000007)

Submission status: Accepted

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

moji = ""
flag = True

for i in range(n):
    if flag == False:
        flag = True
        continue
    if s[i] != t[i]:
        moji += "A"
        flag = False
    else:
        moji += "B"

if moji[0] == "A":
    now = 6
else:
    now = 3

l = len(moji)
mod = 10**9+7

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

print(now%mod)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
S = [S1] + [S2]
s = []
ans = 1
p = 10**9+7
if S[0][0] == S[1][0]:
  s.append(0)
  ans = ans *3
  ans = ans%p
else:
  s.append(1)
  ans = ans *6
  ans = ans%p
  
for i in range(1,N):
  if S[0][i] == S[1][i] and s[i-1] == 0:
    s.append(0)
    ans = ans *2
    ans = ans % p
  elif S[0][i] == S[1][i] and s[i-1] == 1:
    s.append(0)
    ans = ans *1
    ans = ans % p
  elif S[0][i] != S[1][i] and s[i-1] == 0:
    s.append(1)
    ans = ans *2
    ans = ans % p
  elif S[0][i-1] != S[0][i]:
    s.append(1)
    ans = ans *3
    ans = ans%p
  else:
    s.append(1)
    
print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
N = int(input())
S1 = input().strip()
S2 = input().strip()
cnt = 1
cur = 0
if N>=2 and S1[0]==S1[1]:
    cnt = cnt*6
    cur = 2
else:
    cnt = cnt*3
    cur = 1
while cur<N:
    if cur<N-1 and S1[cur]==S1[cur+1]:
        if S1[cur-1]==S2[cur-1]:
            cnt = (cnt*2)%p
            cur += 2
        else:
            cnt = (cnt*3)%p
            cur += 2
    elif S1[cur-1]==S2[cur-1]:
        cnt = (cnt*2)%p
        cur += 1
    elif cur>=2 and S1[cur-2]==S1[cur-1]:
        cur += 1
print(cnt)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
S = input() + "_"
T = input() + "_"
D = []
i = 0
while i < N:
    if S[i] == S[i+1]:
        D.append(2)
        i += 1
    else:
        D.append(1)
    i += 1

if D[0] == 1:
    ans = 3
else:
    ans = 6
for k in range(1,len(D)):
    if D[k-1] == 1 and D[k] == 2:
        ans *= 2
    elif D[k-1] == 2 and D[k] == 1:
        ans *= 1
    elif D[k-1] == 1 and D[k] == 1:
        ans *= 2
    else:
        ans *= 3
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
T = input()
MOD = 10**9 + 7

isPrevI = S[0] == T[0]

ans = 3 if isPrevI else 6
now = 1 if isPrevI else 2

while now < N:
    isI = S[now] == T[now]

    if isPrevI:
        ans *= 2
    elif not isI:
        ans *= 3
    ans %= MOD
    now += 1 if isI else 2
    isPrevI = isI

print(ans)

Submission status: Accepted

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

mod = 10**9+7
ans = 1
flag = False
for i in range(n):
    if s1[i] == s2[i]:
        if i == 0:
            ans *= 3
        else:
            if flag:
                ans *= 2
            else:
                ans *= 1
        flag = True
    else:
        if i == n-1:
            continue
        else:
            if s1[i] == s1[i+1] and s2[i] == s2[i+1]:
                if i == 0:
                    ans *= 6
                else:
                    if flag:
                        ans *= 2
                    else:
                        ans *= 3
            else:
                continue
        flag = False
    ans %= mod
print(ans)

Submission status: Accepted

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

DIVIDER = 1000000007

pattern = []
for i, Si in enumerate(S[0]):
    if i == 0:
        cnt = 1
    else:
        if Si != Si_prev:
            pattern.append(cnt)
            cnt = 1
        else:
            cnt += 1
    #
    Si_prev = Si
else:
    pattern.append(cnt)

for i, n_v in enumerate(pattern):
    if i == 0:
        if n_v == 1:
            ans = 3
        else:
            ans = 6
    else:
        if n_v_prev == 1 and n_v == 1:
            ans = (ans * 2) % DIVIDER
        elif n_v_prev == 1 and n_v == 2:
            ans = (ans * 2) % DIVIDER
        elif n_v_prev == 2 and n_v == 1:
            ans = (ans * 1) % DIVIDER
        else:
            ans = (ans * 3) % DIVIDER
    #
    n_v_prev = n_v

# print("#", pattern)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
S1 = input()[:-1]
S2 = input()[:-1]
i = 0
ans = 1
MOD = 10**9+7

while i<N:
    if S1[i]==S2[i]:
        if i==0:
            ans *= 3
            ans %= MOD
        else:
            if flag==0:
                ans *= 2
                ans %= MOD
        
        flag = 0
        i += 1
    else:
        if i==0:
            ans *= 6
        else:
            if flag==0:
                ans *= 2
                ans %= MOD
            else:
                ans *= 3
                ans %= MOD
        
        flag = 1
        i += 2

print(ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())
S1 = list(input())
S2 = list(input())

if S1[0] == S2[0]:
    ans = 3
    flag = True #縦の時
    i = 1
else:
    ans = 6
    flag = False
    i = 2
while i < N:
    if S1[i] == S2[i]:
        i += 1
        if flag:
            ans = (ans * 2) % MOD
        else:
            flag = True
    else:
        i += 2
        if flag:
            ans = (ans * 2) % MOD
            flag = False
        else:
            ans = (ans * 3) % MOD
    
print (ans)

Submission status: Accepted

Solution code:
n=int(input())
t=list(input())
t2=list(input())
cnt=0
ans=1
mod=10**9+7
isdif=False
isend=True
while cnt<n:
    if t[cnt]==t2[cnt]:
        if isend:
            ans*=3
            isend=False
        elif not isdif:
            ans*=2
            ans%=mod
        else:
            pass
        isdif=False
        cnt+=1
    elif t[cnt]!=t2[cnt]:
        if isend:
            ans*=6
            isend=False
        elif isdif:
            ans*=3
            ans%=mod
        else:
            ans*=2
            ans%=mod
        isdif=True
        cnt+=2
print(ans)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)

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

pattern = []

i = 0
while i < N:
    if i != N-1 and S1[i] == S1[i+1]:
        pattern.append(2)
        i += 2
    else:
        pattern.append(1)
        i += 1

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
t = input()
i = 0
if s[0]==t[0]:
    h = True
    r = 3
    i += 1
else:
    r = 6
    i += 2
    h = False
mod = 10**9 +7
while i < n:
    if s[i]==t[i]:
        if h:
            i += 1
            r = (r*2)%mod
        else:
            i += 1
            h = True
    else:
        if h:
            r = (r*2)%mod
            h = False
        else:
            r = (r*3)%mod
        i += 2
print(r)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc081/tasks/arc081_b

# 幅1: 色数だけ縦 (3)
# 幅2: 色数だけ横と縦に2本選ぶ (6)
# 隣接している場所の色の塗り方が問題

N = int(input())
MOD = 1000000007
if N == 1:
    print(3)
    exit()
S = [list(input()) for _ in range(2)]

ans = 1
i = 0
is_x = None
while i < N:
    if i == 0:
        if S[0][i] == S[1][i]:
            ans *= 3
            i += 1
            is_x = True
        else:
            ans *= 6
            i += 2
            is_x = False
    else:
        if S[0][i] == S[1][i]:
            if is_x:
                ans *= 2
            else:
                ans *= 1
            is_x = True
            i += 1
        else:
            if is_x:
                ans *= 2
            else:
                ans *= 3
            is_x = False
            i += 2
    ans = ans % MOD
print(ans)

Submission status: Accepted

Solution code:
#!python3

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

# input
N = int(input())
S = [input() for _ in range(2)]

MOD = 10 ** 9 + 7


def main():
    ans, i = (3, 1) if S[0][0] == S[1][0] else (6, 2)
    while i < N:
        if S[0][i] == S[1][i]:
            x = 2 if S[0][i - 1] == S[1][i - 1] else 1
            i += 1
        else:
            x = 2 if S[0][i - 1] == S[1][i - 1] else 3
            i += 2
        ans = ans * x % MOD
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
s_=[input() for _ in range(2)]
mod=pow(10,9)+7
s=[1]
for i in range(n-1):
  if s_[0][i]==s_[0][i+1]:
    s[-1]+=1
  else:
    s.append(1)
ans=3*s[0]
for i in range(1,len(s)):
  if s[i-1]==1:
    ans*=2
    ans%=mod
  elif s[i]==2:
    ans*=3
    ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
S=[list(input()) for _ in range(2)]
A=""

cnt=0
for i in range(n):
    if S[0][i]==S[1][i]:
        A +="A"
    else:
        cnt +=1
        if cnt==2:
            A +="B"
            cnt=0

ans=6 if A[0]=="B" else 3
for i in range(1,len(A)):
    num=A[i-1]+A[i]
    if num=="BA":continue
    elif num=="BB":ans *=3
    else:ans *=2
    ans %=mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
mod = 10**9 + 7
ind = []
for i,(_s1,_s2) in enumerate(zip(s1,s2)):
    if _s1 == _s2:
        ind.append(i)
# print(ind)
cnt = 0
if len(ind) == 0:
    d = 6
    cnt = 2
    single = False
elif ind[0] == 0:
    d = 3
    single = True
    cnt = 1
else:
    d = 6
    single = False
    cnt = 2
        
while cnt < n:
    if cnt in ind: # * -> 1
        if single: 
            d *= 2
        else:#2->1
            d *= 1
        cnt += 1
        single = True
    else: # * -> 2
        if single:
            d *= 2
        else:
            d *= 3
        cnt += 2
        single = False
    d %= mod
    
print(d)

"""
"""