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:
import numpy as np
n = int(input())
s1 = list(input())
s2 = list(input())

domino = np.array([s1, s2])
array = []
point = 0
while True:
    col = domino[:, point]
    if col[0] == col[1]:
        array.append(0) # X
        point += 1
    else:
        array.append(1) # Y
        point += 2
    if point >= n:
        break

total = 1
for i in range(len(array)):
    if i == 0:
        if array[i] == 0:
            total *= 3
        else:
            total *= 6
    else:
        if array[i] == 0:
            if array[i-1] == 0:
                total *= 2
            else:
                total *= 1
        else:
            if array[i-1] == 0:
                total *= 2
            else:
                total *= 3
print(total % (10**9 + 7))

Submission status: Accepted

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

if N == 1:
    print(3)
else:
    if S1[0] == S1[1]:
        left_domino = 0
        ans, i = 6, 2    
    else:
        left_domino = 1
        ans, i = 3, 1

    while i < N-1:
        if S1[i] == S1[i+1]:
            if left_domino == 0:
                ans *= 3
            else:
                ans *= 2
            left_domino = 0
            i += 2
        else:
            if left_domino != 0:
                ans *= 2
            left_domino = 1
            i += 1

    if S1[-1] == S2[-1] and left_domino != 0:
        ans *= 2

    print(ans % 1000000007)

Submission status: Accepted

Solution code:

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


state = 0
now = 0
ans = 1

while now < N:

    if state == 0 and S1[now] == S2[now]:
        ans *= 3
        now += 1
        state = 1

    elif state == 0 and S1[now] != S2[now]:
        ans *= 6
        now += 2
        state = 2

    elif state == 1 and S1[now] == S2[now]:
        ans *= 2
        now += 1
        state = 1

    elif state == 1 and S1[now] != S2[now]:
        ans *= 2
        now += 2
        state = 2

    elif state == 2 and S1[now] == S2[now]:
        ans *= 1
        now += 1
        state = 1

    elif state == 2 and S1[now] != S2[now]:
        ans *= 3
        now += 2
        state = 2

    ans %= (10 ** 9 + 7)

print (ans)

Submission status: Accepted

Solution code:
n = int(input())
s0 = input().rstrip()
s1 = input().rstrip()
v = True
index = 0
res = 3
while index < n:
    vv = s0[index] == s1[index]
    if index == 0 and vv:
        pass
    elif v:
        res *= 2
    elif not v and not vv:
        res *= 3
    index += 1 if vv else 2
    v = vv
MOD = 10**9 + 7
print(res % MOD)

Submission status: Accepted

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

col=[]
for i in range(n):
    if s[i+1]!=s[i]:
        col.append(1)
    else:
        col[-1]+=1
    
for i in range(len(col)):
    now=col[i]
    if i==0:
        ans=3 if now==1 else 6
        continue
    bef=col[i-1]
    if bef==1:
        ans*=2
        ans%=mod
    elif bef==2 and now==2:
        ans*=3
        ans%=mod

print(ans)

Submission status: Accepted

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

is_vertical = []

i = 0
while i < N:
    if i < N - 1 and S_1[i] == S_1[i + 1]:
        is_vertical.append(False)
        i += 2
    else:
        is_vertical.append(True)
        i += 1

res = 3 if is_vertical[0] else 6

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

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

Submission status: Accepted

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

mod = 10**9+7
flag = 0
joutai = 0

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

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ls1 = list(input())
    ls2 = list(input())

    if ls1[0]==ls2[0]:
        ans = 3
        i =1
        flg = "b"
    else:
        ans = 6
        flg = "a"
        i =2

    while 1:

        if i >= n:
            break

        if ls1[i]==ls2[i]:
            if flg == "a":
                flg = "b"
            else:
                ans = (ans*2)%(10**9+7)

            i += 1

        else:
            if flg == "a":
                ans = (ans*3)%(10**9+7)
            else:
                ans = (ans*2)%(10**9+7)
                flg = "a"

            i += 2
        if i >= n:
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for _ in range(2)]

if s[0][0] == s[1][0]:
    c = 3
    last = 'x'
    p = 1
else:
    c = 6
    last = 'y'
    p = 2

while p < n:
    if s[0][p] == s[1][p]:
        if last == 'x':
            c *= 2
        else:
            c *= 1
        last = 'x'
        p += 1
    else:
        if last == 'x':
            c *= 2
        else:
            c *= 3
        last = 'y'
        p += 2
    c %= 10 ** 9 + 7

print(c)

Submission status: Accepted

Solution code:
n = int(input())
s = input()+"?"
i = 0
ref = []
mod = 10**9+7
while i<n:
	if s[i]==s[i+1]:
		ref += [1]
		i += 2
	else:
		ref += [0]
		i += 1
ans = 6 if ref[0] else 3
for i,j in zip(ref,ref[1:]):
	if (1-i)&(1-j):
		ans *= 2
	elif i&(1-j):
		ans *= 1
	elif (1-i)&j:
		ans *= 2
	else:
		ans *= 3
	ans %= mod
print(ans)

Submission status: Accepted

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

s = sorted(set(S1) | set(S2))

c = [[None, None]] * N
"""
rrB
ggB

r2
r2

"""
cnt = 1
if S1[0] == S2[0]:
    # x
    # x
    cnt = 3 
    i = 1
else:
    # 012
    # xx
    # yy
    cnt = 6
    i = 2

while i < N:
    m = 0
    if S1[i] == S2[i]:
        if S1[i-1] == S2[i-1]:
            # xA
            # xA
            m= 2
        else:
            # xA
            # yA
            m= 1
        i+=1
    else:
        if S1[i-1] == S2[i-1]:
            # xAA
            # xBB
            m= 2
        else:
            # rrAA r,r,r,g,g,g,b,b,b
            # ggBB r,g,b,r,g,b,r,g,b
            #            o   o o    
            m= 3
        i+=2
    cnt = (cnt * m) % 1000000007
    #print(S1[:i])
    #print(S2[:i])
    #print(m, cnt)
    #print()
print(cnt)

Submission status: Accepted

Solution code:
def main():

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

    mod = pow(10, 9) + 7
    i = 0
    count = 1
    isSame = True
    while i < N:
        if S1[i] == S2[i]:
            if isSame:
                if i == 0:
                    count *= 3
                else:
                    count *= 2
            isSame = True
            i += 1
        else:
            if isSame:
                if i == 0:
                    count *= 6
                else:
                    count *= 2
            else:
                count *= 3
            isSame = False
            i += 2
        count %= mod
    return count

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

d=[0]
for i in range(1,n):
    if s[i-1]==s[i]:
        d[-1]+=1
    else:
        d.append(0)
ans=[3,6][d[0]]
for i in range(1,len(d)):
    t=1
    if d[i-1]==d[i]==1:
        t=3
    elif d[i-1]!=1:
        t=2
    ans=(ans*t)%mod
print(ans)

Submission status: Accepted

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

d=[0]
for i in range(1,n):
    if s[i-1]==s[i]:
        d[-1]+=1
    else:
        d.append(0)
ans=[3,6][d[0]]
for i in range(1,len(d)):
    if d[i-1]==d[i]==1:
        t=3
    elif d[i-1]==1:
        t=1
    else:
        t=2
    ans=(ans*t)%mod
print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
n=int(input())
a=input()

d=[0]
for i in range(1,n):
    if a[i-1]==a[i]:
        d[-1]+=1
    else:
        d.append(0)
ans=[3,6][d[0]]
for i in range(1,len(d)):
    if d[i-1]==d[i]==1:
        t=3
    elif d[i-1]==1 and d[i]==0:
        t=1
    else:
        t=2
    ans=(ans*t)%mod
print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
n=int(input())
a=input()
#b=input()
#1 22
#1
d=[1]
for i in range(1,n):
    if a[i-1]==a[i]:
        d[-1]+=1
    else:
        d.append(1)
ans=[3,6][d[0]-1]
for i in range(1,len(d)):
    if d[i-1]==d[i]==2:
        t=3
    elif d[i-1]==2 and d[i]==1:
        t=1
    else:
        t=2
    ans=(ans*t)%mod
print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
n=int(input())
a=input()
b=input()
#1 22
#1
d=[1]
for i in range(1,n):
    if a[i-1]==a[i]:
        d[-1]+=1
    else:
        d.append(1)
ans=[3,6][d[0]-1]
for i in range(1,len(d)):
    if d[i-1]==d[i]==1:
        t=2
    elif d[i-1]==d[i]==2:
        t=3
    elif d[i-1]==2 and d[i]==1:
        t=1
    else:
        t=2
    ans=(ans*t)%mod
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    s = [input().strip() for i in range(2)]

    MOD = 1000000007
    if N == 1:
        print(3)
        return
    ans = 0
    pre = -1
    i = 0
    while i < N-1:
        if s[0][i] == s[0][i+1]:# type 0
            if ans == 0:
                ans = 6
            else:
                if pre == 0:
                    ans *= 3
                    ans %= MOD
                else:
                    ans *= 2
                    ans %= MOD
            i += 2
            pre = 0
        else:# type 1
            if ans == 0:
                ans = 3
            else:
                if pre == 0:
                    pass
                else:
                    ans *= 2
                    ans %= MOD
            i += 1
            pre = 1
    if i == N-1:
        if pre == 1:
            ans *= 2
            ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

if n == 1 or s1[0] != s1[1]:
    ans = 3
    ind = 1
    mae = 1
else:
    ans = 6
    ind = 2
    mae = 2

while ind < n-1:
    if s1[ind] == s1[ind + 1]:
        if mae == 2:
            ans = (ans * 3) % mod
        else:
            ans = (ans * 2) % mod
        ind += 2
        mae = 2
    else:
        if mae == 2:
            ans = (ans * 1) % mod
        else:
            ans = (ans * 2) % mod
        ind += 1
        mae = 1

if ind == n-1:
    if mae == 2:
        ans = (ans * 1) % mod
    else:
        ans = (ans * 2) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
# ABC071D - Coloring Dominoes (ARC081D)
def main():
    """
    Vertical (V): a
                  a
    Horizontal (H): aa
                    bb
    """
    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:  # new dominos
            if a == b:  # V + H (2)
                ans *= 2
            else:  # H + V (1) or H + H (3)
                ans *= 1 if i == j else 3
            ans %= MOD
        a, b = i, j
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
alp = [chr(ord('a') + i) for i in range(26)]

#A
def A():
    x, a, b = LI()
    if abs(x - a) > abs(x - b):
        print("B")
    else:
        print("A")
    return

#B
def B():
    s = S()
    s = set(s)
    for i in s:
        alp.remove(i)
    if len(alp) == 0:
        print("None")
    else:
        print(alp[0])
    return

#C
def C():
    n = II()
    a = LI()
    i = 1
    a.sort(reverse=True)
    ans = []
    while i < n:
        if a[i] == a[i - 1]:
            ans.append(a[i])
            if len(ans) == 2:
                print(ans[0] * ans[1])
                return
            i += 2
        else:
            i += 1
    print(0)

#D
def D():
    n = II()
    s1 = S()
    s2 = S()
    i = 0
    f = 0
    if s1[i] == s2[i]:
        ans = 3
        i += 1
        f = 1
    else:
        ans = 6
        i += 2
    while i < n:
        if s1[i] == s2[i]:
            ans *= 2 if f else 1
            ans %= mod
            i += 1
            f = 1
            continue
        i += 2
        ans *= 2 if f else 3
        f = 0
        ans %= mod
    print(ans%mod)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

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

mod = int(1E9+7)

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
r = 1
s = 0
for i in range(N):
  p = s
  if s == 0:
    if S1[i] == S2[i]:
      r = r*3%1000000007
      s = 1
    else:
      r = r*6%1000000007
      s = 2
  elif s == 1:
    if S1[i] == S2[i]:
      r = r*2%1000000007
      s = 1
    else:
      r = r*2%1000000007
      s = 2
  elif s == 2:
    s = 3
  elif s == 3:
    if S1[i] == S2[i]:
      r = r*1%1000000007
      s = 1
    else:
      r = r*3%1000000007
      s = 2
  #print(S1[i], S2[i], p, s, r)
print(r)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
mod = 1000000007
j = 0
if S1[0] == S2[0]:
    ans = 3
else:
    ans = 6
while 1:
    if S1[j] == S2[j]:
        j += 1
        if j >= N:
            break
        ans = ans*2
    else:
        j += 2
        if j >= N:
            break
        if S1[j] != S2[j]:
            ans = ans*3
print(ans%mod)

Submission status: Accepted

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

# False->tate True->yoko
if S1[0] == S2[0] :
    ret = 3
    pre = False
    i = 1
else :
    ret = 6
    pre = True
    i = 2

while i < N :
    cur = (S1[i] != S2[i])
    if not pre :
        ret *= 2
    elif pre and cur :
        ret *= 3
    
    ret %= mod
    
    if cur :
        i += 2
    else :
        i += 1
    pre = cur
    
print(ret)

Submission status: Accepted

Solution code:
class Mint:
    MOD = 1000000007  # Must be a prime
    CACHE_FACTORIALS = [1, 1]

    def __init__(self, v):
        if self.__isally(v):
            self.v = v.v % self.MOD
        else:
            self.v = v % self.MOD

    @property
    def inv(self):
        return Mint(self.__minv(self.v))

    @classmethod
    def factorial(cls, v):
        for i in range(len(cls.CACHE_FACTORIALS), int(v) + 1):
            cls.CACHE_FACTORIALS.append(cls.CACHE_FACTORIALS[-1] * i % cls.MOD)
        return Mint(cls.CACHE_FACTORIALS[int(v)])

    @classmethod
    def perm(cls, n, r):
        if n < r or r < 0:
            return 0
        return cls.factorial(n) // cls.factorial(n - r)

    @classmethod
    def comb(cls, n, r):
        if n < r or r < 0:
            return 0
        return cls.perm(n, r) // cls.factorial(r)

    @classmethod
    def __isally(cls, v) -> bool:
        return isinstance(v, cls)

    @classmethod
    def __minv(cls, v) -> int:
        return pow(v, cls.MOD - 2, cls.MOD)

    @classmethod
    def __mpow(cls, v, w) -> int:
        return pow(v, w, cls.MOD)

    def __str__(self):
        return str(self.v)
    __repr__ = __str__

    def __int__(self):
        return self.v

    def __eq__(self, w):
        return self.v == w.v if self.__isally(w) else self.v == w

    def __add__(self, w):
        return Mint(self.v + w.v) if self.__isally(w) else Mint(self.v + w)
    __radd__ = __add__

    def __sub__(self, w):
        return Mint(self.v - w.v) if self.__isally(w) else Mint(self.v - w)

    def __rsub__(self, u):
        return Mint(u.v - self.v) if self.__isally(u) else Mint(u - self.v)

    def __mul__(self, w):
        return Mint(self.v * w.v) if self.__isally(w) else Mint(self.v * w)
    __rmul__ = __mul__

    def __floordiv__(self, w):
        return Mint(self.v * self.__minv(w.v)) if self.__isally(w) else \
            Mint(self.v * self.__minv(w))

    def __rfloordiv__(self, u):
        return Mint(u.v * self.__minv(self.v)) if self.__isally(u) else \
            Mint(u * self.__minv(self.v))

    def __pow__(self, w):
        return Mint(self.__mpow(self.v, w.v)) if self.__isally(w) else \
            Mint(self.__mpow(self.v, w))

    def __rpow__(self, u):
        return Mint(self.__mpow(u.v, self.v)) if self.__isally(u) else \
            Mint(self.__mpow(u, self.v))


N = int(input())
S1 = input()
S2 = input()
if S1[0] == S2[0]:
    ans = Mint(3)
    j = 1
else:
    ans = Mint(6)
    j = 2
while j < N:
    a = S1[j] == S2[j]
    b = S1[j-1] == S2[j-1]
    if a:
        ans *= 2 if b else 1
        j += 1
    else:
        ans *= 2 if b else 3
        j += 2

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s1=input()
s2=input()
l=[]
old="hoge"
for i in range(n):
    if s1[i]==s2[i]:
        l.append(0)
    elif s1[i]!=old:
        l.append(1)
    old=s1[i]
ans=1
flag=2
INF=10**9+7
for i in l:
    if flag==1:
        if i==1:ans=ans*3%INF
    elif flag==0:ans=ans*2%INF
    else:
        if i==0:ans*=3
        else:ans*=6
    flag=i
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())
s = input()
t = input()
#x,y = [int(i) for i in readline().split()]
MOD = 10**9+7
if s[0] == t[0]:
    ans = 3
    i = 1
    yoko = 0
else:
    ans = 6
    i = 2
    yoko = 1


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 1000000007
n = int(input())
s = [input() for _ in range(2)]

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

while col < n:
    if s[0][col] == s[1][col]:
        if s[0][col - 1] == s[1][col - 1]:
            ans *= 2
        col += 1
    else:
        if s[0][col - 1] == s[1][col - 1]:
            ans *= 2
        else:
            ans *= 3
        col += 2

    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
_ = input()
nums = [0]*N
ans = 3
c = 1
mod = 1000000007
for i in range(N-1):
    if S1[i] == S1[i + 1]:
        nums[i], nums[i + 1] = c,c
        c += 1

for i in range(N-1):
    if i > 0 and nums[i] == nums[i + 1] and nums[i] != 0 and nums[i - 1] != 0:
        ans *= 3 
    elif nums[i] == nums[i + 1] and nums[i] != 0:
        ans *= 2
    elif nums[i] == nums[i + 1] == 0:
        ans *= 2
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, S: "List[str]"):

    counter = 1
    s1, s2 = S
    pre = 0
    i = 0
    while i < N:
        if s1[i] == s2[i]:
            counter *= 3-pre
            counter %= MOD
            i += 1
            pre = 1
        else:
            if pre == 0:
                counter *= 6
                counter %= MOD
            elif pre == 1:
                counter *= 2
                counter %= MOD
            else:
                counter *= 3
                counter %= MOD

            i += 2
            pre = 2

    print(counter)

    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:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N = i_inpl()
    S1, S2 = input(), input()

    l = []
    i = 0
    while True:
        if S1[i] == S2[i]:
            l.append("X")
        else:
            l.append("Y")
            i += 1
        i += 1
        if i >= N:
            break

    if l[0] == "X":
        ans = 3
    else:
        ans = 6

    for i in range(1, len(l)):
        if l[i-1] == "X" and l[i] == "Y":
            ans *= 2
        elif l[i-1] == "X" and l[i] == "X":
            ans *= 2
        elif l[i-1] == "Y" and l[i] == "Y":
            ans *= 3
        elif l[i-1] == "X" and l[i] == "Y":
            ans *= 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

com = 1
pre = "e"
flag = True
for i in range(n):
    if s1[i] == s2[i]:
        if pre == "e":
            com *= 3
        elif pre == "v":
            com *= 2
            com %= mod
        else:
            pass
        pre = "v"
    else:
        if flag == True:
            if pre == "e":
                com *= 6
            elif pre == "v":
                com *= 2
                com %= mod
            else:
                com *= 3
                com %= mod
            flag = False
        else:
            flag = True
        pre = "h"
print(com)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from math import *

N = int(input())
s, t = input(), input()
mod = 10**9+7
ans = 1
pre = -1
for a, b in zip(s, t):
    if pre == 0:
        ans *= 2
        if a == b:
            pre = 0
        else:
            pre = 1
    elif pre == 1:
        pre = 2
    elif pre == 2:
        if a == b:
            pre = 0
        else:
            ans *= 3
            pre = 1
    else:
        if a == b:
            ans *= 3
            pre = 0
        else:
            ans *= 6
            pre = 1
    ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF=10**9+7
n=int(input())
s1=input()
s2=input()
ans=1
v=0
h=0
i=0
while i!=n:
    if v==0 and h==0:
        if s1[i]==s2[i]:
            ans=3
            v=1
            i=i+1
        else:
            ans=3*2
            h=1
            i=i+2
    elif v==1:
        if s1[i]==s2[i]:
            ans=(ans*2)%INF
            i=i+1
        else:
            ans=(ans*2)%INF
            v=0
            h=1
            i=i+2
    elif h==1:
        if s1[i]==s2[i]:
            v=1
            h=0
            i=i+1
        else:
            ans=(ans*3)%INF
            i=i+2
print(ans)

Submission status: Accepted

Solution code:
MOD  = 1000000007

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
MOD = 10 ** 9 + 7
if S1[0] == S2[0]:
  ans = 3
  i = 1
  f = True
else:
  ans = 6
  i = 2
  f = False

while i < N:
  if S1[i] == S2[i]:
    if f:
      ans = ans * 2 % MOD
    f = True
    i += 1
  else:
    if f:
      ans = ans * 2 % MOD
    else:
      ans = ans * 3 % MOD
    f = False
    i += 2

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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


main()

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
s1 = []
mod = 1000000007
i = 0
while i < n-1:
    if s[i]==s[i+1]:
        s1.append(0)
        i += 1
    else:
        s1.append(1)
    i += 1

if s[n-2]!=s[n-1]:
    s1.append(1)

if n==1:
    s1.append(1)

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

print(ans%mod)