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 examC():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] += 1
    a = [0,0]
    for key,i in d.items():
        if i>=4:
            if a[1]<key:
                a = [key,key]
            elif a[0]<key:
                a = [key,a[1]]
        elif i>=2:
            if a[1]<key:
                a = [a[1],key]
            elif a[0]<key:
                a = [key,a[1]]
    ans = a[0]*a[1]
    print(ans)
    return

def examD():
    N = I()
    S = [SI() for _ in range(2)]
    ans = 1
    flag = 0
    i = 0
    while(i<N):
        if S[0][i]==S[1][i]:
            if flag==1:
                ans *= 2
            elif flag==0:
                ans *= 3
            flag = 1
        else:
            if flag==0:
                ans *= 6
            elif flag==1:
                ans *= 2
            elif flag==2:
                ans *= 3
            flag = 2
        i += flag
        ans %= mod
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
N = int(input())
S = input()
i = 0
l = []
while i < N:
    if i + 1 < N:
        if S[i] == S[i + 1]:
            i += 2
            l.append(2)
            continue
    i += 1
    l.append(1)

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

Submission status: Accepted

Solution code:


N = int(input())
s1 = input()
s2 = input()
S = [s1, s2]
MOD = 10**9+7

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


x = 0
ans = 1
while x <= N-1:
    # 縦の場合
    if S[0][x] == S[1][x]:
        if x == 0:
            ans *= 3
            x += 1
        else:
            # 手前のやつが縦かどうかに依存
            if S[0][x-1] == S[1][x-1]:
                ans *= 2
                x += 1
            else:
                #横二段の後に縦なので、横２段以外の１色
                x += 1
    # 横の場合
    else:
        if x == 0:
            ans *= 3*2
            x += 2
        else:
            # 手前のやつが縦かどうかに依存
            if S[0][x-1] == S[1][x-1]:
                ans *= 2*1
                x += 2
            else:
                ans *= 3
                x += 2
    ans %= MOD
        
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = int(input())
S = input()
S2 = input()
lst = []
i = 0
while i < N:
    if i == N-1 or S[i] != S[i+1]:
        lst.append(1)
        i += 1
    else:
        lst.append(2)
        i += 2
if lst[0] == 1:
    ans = 3
else:
    ans = 6
for j in range(1, len(lst)):
    if lst[j-1] == 1:
        ans *= 2
    elif lst[j-1] == 2 and lst[j] == 2:
        ans *= 3
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
M = 10**9+7
N=int(input())
S=input().strip()
T=input().strip()
for i in range(N):
    if i == 0:
        if S[i] == T[i]:
            r = 3
            tmp = 1
        else:
            r = 6
            tmp = 0
        continue
    if S[i] == S[i-1]:
        tmp = 0
        continue
    if tmp:
        r = r*2%M
    elif S[i] != T[i]:
        r = r*3%M
    tmp=1
print(r)

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
gomi = str(input())
num = [1]
for i in range(n-1):
  if s[i] == s[i+1]:
    num[-1]+=1
  else:
    num.append(1)
ans = 1
before = 0
for i in range(len(num)):
  if num[i] == 2:
    if before == 1:
      ans *= 2
      before = 2
    elif before == 2:
      ans *= 3
    else:
      ans *= 6
      before = 2
  else:
    if before == 1:
      ans *= 2
    elif before == 2:
      before = 1
    else:
      ans *= 3
      before = 1
  ans %= 10 ** 9 + 7
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
s1 = input()
s2 = input()
ans = 1
being_horizontal = False
was_horizontal = False
was_vertical = False
MOD = 10**9+7
for i in range(N):

    if not was_horizontal and not being_horizontal and not was_vertical: # 開始時
        if s1[i] != s2[i]:
            ans *= 6
            being_horizontal = True
        else:
            ans *= 3
            was_vertical = True
    elif being_horizontal:
        being_horizontal = False
        was_horizontal = True
    elif was_horizontal and s1[i] == s2[i]:
        was_horizontal = False
        was_vertical = True
    elif was_horizontal and s1[i] != s2[i]:
        ans *= 3
        being_horizontal = True
        was_horizontal = False
    elif was_vertical and s1[i] == s2[i]:
        ans *= 2
        was_vertical = True
    elif was_vertical and s1[i] != s2[i]:
        ans *= 2
        was_vertical = False
        being_horizontal = True
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
bbn=1000000007
	
#+++++

		
def main():
	n = int(input())
	sa = input()
	sb = input()
	ll=[]
	i=0
	while i < n:
		if sa[i] == sb[i]:
			ll.append(1)
		else:
			ll.append(2)
			i+=1
		i+=1
	
	val= 3 if ll[0]==1 else 6
	vv=[[2,2],[1,3]]
	for pre, now in zip(ll,ll[1:]):
		val *= vv[pre-1][now-1]
		val = val % bbn
		
	print(val)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
pro = 1
i = 0
if S1[0] != S2[0]:
    pro = 6
    i = 2
    two = True
else:
    pro = 3
    i = 1
    two = False
while i < N:
    if S1[i] != S2[i]:
        i += 2
        if two:
            pro *= 3
        else:
            pro *= 2
        two = True
    else:
        i += 1
        if not two:
            pro *= 2
        two = False
print(pro%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
#https://atcoder.jp/contests/arc081/tasks/arc081_b
#D - Coloring Dominoes
"""
need to consider the case that ticket is not enough to lower everything
"""

N = gi()
S1 = gw()
S2 = gw()

i = 1
ans = 3

if (N > 1 and S1[0] == S1[1]):
    i = 2
    ans = 6

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

print(ans)

Submission status: Accepted

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

p=[]
i=0
while i<N:
    if S1[i]==S2[i]:
        p.append(0)
        i+=1
    else:
        p.append(1)
        i+=2

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S1=input()
S2=input()
LIST=[]
i=0
while(N>i):
    if(S1[i]==S2[i]):
        LIST.append(1)
    else:
        LIST.append(0)
        i+=1
    i+=1

s=1
t=9
for i in range(len(LIST)):
    if(t==0):
        if(LIST[i]==0):
            s*=3
        else:
            s*=1
    elif(t==1):
        if(LIST[i]==0):
            s*=2
        else:
            s*=2
    else:
        if(LIST[i]==0):
            s*=6
        else:
            s*=3
    t=LIST[i]
    s=s%1000000007
print(s)

Submission status: Accepted

Solution code:
mod=10**9+7

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

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

while i<N:
    if S1[i]!=S2[i]:
        if S1[i-1]!=S2[i-1]:
            ans=ans*3%mod
        else:
            ans=ans*2%mod
        i+=2
    elif S1[i]==S2[i]:
        if S1[i-1]==S2[i-1]:
            ans=ans*2%mod
        i+=1

print(ans)

Submission status: Accepted

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

mod=10**9+7

if S1[0]==S2[0]:
    cnt=3
    i=1
    f=0
if S1[0]!=S2[0]:
    cnt=6
    i=2
    f=1

while i<N:
    if S1[i]==S2[i]:
        if f==0:
            cnt=(cnt*2)%mod
        elif f==1:
            cnt=(cnt*1)%mod
        i+=1
        f=0
    elif S1[i]!=S2[i]:
        if f==0:
            cnt=(cnt*2)%mod
        elif f==1:
            cnt=(cnt*3)%mod
        i+=2
        f=1

print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
S=list(input())
T=list(input())
state=[]
lim=1000000007
i=0
while i<N:
    if S[i] == T[i]:
        state.append(0)
        i+=1
    else:
        state.append(1)
        i+=2
if state[0]==0:
    ans=3
else:
    ans=6
for i in range(1,len(state)):
    if state[i] == 1 and state[i-1] == 1:
        ans = (ans * 3) % lim
    elif state[i] == 1 and state[i-1] == 0:
        ans = (ans * 2) % lim
    elif state[i] == 0 and state[i-1] == 1:
        pass
    elif state[i] == 0 and state[i-1] == 0: 
        ans = (ans * 2) % lim
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
MOD = 10 ** 9 + 7
S1 = rs()
S2 = rs()
color = [None] * N

answer = 1
pattern = 0 #１つ前の列の色の種類

for i in range(N):
    if color[i] != None:
        continue
    if S1[i] == S2[i]:
        answer *= 3 - pattern
        pattern = 1
    else:
        answer *= [6, 2, 3][pattern]
        color[i+1] = 1
        pattern = 2

print(answer%MOD)
#08

Submission status: Accepted

Solution code:
N = int(input())
A = [input() for _ in range(2)]
mod = 10**9+7
ptn = []
for i in range(N-1):
    if A[0][i] == A[0][i+1]:
        ptn.append("=")
    elif A[0][i] == A[1][i]:
        ptn.append("|")
if A[0][-1] == A[1][-1]:
    ptn.append("|") 

if ptn[0] == "|":
    ans = 3
else:
    ans = 6
for i in range(1,len(ptn)):
    if (ptn[i-1],ptn[i]) == ("|","|"):
        ans = ans * 2 % mod
    elif (ptn[i-1],ptn[i]) == ("=","="):
        ans = ans * 3 % mod
    elif (ptn[i-1],ptn[i]) == ("|", "="):
        ans = ans * 2 % mod
    else:
        continue
print(ans)

Submission status: Accepted

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

ty=[]
i=0
while i<N:
  if S1[i]==S2[i]:
    ty.append(1)
    i+=1
  else:
    ty.append(0)
    i+=2
    
if ty[0]==0:
  ans=6
else:
  ans=3
  
for i in range(1,len(ty)):
  if ty[i-1]==0:
    if ty[i]==0:
      ans=(ans*3)%mod
  else:
    ans=(ans*2)%mod
    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    s1=input()
    s2=input()
    if s1[0]==s2[0]:
        ans=3
        index=1
        key=0
    else:
        ans=6
        index=2
        key=1
    while index<=n-1:
        if s1[index]==s2[index]:
            if key==0:
                ans=(ans*2)%mod
                index+=1
            else:
                key=0
                index+=1
                continue
        else:
            if key==0:
                ans=(ans*2)%mod
                index+=2
                key=1
            else:
                ans=(ans*3)%mod
                index+=2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N = int(input())
S1 = input()
S2 = input()
pattern = []
i = 0
while i < N:
    if i == N - 1 or S1[i] != S1[i+1]:
        pattern.append(1)
        i += 1
    else:
        pattern.append(2)
        i += 2
dp = [1 for _ in range(len(pattern) + 1)]
for i in range(len(pattern)):
    if i == 0:
        if pattern[0] == 1:
            dp[i+1] = 3
        else:
            dp[i+1] = 6
    elif pattern[i-1] == 1:
        dp[i+1] = (dp[i] * 2) % MOD
    elif pattern[i-1] == pattern[i] == 2:
        dp[i+1] = (dp[i] * 3) % MOD
    else:
        dp[i+1] = dp[i]
print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
s_1=str(input())
s_2=str(input())
i=0
if s_1[0]==s_2[0]:
    ans=3
    c=1
    i+=1
else:
    ans=6
    c=2
    i+=2
while i<n:
    if s_1[i]==s_2[i]:
        if c==1:
            ans=ans*2%(1000000007)
        c=1
        i+=1
    else:
        if c==2:
            ans=ans*3%(1000000007)
        else:
            ans=ans*2%(1000000007)
        c=2
        i+=2
print(ans%(1000000007))

Submission status: Accepted

Solution code:
N = int(input())
S = []
S += [input()]
S += [input()]

idx = 0
if S[0][idx]==S[1][idx]:
    flag = 0
    cnt = 3
    idx +=1
elif S[0][idx]!=S[1][idx]:
    flag = 1
    cnt = 6
    idx +=2

while idx<N:
  tmp = [S[0][idx],S[1][idx]]
  if flag == 0:
    if S[0][idx]==S[1][idx]:
      cnt *=2
      flag = 0
      idx +=1
    else:
      cnt *=2
      flag =1
      idx +=2
  elif flag ==1:
    if S[0][idx]==S[1][idx]:
      cnt *=1
      flag = 0
      idx +=1
    else :
      cnt *=3
      flag =1
      idx +=2

print(cnt%1000000007)

Submission status: Accepted

Solution code:
N = int(input())
s1 = input()
s2 = input()
MOD = 1000000007
state = -1
ans = 1
flag = False
for i in range(N):
  if i+1<N:
    if s1[i]==s1[i+1]:
      flag = True
      continue
    if flag:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 3
      else:
        ans *= 6
      state = 2
    else:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 1
      else:
        ans *= 3
      state = 1
    flag = False
  else:
    if flag:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 3
      else:
        ans *= 6
    else:
      if state==1:
        ans *= 2
      elif state==2:
        ans *= 1
      else:
        ans *= 3
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
U = list(input())
input()

mod = 1000000007

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

idx = 0
li = []
while idx < len(U) - 1:
  if U[idx] == U[idx + 1]:
    li.append(2)
    idx += 1
  else:
    li.append(1)
  idx += 1
if U[-1] != U[-2]:
  li.append(1)

ans = 1
pre = li[0]

if pre == 1:
  ans = ans * 3 % mod
else:
  ans = ans * 6 % mod
  
for i in li[1:]:
  if pre == 1:
    ans = ans * 2 % mod
  else:
    if i == 2:
      ans = ans * 3 % mod
  pre = i

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline

N = int(input())
S = [list(input())[: -1] for _ in range(2)]
#print(S)
h = 0
v = 0
x = [0] * N
mod = 10 ** 9 + 7
for i in range(N):
  if S[0][i] == S[1][i]:
    v += 1
    x[i] = 1
for i in range(N - 1):
  if S[0][i] == S[0][i + 1]:
    h += 1
    x[i] = 0
res = 3
i = 0
if x[0] == 0:
  i += 2
  res *= 2
else: i += 1
while i < N:
  #print(i)
  if x[i] == 0:
    if x[i - 1] == 0:
      res *= 3
      res %= mod
    else:
      res *= 2
      res %= mod
    i += 1
  else:
    if x[i - 1] != 0:
      res *= 2
      res %= mod
  i += 1
#print(h, v)
#print(x)
print(res)

Submission status: Accepted

Solution code:
md = 10**9 + 7
N = int(input())

S1 = input()
S2 = input()

if S1[0] == S2[0]:
	res = 3
	i = 1
	form = "S"
else:
	res = 6
	i = 2
	form = "B"

while i < N:
	if S1[i] == S2[i]:
		if form == "S":
			res = res*2
		form = "S"
		i += 1
	else:
		if form == "S":
			res = res*2
		else:
			res = res*3
		form = "B"
		i += 2

print(res%md)

Submission status: Accepted

Solution code:
n=int(input())
w1=input()
w2=input()
count=1
now=0
frag=True
while now<n:
  if w1[now]==w2[now]:
    if now==0:
      count*=3
    else:
      if frag:
        count*=2
      else:
        count*=1
        frag=True
    now+=1
  else:
    if now==0:
      count*=6
    else:
      if frag:
        count*=2
      else:
        count*=3
    now+=2
    frag=False
print(count%(10**9+7))

Submission status: Accepted

Solution code:
n=int(input())
a=input()
b=input()
mod=10**9+7
ans=0
i=1
mae=-1
if a[0]==b[0]:
    ans=3
    mae=1
else:
    ans=6
    i+=1
    mae=0

while i<n:
    if a[i]==b[i]:
        if mae:
            ans*=2
        else:
            pass

        i+=1
        mae=1
    else:
        if mae:
            ans*=2
        else:
            ans*=3
        i+=2
        mae=0
    ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S1 = input()
    S2 = input()
    cnt = 0
    MOD = 10 ** 9 + 7
    i = 0
    while i < N:
        if i == 0:
            if S1[i] == S2[i]:
                cnt += 3
                cnt %= MOD
                i += 1
            else:
                cnt += 6
                cnt %= MOD
                i += 2
        else:
            if S1[i] == S2[i]:
                if S1[i-1] == S2[i-1]:
                    cnt *= 2
                    cnt %= MOD
                    i += 1
                else:
                    cnt *= 1
                    cnt %= MOD
                    i += 1
            else:
                if S1[i-1] == S2[i-1]:
                    cnt *= 2
                    cnt %= MOD
                    i += 2
                else:
                    cnt *= 3
                    cnt %= MOD
                    i += 2

    print(cnt)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

if S1[0] == S2[0]:
    ans = 3
    tmp = True #直前が縦
    j = 1 #次に見始めるところ
else:
    ans = 6
    tmp = False
    j = 2

while j < N:
    if S1[j] == S2[j]: #縦に並んでいる時
        if tmp: #縦が連続の時
            ans *= 2
        else: #直前が横
            ans *= 1
        tmp = True
        j += 1
    else: #横に並んでいる時
        if tmp: #縦-->横のとき
            ans *= 2
        else: #横が連続の時
            ans *= 3
        tmp = False
        j += 2
    ans %= MOD

print (ans)

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
memo_ls = [0 for j in range(n)]
ind = 0
while ind < n:
    if s1[ind] == s2[ind]:
        if ind == 0:
            memo_ls[ind] = 3
        elif s1[ind-1] == s2[ind-1]:
            memo_ls[ind] = memo_ls[ind - 1] * 2 % (10**9+7)
        else:
            memo_ls[ind] = memo_ls[ind - 1]
        ind += 1
    else:
        if ind == 0:
           memo_ls[ind] = 6
        elif s1[ind-1] == s2[ind-1]:
            memo_ls[ind] = memo_ls[ind - 1] * 2 % (10 ** 9 + 7)
        else:
            memo_ls[ind] = memo_ls[ind - 1] * 3 % (10 ** 9 + 7)
        memo_ls[ind + 1] = memo_ls[ind]
        ind += 2
print(memo_ls[n-1])

Submission status: Accepted

Solution code:
MOD = 1000000007

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

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

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

print(ans)

Submission status: Accepted

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

import math

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

    ans = 1
    tate = False
    i = 0
    if S1[i] == S2[i]: # 縦スタート
        ans *= 3
        tate = True
        i += 1
    else: # 横スタート
        ans *= 6
        tate = False
        i += 2

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

l = []
flag = False
for i in range(n):
    if s1[i] == s2[i]:
        l.append(1)
    else:
        if flag:
            l.append(2)
            flag = False
        else:
            flag = True

#print(l)

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

for i in range(1,len(l)):
    if l[i-1] == 1 and l[i] == 1:
        ans *= 2
    elif l[i-1] == 1 and l[i] == 2:
        ans *= 2
    elif l[i-1] == 2 and l[i] == 1:
        ans *= 1
    else:
        ans *= 3
    ans %= inf

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = input()
B = input()

def f(horizontal_flag):
    if horizontal_flag[0]:
        if horizontal_flag[1]:
            return 3
        else:
            return 1
    else:
        return 2

if N == 1:
    print(3)    
else:
    if A[0] == A[1]:
        counter = 6
        initial_num = 2
        horizontal_flag = [1,0]
    else:
        counter = 3
        initial_num = 1
        horizontal_flag = [0,0]

    for i in range(initial_num,N):
        if i == N-1:
            if horizontal_flag[1] == 2:
                horizontal_flag[1] = 1
                counter *= f(horizontal_flag)
            else:
                horizontal_flag[1] = 0
                counter *= f(horizontal_flag)
        elif A[i] == A[i+1]:
            horizontal_flag[1] = 2
        else:
            if horizontal_flag[1] == 2:
                horizontal_flag[1] = 1
                counter *= f(horizontal_flag)
            else:
                horizontal_flag[1] = 0
                counter *= f(horizontal_flag)
            horizontal_flag[0] = horizontal_flag[1]
    print(counter % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

# ドミノの並べ方を数えて行く
mod = 1000000007

pointa_s1 = 0
pointa_s2 = 0
if S1[pointa_s1] == S2[pointa_s2]:  # 縦に同じドミノからスタートする場合
    ans = 3
    pointa_s1 += 1
    pointa_s2 += 1
else:  # 横に同じドミノからスタートする場合
    ans = 6
    pointa_s1 += 2
    pointa_s2 += 2

while N > pointa_s1:
    # 分岐を色々考えていく
    if S1[pointa_s1] == S2[pointa_s2]:  # 縦に同じとき
        if S1[pointa_s1-1] == S2[pointa_s2-1]:  # その前も縦に並んているなら
            ans *= 2
            pointa_s1 += 1
            pointa_s2 += 1
        else:  # その前が横に並んでいるなら
            ans *= 1
            pointa_s1 += 1
            pointa_s2 += 1
    else:  # 今見ているものが横に同じとき
        if S1[pointa_s1-1] == S2[pointa_s2-1]:  # その前も縦に並んているなら
            ans *= 2
            pointa_s1 += 2
            pointa_s2 += 2
        else:  # その前が横に並んでいるなら
            ans *= 3
            pointa_s1 += 2
            pointa_s2 += 2

print(ans % mod)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
S1 = input()
S2 = input()
MOD = 1000000007
dir = 0 # 0→ よこ 1 →たて

if N == 1:
    ans = 3
    i = 1

elif S1[0] == S1[1]:
    dir = 0
    ans = 6
    i = 2
else:
    dir = 1
    ans = 3
    i = 1
p = [0,0,0,0]
while True:
    if i>=N:
        break


    if dir == 0:
        if i + 1 < N and S1[i] == S1[i + 1]: #横→横パターン

            dir = 0
            i += 2
            p[0] += 1
            ans *= 3
        else:

            i+=1  #横→縦パターン
            dir = 1
            ans *= 1


            p[1] += 1

    elif dir == 1:
        if i + 1 < N and  S1[i] == S1[i + 1]: #縦→横パターン
            i += 2
            dir = 0

            ans *= 2


            p[2] +=1
        else: #縦→縦パターン
            i += 1
            dir = 1
            ans *= 2
            p[3] +=1
    # print(ans)
    ans %= MOD
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys,heapq,bisect

mod = 10**9+7

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return input()

def GCD(a,b):
    while(a%b != 0):
        a,b = b,a%b
    return b

def LCM(a,b):
    return a*b//GCD(a,b)

def main():
    N = I()
    S1 = S()
    S2 = S()

    r = 1
    d_type = 0
    i = 0

    if S1[0] == S2[0]:
        r *= 3
        i += 1
        d_type = 0
    else:
        r *= 3 * 2
        i += 2
        d_type = 1

    while i < N:
        if d_type == 0 and S1[i] == S2[i]:
            r *= 2
            r %= mod
            d_type = 0
            i += 1
        elif d_type == 1 and S1[i] == S2[i]:
            d_type = 0
            i += 1
        elif d_type == 0 and S1[i] != S2[i]:
            r *= 2
            r %= mod
            d_type = 1
            i += 2
        else:
            r *= 3
            r %= mod
            d_type = 1
            i += 2

    return(r)

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

Submission status: Accepted

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

T=[]
i=0
while i<N:
  if S1[i]==S2[i]:
    T.append("T")
    i+=1
  else:
    T.append("Y")
    i+=2
#print(T)

u=[0]*len(T)
u[0]=3 if T[0]=="T" else 6
for i in range(1,len(T)):
  if T[i]=="T" and T[i-1]=="T":
    u[i]=2
  elif T[i]=="T" and T[i-1]=="Y":
    u[i]=1
  elif T[i]=="Y" and T[i-1]=="T":
    u[i]=2
  else:
    u[i]=3
#print(u)

md=10**9+7
ans=1
for i in u:
  ans*=i
  ans%=md
print(ans)

Submission status: Accepted

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


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

if S1[0] != S2[0]:
    ans = 6
    i = 2
    prev = 0  # 0: horizontal, 1:vertical
else:
    ans = 3
    i = 1
    prev = 1

while i <= N-1:
    if prev == 0 and S1[i] != S2[i]:
        ans *= 3
        i += 2
        prev = 0
    elif prev == 0 and S1[i] == S2[i]:
        ans *= 1
        i += 1
        prev = 1
    elif prev == 1 and S1[i] != S2[i]:
        ans *= 2
        i += 2
        prev = 0
    else:
        ans *= 2
        i += 1
        prev = 1
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = list(input())
S2 = list(input())
ans=1
prev=0
ue = ""
for i in range(N):
  if S1[i]==S2[i]:
    if prev == 0:
      ans*=3
    elif prev == 1:
      ans*=2
    else:
      ans*=1
    prev = 1
  else:
    if ue == S1[i]:
      continue
    else:
      if prev == 0:
        ans*=6
      elif prev == 1:
        ans*=2
      else:
        ans*=3
      ue=S1[i]
      prev=2
print(ans%1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n = I()
U = S()
D = S()
ans = 3
if U[0] != D[0]:
    ans *= 2
for i in range(1, n):
    if U[i-1] == U[i] or (U[i] == D[i] and U[i-1] != D[i-1]):
        continue
    elif U[i-1] != D[i-1] and U[i] != D[i]:
        ans = ans * 3 % mod
    else:
        ans = ans * 2 % mod



print(ans)