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():
    num = int(input())
    data = [list(input()) for i in range(2)]

    kari = []
    pre = ''

    for i in range(num):
        now_data = data[0][i]
        if pre == '':
            pre = now_data
        elif now_data == pre:
            kari.append(1)
            pre = ''
        else:
            kari.append(0)
            pre = now_data
    if pre != '':
        kari.append(0)

    if kari[0]:
        ans = 6
    else:
        ans= 3
    mod = 10 ** 9 + 7
    pre_kari = kari[0]
    for i in range(1, len(kari)):
        now_kari = kari[i]
        if pre_kari and now_kari:
            ans = (ans * 3) % mod
        elif pre_kari and not now_kari:
            pass
        elif not pre_kari and not now_kari:
            ans = (ans * 2) % mod
        else:
            ans = (ans * 2) % mod
        pre_kari = now_kari


    print(ans % mod)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

i = 0
while i < len(s1):
  if s1[i] == s2[i]:
    code.append('S')
    i += 1
  else:
    code.append('D')
    i += 2

mod = 1000000007
if code[0] == 'S':
  ptn = 3
else:
  ptn = 6
for i in range(1, len(code)):
  x, y = code[i-1], code[i]

  if x == 'S' and y == 'S':
    ptn = (ptn * 2) % mod
  elif x == 'S' and y == 'D':
    ptn = (ptn * 2) % mod
  elif x == 'D' and y == 'D':
    ptn = (ptn * 3) % mod
  elif x == 'D' and y == 'S':    
    ptn = ptn
print(ptn)

Submission status: Accepted

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

mod = 10**9 + 7
dp = [0]*(N+1)

if S[0][1] == S[1][1]:
    dp[1] = 3
    i = 1
else:
    dp[1] = 6
    dp[2] = 6
    i = 2

while i <= N-1:
    if S[0][i] == S[1][i]:#pattern1
        if S[0][i+1] == S[1][i+1]:
            dp[i+1] = (dp[i]*2)%mod
            i += 1
        else:
            dp[i+1] = (dp[i]*2) %mod
            dp[i+2] = dp[i+1]
            i += 2
    else:
        if S[0][i+1] == S[1][i+1]:
            dp[i+1] = dp[i]
            i += 1
        else:
            dp[i+1] = (dp[i]*3)%mod
            dp[i+2] = dp[i+1]
            i += 2

print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
s1=input()
s2=input()
if n==1:
    print(3)
    exit()
s=""
i=0
while i<n:
    if s1[i]==s2[i]:
        s+="1"
        i+=1
    else:
        s+="2"
        i+=2
ans=0
if s[0]=="1":
    ans+=3
else:
    ans+=6
before=s[0]
for j in range(1,len(s)):
    if before=="1":
        if s[j]=="1":
            ans*=2
        else:
            ans*=2
    else:
        if s[j]=="2":
            ans*=3
    before=s[j]
print(ans%(10**9+7))

Submission status: Accepted

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

MOD = 1000000007  # type: int

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


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s, t = input(), input()
p = ''
i = 0
while i < n:
    if s[i] == t[i]:
        p += 'X'
    else:
        p += 'Y'
        i += 1
    i += 1
ans = (3 if p[0] == 'X' else 6)
for i in range(1, len(p)):
    if p[i] == 'X':
        if p[i - 1] == 'X':
            ans *= 2
        else:
            ans *= 1
    else:
        if p[i - 1] == 'X':
            ans *= 2
        else:
            ans *= 3
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
DIV=10**9+7
N=int(input())
ST=[input(), input()]
PST=[]
ptr=0
while ptr < N:
    # 1枚のとき
    if ST[0][ptr] == ST[1][ptr]:
        ptr += 1
        PST.append(0)
    # 2枚のとき
    else:
        ptr += 2
        PST.append(1)

# print(PST)

res = 3 if PST[0] == 0 else 6
for i in range(len(PST)-1):
    if PST[i] == 0 and PST[i+1] == 0:
        res = (res*2)%DIV
    elif PST[i] == 0 and PST[i+1] == 1:
        res = (res*2)%DIV
    elif PST[i] == 1 and PST[i+1] == 0:
        res = res
    elif PST[i] == 1 and PST[i+1] == 1:
        res = (res*3)%DIV

print(res)

Submission status: Accepted

Solution code:
n=int(input())
s1=list(input())
s2=list(input())
x=-1
if s1[0]==s2[0]:
  ct=3;k=1;p=1
else:
  ct=6;k=2;p=2
for i in range(k,n):
  if x!=i:
    if s1[i]==s2[i]:
      if p==1:
        ct*=2;p=1
      else:
        ct*=1;p=1
    else:
      x=i+1
      if p==1:
        ct*=2;p=2
      else:
        ct*=3;p=2
    ct%=(10**9+7)
print(ct)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
t = input()
pointer = 0
ans = [1,0]
mod = 1000000007
while pointer < n:
	if s[pointer] == t[pointer]:

		pointer += 1
		if ans[1] == 0:
			ans[0] = ans[0] *3
		elif ans[1] == 1:
			ans[0] = ans[0] *2
		#ans[0] = ans[0] % mod
		ans[1] = 1

	else:

		pointer += 2
		if ans[1] == 0:
			ans[0] = ans[0] *6
		elif ans[1] == 1:
			ans[0] = ans[0] *2
		elif ans[1] == 2:
			ans[0] = ans[0] *3
		#ans[0] = ans[0] % mod
		ans[1] = 2

print(ans[0] % mod)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()
    T = ST()
    contin = False
    equal = False
    if S[0] == T[0]:
        ans = 3
        equal = True
    else:
        ans = 6
        contin = False
    start = 1 + (S[0] != T[0])
    for s, t in zip(S[start:], T[start:]):
        if s == t:
            if equal:
                ans *= 2
            else:
                pass
            equal = True
        else:
            if contin:
                if equal:
                    ans *= 2
                else:
                    ans *= 3
                contin = False
                equal = False
            else:
                contin = True
        ans %= mod
        
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)



def main():
    input()
    x=[len(list(v))for k,v in groupby(input())]
    if x[0]==1:
        ans=3
    else:
        ans=6
    mod=10**9+7
    for i in range(1,len(x)):
        if x[i-1]==1 and x[i]==1:
            ans*=2%mod
        elif x[i-1]==1 and x[i]==2:
            ans*=2%mod
        elif x[i-1]==2 and x[i]==2:
            ans*=3%mod
    print(ans%mod)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

MOD = 1000000007

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
T = sys.stdin.readline().rstrip()

ans = 1
# 次横だったら掛ける何通りするか
next_h = 6
# 次縦だったら
next_v = 3
i = 0
while i < N:
    s, t = S[i], T[i]
    if s != t:
        # 横
        ans *= next_h
        next_h = 3
        next_v = 1
        i += 2
    else:
        # 縦
        ans *= next_v
        next_h = 2
        next_v = 2
        i += 1
    ans %= MOD

print(ans)

Submission status: Accepted

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

mod=1000000007

str=""
i=0
while i<N:
	if S1[i]==S2[i]:
		str+="t"
		i+=1
	else:
		str+="y"
		i+=2


l=len(str)

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

for i in range(l-1):
	now=str[i]
	next=str[i+1]
	if now=="t" and next=="y":
		ans*=2
	elif now=="t" and next=="t":
		ans*=2
	elif  now=="y" and next=="y":
		ans*=3
	elif  now=="y" and next=="t":
		ans*=1
	ans%=mod

print ans

Submission status: Accepted

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

Submission status: Accepted

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

li = []
c = 0
for i in range( len(S) ):
  if ( c < len(S)-1):
    if S[c]==S[c+1]:
      li.append(2)
      c +=2
    else:
      li.append(1)
      c+=1
  else:
    li.append(1)
    c+=1
  if (c==len(S)):
    break

if (li[0]==1):
  s = 3
else:
  s = 6

MOD = 1000000007
for i in range( len(li)-1 ):
  if ( li[i]==1 and li[i+1]==1 ):
    s = (s*2)%MOD
  if ( li[i]==1 and li[i+1]==2 ):
    s = (s*2)%MOD
  if ( li[i]==2 and li[i+1]==1 ):
    s = s
  if ( li[i]==2 and li[i+1]==2 ):
    s = (s*3)%MOD
print ( s%MOD )

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)%mod
    else:
        j += 2
        if j >= N:
            break
        if S1[j] != S2[j]:
            ans = (ans*3)%mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    S1 = list(_ for _ in input())
    S2 = list(_ for _ in input())
    S1_used = [-1]*N
    S2_used = [-1]*N
    
    if S1[0] == S2[0]:
        ans = 3
    else:
        ans = 6
    for i in range(1,N):
        if S1[i] != S1[i-1] and S1[i] != S2[i]:
            if S1[i-1] == S2[i-1]:
                ans *=2
            else:
                ans *=3
        elif S1[i] != S1[i-1] and S1[i] == S2[i]:
            if S1[i-1] == S2[i-1]:
                ans *=2
    print(ans%MOD)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(N: int, S: "List[str]"):
    conv = []
    i = 0
    while i < N:
        c, o = (0, 1) if S[0][i] == S[1][i] else (1, 2)
        conv.append(c)
        i += o

    ret = 3 if conv[0] == 0 else 6
    for b, c in zip(conv, conv[1:]):
        if b == 0 and c == 0:
            ret *= 2
        elif b == 0 and c == 1:
            ret *= 2
        elif b == 1 and c == 0 :
            ret *= 1
        elif b == 1 and c == 1:
            ret *= 3
    return ret % MOD

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]"
    result = solve(N, S)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = [''] * 2
S[0] = input()
S[1] = input()

MOD = 10 ** 9 + 7

if S[0][0] == S[1][0]:
    ans = 3
    row = True
    skip = False
else:
    ans = 6
    row = False
    skip = True
for i in range(1, N):
    if not skip:
        if S[0][i] == S[1][i]:
            if row:
                ans *= 2
            else:
                ans *= 1
            row = True
        else:
            if row:
                ans *= 2
            else:
                ans *= 3
            row = False
            skip = True
        ans %= MOD
    else:
        skip = False

print(ans)

Submission status: Accepted

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

i = 1
if S1[0] == S2[0]:
    ans = 3
    state = 0
else:
    i+= 1
    ans = 6
    state = 1
mod  = 10**9 + 7
while N > i:
    if S1[i] != S2[i] and state == 0:
        ans *= 2
        i+=2
        state = 1
    elif S1[i] != S2[i] and state == 1:
        ans *= 3
        i+=2
    elif S1[i] == S2[i] and state == 0:
        ans *= 2
        i+= 1
    elif S1[i] == S2[i] and state == 1:
        ans *= 1
        i+=1
        state = 0

    ans %= mod
print(ans)

Submission status: Accepted

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

skip = False
double = False
for i in range(N):
    if skip:
        skip = False
        continue
    if i == 0:
        if S1[i] == S2[i]:
            ans = 3
        else:
            ans = 6
            skip = True
            double = True
    else:
        if S1[i] == S2[i]:
            if double:
                ans *= 1
            else:
                ans *= 2
            double = False            
        else:
            if double:
                ans *= 3
            else:
                ans *= 2
            skip = True
            double = True


ans = ans % 1000000007
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s1 = input()
s2 = input()
dirct = []
i = 0
while i<n:
    if s1[i] ==s2[i]:
        dirct.append(True)
        i+=1
        continue
    else:
        i+=2
        dirct.append(False)
        continue
dp = [0]*52
MAX = 1000000007
for i in range(len(dirct)):
    if i == 0:
        if dirct[0]:
            dp[0]=3
        else:
            dp[0]=6
        continue
    #| |
    if dirct[i] and dirct[i-1]:
        dp[i] = (dp[i-1]*2)%MAX
        continue
    #= |
    if dirct[i] and (not dirct[i-1]):   
        dp[i] = dp[i-1]
        continue
    #| =
    if (not dirct[i]) and dirct[i-1]:
        dp[i] = (dp[i-1]*2)%MAX
        continue
    #= =
    if (not dirct[i]) and (not dirct[i-1]):
        dp[i] = (dp[i-1]*3)%MAX

print(dp[len(dirct)-1]%MAX)

Submission status: Accepted

Solution code:
n = int(input())
a = input().rstrip()
b = input().rstrip()
pattern = []
l = 0
while l < n:
    if a[l] == b[l]:
        pattern.append(1)
        l += 1
    else:
        pattern.append(0)
        l += 2

ans = 1
for i in range(len(pattern)):
    if i == 0:
        if pattern[i] == 1:
            ans *= 3
        else:
            ans *= 6
        continue
    if pattern[i-1] == 1 and pattern[i] == 1:
        ans *= 2
    elif pattern[i-1] == 0 and pattern[i] == 0:
        ans *= 3
    elif pattern[i-1] == 1 and pattern[i] == 0:
        ans *= 2
        
print(ans % (10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
A = input()
B = input()
ans = 3
for i in range(len(A) - 1):
  if A[i] == B[i] and A[i + 1] == B[i + 1]:
    ans *= 2
  if A[i] == B[i] and A[i + 1] != B[i + 1]:
    ans *= 2
  if A[i] != B[i] and A[i + 1] != B[i + 1] and A[i] != A[i + 1]:
    ans *= 3
  if A[i] != B[i] and A[i + 1] != B[i + 1] and A[i] == A[i + 1] and i == 0:
    ans *= 2
  ans %= 1000000007
print(ans)

Submission status: Accepted

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

ans = 1
if S[0] == T[0]:
    flag = 'tate'
    ans *= 3
else:
    flag = 'yoko'
    ans *= 6
    
for i in range(1, N):
    if S[i] == T[i]:
        if flag == 'tate':
            ans *= 2
            flag = 'tate'
        elif flag == 'yoko' or flag == 0:
            flag = 'tate'
    else:
        if flag == 'tate':
            ans *= 2
            flag = 'yoko'
        elif flag == 'yoko':
            flag = 0
        elif flag == 0:
            ans *= 3
            flag = 'yoko'

print(ans % mod)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(str, input().strip())) for _ in range(2)]
    MOD = 10**9 + 7

    D = []
    flag = False
    for i in range(N):
        if A[0][i] != A[1][i] and flag:
            D.append('h')
            flag = False
        elif A[0][i] != A[1][i]:
            flag = True
        else:
            D.append('v')

    if D[0] == 'h':
        ans = 6
    else:
        ans = 3

    for i in range(1, len(D)):
        if D[i-1] == 'v' and D[i] == 'h':
            ans *= 2
        elif D[i-1] == 'v' and D[i] == 'v':
            ans *= 2
        elif D[i-1] == 'h' and D[i] == 'h':
            ans *= 3
        else:
            ans *= 1

    return ans % MOD


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

Submission status: Accepted

Solution code:
N = int(input())
S_1 = list(input())
S_2 = list(input())
if S_1[0] == S_2[0]:
	before_style = 1
	pattern = 3
	i = 1
else:
	before_style = 2
	pattern = 6
	i = 2
	

while i < N:
	if S_1[i] == S_2[i]:
		if before_style == 1:
			before_style = 1
			i += 1			
			pattern *= 2
		else:
			before_style = 1
			i += 1	
			pattern *= 1		
	else:
		if before_style == 1:
			before_style = 2
			i += 2
			pattern *= 2
		else:
			before_style = 2
			i += 2
			pattern *= 3


print(pattern % 1000000007)

Submission status: Accepted

Solution code:
N=int(input())
mod=1000000007
S=input()
data=[]
exist=set()
for s in S:
    if s in exist:
        data[-1]+=1
    elif s not in exist:
        data.append(1)
        exist|={s,}
if data[0]==1:
    ans=3
elif data[0]==2:
    ans=6
for i in range(1,len(data)):
    if (data[i-1],data[i])==(1,1):ans=(ans*2)%mod
    elif (data[i-1],data[i])==(1,2):ans=(ans*2)%mod
    elif (data[i-1],data[i])==(2,1):ans=ans
    elif (data[i-1],data[i])==(2,2):ans=(ans*3)%mod
print(ans)

Submission status: Accepted

Solution code:
def coloring_dominoes(N: int, S1: str, S2: str)->int:
    MOD = 1000000007

    if S1[0] == S2[0]:
        offset = 1
        ret = 3
        before_dir = S1[0] == S2[0]
    else:
        offset = 2
        ret = 3 * 2
        before_dir = S1[0] == S2[0]

    i = offset
    while i < N:
        current_dir = S1[i] == S2[i]

        if before_dir and current_dir:
            ret *= 2
            i += 1
        elif before_dir and not current_dir:
            ret *= 2 * 1
            i += 2
        elif not before_dir and current_dir:
            ret *= 1
            i += 1
        else:
            ret *= 3
            i += 2

        ret %= MOD
        before_dir = current_dir

    return ret


if __name__ == "__main__":
    N = int(input())
    S1 = input()
    S2 = input()
    ans = coloring_dominoes(N, S1, S2)
    print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

N = int(input())
S = [input() for _ in range(2)]
P = []
for i in range(2):
    note = 0
    s = ""
    for j in range(N):
        if S[i][j] == note:
            continue
        s += S[i][j]
        note = S[i][j]
    P.append(s)
f = []
for j in range(len(P[0])):
    t = P[0][j]; b = P[1][j]
    if t == b:
        f.append(1)
    else:
        f.append(0)

if f[0] == 1:
    ans = 3
else:
    ans = 6
for j in range(1,len(P[0])):
    if f[j] == 1:
        if f[j-1] == 1:
            ans *= 2
        else:
            pass
    else:
        if f[j-1] == 1:
            ans *= 2
        else:
            ans *= 3
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    N = int(input())
    S = [input() for _ in range(2)]
    dp = [0] * N
    if S[0][0] == S[1][0]:
        dp[0] = 3
    else:
        dp[0] = 3 * 2
    for i in range(1, N):
        if S[0][i] == S[0][i-1]:
            dp[i] = dp[i-1] % MOD
            continue
        l = 1 if S[0][i-1] == S[1][i-1] else 2
        r = 1 if S[0][i] == S[1][i] else 2
        if l == 1:
            dp[i] = dp[i-1] * 2 % MOD
        elif r == 2:
            dp[i] = dp[i-1] * 3 % MOD
        else:
            dp[i] = dp[i-1] % MOD
    print(dp[N-1])


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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
d = defaultdict(int)
a = LI()
for i in a:
    d[i] += 1
d = list(d.items())
d.sort(key = lambda x:-x[0])
l = 0
k = 0
for i,j in d:
    if j >= 2:
        if l == 0:
            l = i
        else:
            k = i
        if j >= 4:
            k = i
    if k != 0:break
print(l*k)
"""

#D
n = I()
s1 = S()
s2 = S()
ans = 0
i = 0
key = 1
d = defaultdict(int)
while i < n:
    if s1[i] == s2[i]:
        if not d[s1[i]]:
            d[s1[i]] = 1
            if i == 0:
                ans = 3
            else:
                if key:
                    ans *= 2
        key = 1
    else:
        if not d[s1[i]] and not d[s2[i]]:
            d[s1[i]] = 1
            d[s2[i]] = 1
            if i == 0:
                ans = 6
            else:
                if key:
                    ans *= 2
                else:
                    ans *= 3
        if not d[s1[i]]:
            d[s1[i]] = 1
            if not key:
                ans *= 2
        if not d[s2[i]]:
            d[s2[i]] = 1
            if not key:
                ans *= 2
        key = 0
        i += 1
    i += 1
    ans %= mod
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
s1= input()
s2= input()
ans =3
if s1[0]!=s2[0]:
  ans = 6
  k = 2
  tate_flag = False
else:
  ans = 3
  k = 1
  tate_flag = True
  
flag =False
for i in range(k,n):
  if flag:
    flag = False
  elif s1[i]!=s2[i] and tate_flag:
    ans = ans * 2
    flag = True
    tate_flag = False
  elif s1[i]!=s2[i] and not tate_flag:
    ans = ans * 3
    flag = True
    tate_flag = False
  elif s1[i]==s2[i] and tate_flag:
    ans = ans *2
    tate_flag = True
  else:
    ans =ans*1
    tate_flag = True
  ans = ans % 1000000007
print(ans)

Submission status: Accepted

Solution code:
#071-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
n=I()
s1=list(S())
s2=SL()
mod=pow(10,9)+7
s=[]
i=0
if n==1:
    ans=3
elif n==2:
    ans=6
else:
    while i<=n-2:
        if s1[i]==s1[i+1]:
            s.append(2)
            i+=2
        else:
            s.append(1)
            i+=1
    if s1[-1]!=s1[-2]:
        s.append(1)
    if s[0]==1:
        ans=3
    else:
        ans=6
    for i in range(1,len(s)):
        if s[i-1]==1:
            ans*=2
        else:
            if s[i]==2:
                ans*=3
        ans=ans%mod
print(ans)

Submission status: Accepted

Solution code:
x=0
N=int(input())
S=[input() for _ in range(2)]
mod=10**9+7

l=[]
while x<N:
    if S[0][x]==S[1][x]:
        l.append(1)
        # たて
        x+=1
    else:
        l.append(0)
        # 横
        x+=2

v=1
for i,j in enumerate(l):
    if not i:
        v=3 if j else 6
    else:
        if l[i-1]:
            v*=2
        elif not j:
            v*=3
    v%=mod

print(v)

Submission status: Accepted

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

p=0
prev=0
ans=3

if S1[p]==S2[p]:
    p+=1
    prev=1
else:
    p+=2
    prev=2
    ans*=2

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = int(input())
x=list(input())
y=list(input())
s = 1
i=0
if x[0] == y[0]:
    s*=3
    i+=1
else:
    s*=6
    i+=2
while i <a :
    if x[i-1] == y[i-1] and x[i]==y[i]:
        s*=2
    elif x[i-1] == y[i-1] and x[i]!=y[i]:
        s*=2
    elif x[i-1] != y[i-1] and x[i] !=y[i]:
        s*=3
    if not x[i] == y[i]:
        i+=1
    i+=1
print(s%1000000007)

Submission status: Accepted

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

i = 0
while i < n:
    if i == 0:
        if s1[i] == s2[i]:
            a = 3
            i += 1
            pre = 0
        else:
            a = 6
            i += 2
            pre = 1
    else:
        if pre == 0:
            a *= 2
            if s1[i] == s2[i]:
                i += 1
            else:
                pre = 1
                i += 2
        elif pre == 1:
            if s1[i] == s2[i]:
                pre = 0
                i += 1
            else:
                a *= 3
                i += 2

print(a%1000000007)

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
if s1[0] == s2[0]:
    preState = 0
    ans = 3
    index = 1
else:
    preState = 1
    ans = 6
    index = 2
while index < n:
    if s1[index] == s2[index]:
        if preState == 0:
            ans *= 2
        else:
            pass
        preState = 0
        index += 1

    else:
        if preState == 0:
            ans *= 2
        else:
            ans *= 3
        preState = 1
        index += 2
print(ans % 1000000007)

Submission status: Accepted

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

if S[0][0] == S[1][0]:
    last_kind = 0
    ans = 3
    i = 1
else:
    last_kind = 1
    ans = 6
    i = 2
while i < N:
    if last_kind == 0 and S[0][i] == S[1][i]:
        ans *= 2
        last_kind = 0
        i += 1
    elif last_kind == 1 and S[0][i] == S[1][i]:
        last_kind = 0
        i += 1
    elif last_kind == 0 and S[0][i] == S[0][i+1]:
        ans *= 2
        last_kind = 1
        i += 2
    elif last_kind == 1 and S[0][i] == S[0][i+1]:
        ans *= 3
        last_kind = 1
        i += 2
    ans %= M

print(ans)

Submission status: Accepted

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

if S1[0] == S2[0]:
    result = 3
    skip   = False
    tate   = True
else:
    result = 6
    skip   = True
    tate   = False

for n in range(1, N):
    if skip == True:
        skip = False
        continue
    elif S1[n] == S2[n]:
        if tate == True:
            result *= 2
        else:
            tate = True
    else:
        if tate == True:
            result *= 2
        else:
            result *= 3
        skip    = True
        tate    = False
    if result  >= 1000000007:
        result %= 1000000007

print(result)