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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().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
inf = 1e10

#solve
def solve():
    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)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

count = 0
mod = (10**9) +7

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

while count < n-1:
    if (S[0][count] == S[1][count]) and (S[0][count+1] == S[1][count+1]):
        ans = ans * 2
        ans = ans % mod
        count += 1
    elif S[0][count] == S[1][count]:
        ans = ans * 2
        ans = ans % mod
        count += 1
    elif count >= n-2:
        break
    elif S[0][count+2] == S[1][count+2]:
        ans = ans
        count += 2
    else:
        ans = ans * 3
        ans = ans % mod
        count += 2
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

L = []

for i in range(n):
    if s1[i] == s2[i]:
        L.append(0)
    else:
        if i == n-1:
            continue
        if s1[i] == s1[i+1]:
            L.append(1)

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

Submission status: Accepted

Solution code:
#17:43
n = int(input())
mod = 10**9 + 7
s = input()
t = [1]
for i in range(1,n):
  if s[i-1] == s[i]:
    t[-1] += 1
  else:
    t.append(1)
#print(t)
l = len(t)
if t[0] == 2:
  ans = 6
else:
  ans = 3
for j in range(1,l):
  if t[j-1] == 1:
    ans *= 2
    ans %= mod
  elif t[j] == 2:
    ans *= 3
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    domino=[list(input()) for i in range(2)]
    mod=10**9+7

    if domino[0][0]==domino[1][0]:
        dp=[3]
        i=1
        before=True
    else:
        dp=[6]
        i=2
        before=False

    while i<n:
        if domino[0][i]==domino[1][i]:
            if before:
                nex=dp[-1]*2%mod
                dp.append(nex)
            else:
                nex=dp[-1]%mod
                dp.append(nex)
            before=True
            i+=1
        else:
            if before:
                nex=dp[-1]*2%mod
                dp.append(nex)
            else:
                nex=dp[-1]*3%mod
                dp.append(nex)
            before=False
            i+=2
    print(dp[-1])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    width = int(input())
    grid = [input() for _ in range(2)]
    mod = 1000000007
    index = 0
    answer = 0
    former_grid = 0  # 1:上下同じ，0:上下が異なる
    while index < width:
        if index == 0:
            if grid[0][index] == grid[1][index]:
                answer = 3
                former_grid = 1
            else:
                answer = 6
                former_grid = 0
                index += 1
        else:
            if former_grid:
                # 直前が縦方向に置いていたとき
                answer = answer * 2 % mod
                if not grid[0][index] == grid[1][index]:
                    index += 1
                    former_grid = 0
            else:
                # 直前が横方向に置いていたとき
                if grid[0][index] == grid[1][index]:
                    former_grid = 1
                else:
                    answer = answer * 3 % mod
                    index += 1
        index += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if s1[0] == s2[0]:
    ans = 3
    q = 1
else:
    ans = 6
    q = -1

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
S1 = input().strip()
S2 = input().strip()
compress = []
before = 0
for i in range(N):
    if before == 2:
        before = 0
        continue
    if S1[i] == S2[i]:
        compress.append(1)
        before = 1
    else:
        compress.append(2)
        before = 2

if compress[0] == 1:
    ans = 3
else:
    ans = 6
for i in range(1, len(compress)):
    if compress[i - 1] == 1 and compress[i] == 1:
        ans *= 2
    if compress[i - 1] == 1 and compress[i] == 2:
        ans *= 2
    if compress[i - 1] == 2 and compress[i] == 1:
        ans *= 1
    if compress[i - 1] == 2 and compress[i] == 2:
        ans *= 3

print(ans % MOD)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
S = [S1,S2]
mod = 10**9+7
ans = 1
i = 0
prev = None
while i < N:
    if S[0][i] == S[1][i]:
        i += 1
        if prev is None:
            ans *= 3
        elif prev:
            ans *= 2
        else:
            ans *= 1
        prev = True
    else:
        i += 2
        if prev is None:
            ans *= 6
        elif prev:
            ans *= 2
        else:
            ans *= 3
        prev = False
    ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
mo=10**9+7
n=int(input())+1
s=input()+' '

S=[]
p=s[0]
i=0
while i<n-1:
    c=s[i+1]
    if c==p:
        S+=[2]
        i+=2
    else:
        S+=[1]
        i+=1
    if i<n:
        p=s[i]

p=S.pop()
if p==1:
    ans=3
else:
    ans=6
while S:
    c=S.pop()
    if (p,c)==(1,1):
        ans*=2
    elif (p,c)==(1,2):
        ans*=2
    elif (p,c)==(2,2):
        ans*=3
    elif (p,c)==(2,1):
        ans*=1
    ans%=mo
    p=c
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = [list(input()) for i in range(2)]

mod = 10**9+7

ans = 1
check = 0
count = 0
while count < n:
    if l[0][count] == l[1][count]:
        if count == 0:
            ans *= 3
            count += 1
            check = 1
        else:
            if check == 1:
                ans *= 2
                ans %= mod
                count += 1
            elif check == 2:
                count += 1
                check = 1
    else:
        if count == 0:
            ans *= 6
            count += 2
            check = 2
        else:
            if check == 1:
                ans *= 2
                ans %= mod
                count += 2
                check = 2
            else:
                ans *= 3
                ans %= mod
                count += 2
print(ans%mod)

Submission status: Accepted

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

prev = 0  # 0 = first, 1 = vertical, 2 = horizontal

pattern = 1
skip = False
for s1, s2 in zip(S1, S2):
    if skip:
        skip = False
        continue

    if s1 == s2:
        block = 1
    else:
        block = 2
        skip = True

    if prev == 0:
        if block == 1:
            pattern = pattern * 3 % mod
            prev = 1
        else:
            pattern = pattern * 6 % mod
            prev = 2

    elif prev == 1:
        if block == 1:
            pattern = pattern * 2 % mod
            prev = 1
        else:
            pattern = pattern * 2 % mod
            prev = 2

    elif prev == 2:
        if block == 1:
            prev = 1
        else:
            pattern = pattern * 3 % mod
            prev = 2

print(pattern)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10**9+7
n = int(readline())
u = readline().rstrip().decode('utf-8')
d = readline().rstrip().decode('utf-8')

i = 0
ans = 1
touch = 0
while True:
    if i >= n:
        break
    if u[i] == d[i]:
        ans *= 3-touch
        touch = 1
        i += 1
    else:
        if touch == 2:
            ans *= 3
            i+=2
        else:
            ans *= (3-touch)*(2-touch)
            touch = 2
            i += 2

print(ans%mod)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    MOD = 1000000007
    N = int(input())
    S1 = input().strip()
    S2 = input().strip()

    ans = 1
    now = 0
    i = 0
    while i < N:
        if S1[i] != S2[i]:
            if now == 0:
                ans *= 6
            elif now == 1:
                ans *= 2
            else:
                ans *= 3
            now = 2
            i += 2
        else:
            if now == 0:
                ans *= 3
            elif now == 1:
                ans *= 2
            else:
                ans *= 1
            now = 1
            i += 1

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
mod = 10**9+7
dp = [-1] * (n)
if s1[0] == s2[0]:
    dp[0] = 1 
else:
    dp[0] = 2
for i in range(n-1):
    if dp[i] == -1:
        continue
    if s1[i] == s2[i]:
        dp[i+1] = (dp[i] * 2) % mod
        continue
    if i+2 >= n:
        break
    if s1[i+2] == s2[i+2]:
        dp[i+2] = dp[i]
    else:
        dp[i+2] = (dp[i] * 3) % mod

ans = dp[-1] if dp[-1] != -1 else dp[-2]
print((ans * 3) % mod)
# print(dp)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9+7
S = []
for i in range(2):
    t=[]
    s=input()
    for j in range(len(s)):
        t.append(s[j])
    S.append(t)
#i,jが一致するものと同じ色は使えない

l=[]
for i in range(N):
    if i>=1:
        if S[0][i]==S[0][i-1]:
            continue

    if S[0][i]==S[1][i]:
        l.append("x")
    else:
        l.append("y")
ans = 1

for i in range(len(l)):
    if i==0:
        if l[i]=="x":
            ans *= 3
        else:
            ans *= 6
        continue
    if l[i]=="x":
        if l[i-1]=="x":
            ans *= 2
        else:
            ans *= 1
    else:
        if l[i-1]=="x":
            ans *= 2
        else:
            ans *= 3
ans = ans%MOD
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=input()
B=input()
C=[]
count=1
for i in range(N-1):
  if A[i]!=A[i+1]:
    C.append(count)
    count=1
  else:
    count+=1
if N==1:
  print(3)
  exit()
  
if A[-1]==A[-2]:
  C.append(2)
else:
  C.append(1)

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

Submission status: Accepted

Solution code:
n = int(input())

s1 = list(input())
s2 = list(input())

kind = 0
next_step = 0
# 0なら前が縦、1なら前が横
pre = 0
step = 0
for _ in range(n):
  if next_step > n-1:
    break
  w1 = s1[next_step]
  w2 = s2[next_step]
  if next_step > 0:
    if w1 == w2:
      next_step += 1
      if pre == 0:
        kind *= 2
      else:
        kind *= 1
      pre = 0
    else:
      next_step += 2
      if pre == 0:
        kind *= 2
      else:
        kind *= 3
      pre = 1
  else:
    if w1 == w2:
      kind += 3
      next_step += 1
      pre = 0
    else:
      kind += 6
      next_step += 2
      pre = 1

mod = 1000000007
print(kind%mod)

Submission status: Accepted

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

def main():
    N = int(input())
    S = [list(str(input())) for _ in range(2)]
    dp = [0 for _ in range(N)]
    MOD = 10**9+7
    
    if S[0][0] == S[1][0]:
        dp[0] = 3
        for i in range(1,N):
            if S[0][i-1] != S[0][i]:
                if S[0][i-1] == S[1][i-1]:
                    dp[i] = (dp[i-1]*2)%MOD
                else:
                    if S[0][i] == S[1][i]:
                        dp[i] = dp[i-1]
                    else:
                        dp[i] = (dp[i-1]*3)%MOD
            else:
                dp[i] = dp[i-1]
    else:
        dp[0] = dp[1] = 6
        for i in range(2,N):
            if S[0][i-1] != S[0][i]:
                if S[0][i-1] == S[1][i-1]:
                    dp[i] = (dp[i-1]*2)%MOD
                else:
                    if S[0][i] == S[1][i]:
                        dp[i] = dp[i-1]
                    else:
                        dp[i] = (dp[i-1]*3)%MOD
            else:
                dp[i] = dp[i-1]
                
    print(dp[-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()+"0"
s2 = input()##要らない

i = 0

d = []#0が縦、1が横
while i<n:
    try:
        if s[i]==s[i+1]:
            d.append(1)
            i+=1
        else:
            d.append(0)
        i+=1
    except:
        break

ans = 1
#print(d)
if d[0]==0:
    ans = 3
else:
    ans = 6
mod = 10**9+7
for j in range(1,len(d)):
    if d[j]==0:
        if d[j-1]==0:
            ans*=2
    else:
        if d[j-1]==1:
            ans*=3
        else:
            ans*=2####
    ans%=mod
    

    
print(ans)

Submission status: Accepted

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

T = [[[0]*3 for i in range(3)] for j in range(N)]

for i in range(3):
  for j in range(3):
    if S[0][0]==S[1][0] and i==j or S[0][0]!=S[1][0] and i!=j:
      T[0][i][j] += 1

for i in range(1, N):
  for p0 in range(3):
    for p1 in range(3):
      for c0 in range(3):
        for c1 in range(3):
          if ((S[0][i-1]==S[0][i] and p0==c0 or S[0][i-1]!=S[0][i] and p0!=c0) and
              (S[1][i-1]==S[1][i] and p1==c1 or S[1][i-1]!=S[1][i] and p1!=c1) and
              (S[0][i]==S[1][i] and c0==c1 or S[0][i]!=S[1][i] and c0!=c1)):
            T[i][c0][c1] += T[i-1][p0][p1]
            T[i][c0][c1] %= 1000000007
ans = 0
for i in range(3):
  for j in range(3):
    ans += T[-1][i][j]
    ans %= 1000000007
print ans

Submission status: Accepted

Solution code:
# D - Coloring Dominoes

N = int(input())
S1 = input()
S2 = input()
MOD = 10**9 + 7

if S1[0] == S2[0]:
    same_domino = False
    ans = 3
else:
    same_domino = True
    ans = 3*2

for i in range(1, N):
    if S1[i] == S2[i] and S1[i-1] == S2[i-1]:
        ans *= 2
    elif S1[i] == S2[i] and S1[i-1] != S2[i-1]:
        pass
    elif S1[i] != S2[i] and same_domino:
        same_domino = False
    elif S1[i] != S2[i] and not same_domino and S1[i-1] == S2[i-1]:
        ans *= 2
        same_domino = True
    elif S1[i] != S2[i] and not same_domino and S1[i-1] != S2[i-1]:
        ans *= 3
        same_domino = True

print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
mod = 10**9+7
if s1[0]==s2[0]:
  ans = 3
  pre = '-'
  i = 1
else:
  ans = 6
  pre = '|'
  i = 2
while i<n:
  if s1[i]==s2[i]:
    if pre=='-':
      ans *= 2
      ans %= mod
    pre = '-'
    i += 1
  else:
    if pre=='-':
      ans *= 2
      ans %= mod
    else:
      ans *= 3
      ans %= mod
    pre = '|'
    i += 2
print(ans)

Submission status: Accepted

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

domino = []     # 0 : 横, 1 : 縦
flag = False
for i in range(N):
    if S1[i] == S2[i]:
        domino.append(1)
        flag = False
    else:
        if flag:
            flag = False
        else:
            domino.append(0)
            flag = True

if domino[0] == 0:
    ans = 6
else:
    ans = 3

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
mod = 1000000007
answer = 1
easy = []
i = 0

while N > i:
    if S1[i] == S2[i]:
        easy.append(1)
    else:
        easy.append(0)
        i += 1
    i += 1

for i in range(len(easy)):
    if i == 0:
        if easy[i] == 0:
            answer *= 6
        else:
            answer *= 3
    # elif i == 1:
    #     if easy[i] == 0:
    #         if easy[i-1] == 0:
    #             pass
    #         else:
    #             pass
    #     else:
    #         if easy[i-1] == 0:
    #             pass
    #         else:
    #             pass
    else:
        if easy[i] == 0:
            if easy[i-1] == 0:
                answer *= 3
            else:
                answer *= 2
        else:
            if easy[i-1] == 0:
                answer *= 1
            else:
                answer *= 2

print(answer % mod)

Submission status: Accepted

Solution code:
from itertools import groupby
MOD = 10**9+7
input()
S = input()
T = input()
def f(s): return list(map(lambda p: len(list(p[1])), groupby(s)))
A = f(f(S))
p2 = 0
p3 = 1
if len(A) > 1:
    Av = A[S[0]!=T[0]::2]
    Ah = A[S[0]==T[0]::2]
    p2 += sum(Av)-len(Av)+len(Ah)
    p3 += sum(Ah)-len(Ah)
elif S[0]==T[0]:
    Av = A[S[0]!=T[0]::2]
    p2 += sum(Av)-len(Av)
else:
    Ah = A[S[0]==T[0]::2]
    p3 += sum(Ah)-len(Ah)
    p2 += len(Ah)
print(pow(2,p2,MOD)*pow(3,p3,MOD)%MOD)

Submission status: Accepted

Solution code:
n=int(input())
A=input()
B=input()
ans=1
i=0
while i<n:
  if A[i]==B[i]:
    if i==0:
      ans=ans*3
    elif a==1:
      ans=ans*2
    else:
      ans=ans
    i=i+1
    a=1
  else:
    if i==0:
      ans=ans*6
    elif a==1:
      ans=ans*2
    else:
      ans=ans*3
    i=i+2
    a=2
print(ans%(10**9+7))

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

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

for s, t in zip(ptn[:], ptn[1:]):
    if s == 1 and t == 1:
        ans *= 2
    elif s == 1 and t == 2:
        ans *= 2
    elif s == 2 and t == 1:
        ans *= 1
    elif s == 2 and t == 2:
        ans *= 3
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007
N = int(input())
S = list(map(str, input()))
S = list(map(str, input()))
lst = [0]
i = 0
ans = 1
while i < N:
	if i == N - 1:
		lst.append(1)
		break
	if S[i] == S[i + 1]:
		lst.append(2)
		i += 2
	else:
		lst.append(1)
		i += 1
		

for i in range(len(lst) - 1):
	cur = lst[i]
	nxt = lst[i + 1]
	if cur == 0:
		if nxt == 1:
			ans *= 3
			ans %= MOD
		else:
			ans *= 6
			ans %= MOD
	elif cur == 1:
		if nxt == 1:
			ans *= 2
			ans %= MOD
		else:
			ans *= 2
			ans %= MOD
	else:
		if nxt == 1:
			ans *= 1
		else:
			ans *= 3
			ans %= MOD
			
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=[input() for _ in range(2)]
mod=1000000007
dp=[0]*n
if s[0][0]==s[1][0]:
    dp[0]=3
else:
    dp[0]=6
for i in range(1,n):
    if s[0][i]==s[1][i]:
        if s[0][i-1]==s[1][i-1]:
            dp[i]=dp[i-1]*2%mod
        else:
            dp[i]=dp[i-1]
    else:
        if s[0][i-1]==s[1][i-1]:
            dp[i]=dp[i-1]*2%mod
        else:
            if s[0][i]==s[0][i-1]:
                dp[i]=dp[i-1]
            else:
                dp[i]=dp[i-1]*3%mod
print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
s=[]
s.append(input())
s.append(input())
mod=10**9+7
state=0
parallel=0
ans=1
for i in range(n):
    if s[0][i]==s[1][i]:
        if i==0:
            ans=3
        else:
            if state==0:
                ans*=2
        state=0
    else:
        if i<2:
            if i==1:
                ans=6
                state=1
        else:
            if parallel==0:
                parallel+=1
            else:
                parallel=0
                if state==0:
                    ans*=2
                else:
                    ans*=3
                state=1
    if ans>mod:
        ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()
S2 = input()

if N == 1:
	print(3)
	sys.exit()
else:
	tmp = ""
	if S[0] == S[1]:
		ans = 6
		mode = 2
	else:
		ans = 3
		mode = 1
	tmp = S[0]
	for i in range(1, N):
		if S[i] == tmp:  # 前と同じ
			mode = 2
		else:  # 切り替わり
			if i != N-1 and S[i] == S[i+1]:
				if mode == 1:
					ans = (ans*2)%mod
				elif mode == 2:
					ans = (ans*3)%mod
			else:
				if mode == 1:
					ans = (ans*2)%mod
				elif mode == 2:
					pass
			mode = 1

		tmp = S[i]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
DS = list(input())
i = 0
DC = []
while i<N:
  cnt = DS.count(DS[i])
  DC.append(cnt)
  i += cnt

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

Submission status: Accepted

Solution code:
N=int(input())
s=input()
mod = 10**9+7
d=""
cnt=N
while cnt:
    if  cnt > 1 and s[N-cnt] ==s[N-cnt+1]:
        d += "W"
        cnt -=2
    else:
        d += "H"
        cnt -=1
if d[0] == "W":
    ans = 6
else:
    ans = 3
for i in range(1,len(d)):
    if d[i-1] =="H":
        ans *= 2
    elif d[i] =="W":
        ans *= 3
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = [''] * 2
s[0] = input().strip()
s[1] = input().strip()
mod = 10 ** 9 + 7
if n == 1:
    print(3)
    exit()
if s[0][0] == s[1][0]:
    ans = 3
    j = 1
    if s[0][1] == s[1][1]:
        ans *= 2
        j += 1
elif s[0][0] == s[0][1]:
    ans = 6
    j = 2

while j < n:
    if s[0][j] == s[1][j]:
        if s[0][j-1] == s[1][j-1]:
            ans = (ans * 2) % mod
        j += 1
    else:
        if s[0][j-1] == s[1][j-1]:
            ans = (ans * 2) % mod
        else:
            ans = (ans * 3) % mod
        j += 2

print(ans)

Submission status: Accepted

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

c = []
before = sl[0]
for s in sl[1:]:
   if before == s:
      c.append(1)
      before = ""
   elif before != s and before != "":
      c.append(0)
      before = s
   else:
      before = s
if before != "":
   c.append(0)

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

print(ans)

Submission status: Accepted

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

i=0
while i<n:
    if s1[i]==s2[i]:
        i+=1
        d.append(1)
    else:
        i+=2
        d.append(0)
l=len(d)
if d[0]==0:
    ans=6
else:
    ans=3
for i in range(1,l):
    if d[i-1]==1:
        ans*=2
        ans=ans%1000000007
    elif d[i]==0:
        ans*=3
        ans=ans%1000000007
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

N = INT()
grid = build_grid(2, N, '*', str, space=0, padding=1)

# 最初
if grid[1][1] == grid[2][1]:
    cnt = 3
else:
    cnt = 6
for i in range(2, N+1):
    # 直前が縦向きなら*2
    if grid[1][i-1] == grid[2][i-1]:
        cnt *= 2
    # 直前もここも横向きなら*3
    elif grid[1][i-1] != grid[2][i-1] and grid[1][i] != grid[2][i] and grid[1][i-1] != grid[1][i]:
        cnt *= 3
print(cnt % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]
MOD = 1000000007

def main():
	N = INT()
	A = input().rstrip()
	B = input().rstrip()

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

	print(ans%MOD)

if __name__ == '__main__':
	main()

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:
import sys

MOD = 10 ** 9 + 7

n = int(sys.stdin.readline().rstrip())
s1, s2 = sys.stdin.read().split()

def main():
    if s1[0] == s2[0]:
        i = 1
        res = 3
        flag = 0
    else:
        i = 2
        res = 6
        flag = 1
    
    while i < n:
        if s1[i] == s2[i]:
            if flag:
                res *= 1
            else:
                res = res * 2 % MOD
            flag = 0
            i += 1
        else:
            if flag:
                res = res * 3 % MOD
            else:
                res = res * 2 % MOD
            flag = 1
            i += 2
    return res

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

Submission status: Accepted

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

def ranlength(A):
    num = list(A)
    count = 1
    table = []
    for i in range(len(num)):
        try:
            if num[i] == num[i+1]:
               count = count + 1
            else:
                table.append(count)
                count = 1
        except:
            table.append(count)
    return(table)

T=ranlength(S1)
ans=T[0]*3
for i in range(1,len(T)):
    if T[i-1]==1:
        ans*=2
    elif T[i-1]==2 and T[i]==2:
        ans*=3
    ans%=MOD
print(ans)