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: Wrong Answer

Solution code:
M = 10 ** 9 + 7


def main():
    n = int(input())
    s1, s2 = input(), input()

    com = 1
    i, j = 0, 0
    while i < n or j < n:
        if i <= j:
            if s1[i] == s2[j]:
                if i == 0:
                    com = com * 3 % M
                elif s1[i-1] == s2[j-1]:
                    com = com * 2 % M
                i += 1
                j += 1
            else:
                if i == 0:
                    com = com * 3 % M
                else:
                    com = com * 2 % M
                i += 2

        else:
            if j == 0:
                com = com * 2 % M
            elif s1[i-3] != s2[j-1]:
                com *= 1.5
            j += 2

    print(int(com))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

N = int(input())
S = []
for i in range(2):
    S.append(input())
    

# make XYline
xy = ""
for i in range(len(S[0])):
    if S[0][i] == S[1][i]:
        xy += "X"
    elif i==len(S[0])-1:
        break
    elif S[0][i] == S[0][i+1]:
        xy += "Y"

# proceed
if xy[0] == "X":
    ans = 3
else:
    ans = 6

if len(xy)==1:
    pass
else:
    for i in range(1,len(xy)):
        if xy[i-1] == "X" and xy[i] == "X":
            ans *= 2
        elif xy[i-1] == "X" and xy[i] == "Y":
            ans *= 2
        elif xy[i-1] == "Y" and xy[i] == "X":
            ans *= 1
        elif xy[i-1] == "Y" and xy[i] == "Y":
            ans *= 3

        ans = ans%MOD

Submission status: Wrong Answer

Solution code:
def check(i,j):
    if i > 0:
        k = S[j][i-1] 
        if k in checked and not k in C:
            C.append(k)
    if j > 0:
        l = S[j-1][i]
        if l in checked and not l in C:
            C.append(l)
N = int(input())
S = [list(input()) for _ in range(2)]
ans = 1
checked = {}
for i in range(N):
    for j in range(2):
        p = S[j][i]
        print(p,ans)
        if not p in checked:
            C = []
            check(i,j)
            if j < 1 and S[j+1][i] == p:
                check(i,j+1)
            checked[p] = C
            print(C)
            print([checked[i] for i in C] if C != [] else 0)
            if len(C) > 1:
                if not C[0] in checked[C[-1]]:
                    ans = ((ans*3)//2)
            else:
                ans = (ans*(3-len(C)))
            print(ans)
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
blocks = [input().rstrip() for x in range(2)]

MOD = 1000000007
result = 0
count = 0
prev = False
while count < N-1:
  if count == 0:
    if blocks[0][count] == blocks[1][count]:
      result = 3
      prev = True
    else:
      result = 6
      count += 1
  else:
    if prev:
      result = (result*2) % MOD
      # a bb
      # a cc 
      if blocks[0][count] != blocks[1][count]:
        prev = False
        count += 1
    else:
      if blocks[0][count] == blocks[1][count]:
        prev = True
      else:
        result = (result*3) % MOD
        count += 1
  count += 1
print(result)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

n = int(input())
s = list(input())
s2 = list(input())

array = []

i = 0
while i < n:
	if i == n - 1:
		array.append("t")
		i += 1
	elif s[i] != s[i + 1]:
		array.append("t")
		i += 1
	else:
		array.append("y")
		i += 2

if array[0] == "t":
	ans = 3
else:
	ans = 6

if len(array) == 1:
	print(ans)
else:
	for i in range(1, len(array)):
		if array[i-1] == "t":
			ans = (ans * 2) % MOD
		elif array[i] == "y":
			ans = (ans * 2) % MOD

	print(int(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
import math
N = int(input())
S1 = input()
S2 = input()

i = 0
ans = 1
before = -1 #0:直前が縦、1:直前が横
while i < N :
    if S1[i] == S2[i]:#縦に置かれている
        if before == 1:#直前が横
            ans *= 1
        elif before == 0:#直前が縦
            ans *=2
        else:#最初
            ans *= 3
        i += 1
        before = 0
    else:#横に置かれている
        if before == 1:#直前が横
            ans *= 3
        elif before == 0:#直前が縦
            ans *= 2
        else:#最初
            ans *= 6
        i += 2
        before = 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
s1 = input()
s2 = input()
sum = 1
mul = 1
flag = 0
i = 0

while True:
    if i >= N:
        print(sum%1000000007)
        break

    elif s1[i]==s2[i] and flag==0:
        sum = 3
        i += 1
        flag = 1
    elif s1[i]!=s2[i] and flag==0:
        sum = 6
        i += 2
        flag = 2
    elif s1[i]==s2[i] and flag==1:
        mul = 2
        i += 2
        flag = 1
    elif s1[i]!=s2[i] and flag==1:
        mul = 2
        i += 2
        flag = 2
    elif s1[i]==s2[i] and flag==2:
        mul = 1
        i += 1
        flag = 1
    elif s1[i]!=s2[i] and flag==2:
        mul = 3
        i += 2
        flag = 2
    sum = sum*mul

Submission status: Wrong Answer

Solution code:
import sys

N=int(input())

S=input()

if len(S)==1:
    print(3)
    sys.exit()

if S[0]==S[1]:
    before=2
    S=S[2::]
    pattern=6
else:
    before=1
    S=S[1::]
    pattern=3
while len(S)>1:
    if before==2:
        if S[0]==S[1]:
            pattern=pattern*3
            S=S[2::]
        else:
            before=1
            S=S[1::]
    else:
        if S[0]==S[1]:
            S=S[2::]
            before=2
        else:
            S=S[1::]
        pattern=pattern*2
    print(pattern)
    print(S)



if len(S)==1 and before==1:
    pattern=pattern*2
print (pattern%1000000007)

Submission status: Wrong Answer

Solution code:
def pop_when_x():
    S1.pop(0)
    S2.pop(0)
    global left_state
    left_state = "X"


def pop_when_y():
    S1.pop(0)
    S1.pop(0)
    S2.pop(0)
    S2.pop(0)
    global left_state
    left_state = "Y"


if __name__ == '__main__':
    N = int(input())
    S1 = list(input())
    S2 = list(input())

    if S1[0] == S2[0]:
        cases = 3
        left_state = "X"
        pop_when_x()
    else:
        cases = 6
        left_state = "Y"
        pop_when_y()

    while len(S1) != 0:
        # print("".join(S1))
        # print("".join(S2))
        if S1[0] == S2[0]:
            state = "X"
        else:
            state = "Y"
        # print("left_state:" + left_state)
        # print("state:" + state)
        if left_state == "X" and state == "X":
            cases *= 2
            pop_when_x()
        elif left_state == "X" and state == "Y":
            cases *= 2
            pop_when_y()
        elif left_state == "Y" and state == "X":
            cases *= 1
            pop_when_x()
        elif left_state == "Y" and state == "Y":
            cases *= 3
            pop_when_y()

    print(cases)

Submission status: Wrong Answer

Solution code:
def pop_when_x():
    S1.pop(0)
    S2.pop(0)
    global left_state
    left_state = "X"


def pop_when_y():
    S1.pop(0)
    S1.pop(0)
    S2.pop(0)
    S2.pop(0)
    global left_state
    left_state = "Y"


if __name__ == '__main__':
    N = int(input())
    S1 = list(input())
    S2 = list(input())

    if S1[0] == S2[0]:
        cases = 3
        left_state = "X"
        pop_when_x()
    else:
        cases = 6
        left_state = "Y"
        pop_when_y()

    while len(S1) != 0:
        print("".join(S1))
        print("".join(S2))
        if S1[0] == S2[0]:
            state = "X"
        else:
            state = "Y"
        print("left_state:" + left_state)
        print("state:" + state)
        if left_state == "X" and state == "X":
            cases *= 2
            pop_when_x()
        elif left_state == "X" and state == "Y":
            cases *= 2
            pop_when_y()
        elif left_state == "Y" and state == "X":
            cases *= 1
            pop_when_x()
        elif left_state == "Y" and state == "Y":
            cases *= 3
            pop_when_y()

    print(cases)

Submission status: Wrong Answer

Solution code:
input()

a =raw_input()

edge = []

while len(a) > 1:
      if a[0] == a[1]:
            edge.append(2)
            a = a[2:]
      else:
            edge.append(1)
            a = a[1:]
         
if len(a) == 1:
      edge.append(1)

ans = 1

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

last = edge[0]

for i in range(1, len(edge)):
      if (edge[i-1], edge[i]) == (1, 1):ans *= 2
      if (edge[i-1], edge[i]) == (1, 2):ans *= 2
      if (edge[i-1], edge[i]) == (2, 1):ans *= 1
      if (edge[i-1], edge[i]) == (2, 2):ans *= 2
      ans %= 10**9 + 7

print ans

Submission status: Wrong Answer

Solution code:
N=int(input())

field=[list(input())]
field.append(list(input()))

M=1000000007

b=[field[0][0],field[1][0]]
if b[0]==b[1]:
    bdeffer=False
    count=3
else:
    bdeffer=True
    count=6

for j in range(1,len(field[0])):
    count=count%M
    a=[field[0][j],field[1][j]]

    if a[0]==b[0]:
        b=a
        if a[0]==a[1]:
            bdeffer=False
        else:
            bdeffer=True
        continue

    if a[0]==a[1]:
        if not bdeffer:
            count*=2
    else:
        if bdeffer:
            count*=3
        else:
            count*=2

    b=a[:]

    if a[0]==a[1]:
        bdeffer=False
    else:
        bdeffer=True

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
a1 = list(input())
a2 = list(input())
t, i = 0, 0
x = 1

while (i < len(a1) - 1):
	if(t == 0):
		if(a1[i] == a1[i + 1]):
			x = x*6
			t = 1
			i += 2
		
		else:
			x = x*3
			t = 2
			i += 1

		continue

	if(t == 1):
		if(a1[i] == a1[i + 1]):
			x = x*3
			t = 1
			i += 2

		else:
			x = x*1
			t = 2
			i += 1

		continue

	if(t == 2):
		if(a1[i] == a1[i + 1]):
			x = x*2
			t = 1
			i += 2

		else:
			x = x*2
			t = 2
			i += 1

		continue


if(len(a1) == 1):
	print(3)

else:
	print(x % 1000000007)

Submission status: Wrong Answer

Solution code:
N=int(input())

field=[list(input())]
field.append(list(input()))

M=1000000007

b=[field[0][0],field[1][0]]
if b[0]==b[1]:
    bdeffer=False
    count=3
else:
    bdeffer=True
    count=6

for j in range(1,len(field[0])):

    a=[field[0][j],field[1][j]]

    if a[0]==b[0]:
        b=a
        if a[0]==a[1]:
            bdeffer=False
        else:
            bdeffer=True
        continue

    if a[0]==a[1]:
        if not bdeffer:
            count*=2%M
    else:
        if bdeffer:
            count*=3%M
        else:
            count*=2%M

    b=a[:]

    if a[0]==a[1]:
        bdeffer=False
    else:
        bdeffer=True

print(count)

Submission status: Wrong Answer

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

mod = 1000000007

num = 1
i = 0
b = 0
tmp_t = -1
while(b + i < n):
    if s1[i + b] == s2[i + b]: # t 0
        if tmp_t == 0:
            num = (num * 2) % mod
        elif tmp_t == 1:
            num = (num * 2) % mod
        else:
            num = 3
        tmp_t = 0
    else: # t 1
        if tmp_t == 0:
            num = (num * 1) % mod
        elif tmp_t == 1:
            num = (num * 3) % mod
        else:
            num = 6
        tmp_t = 1
        b += 1
    i += 1

print(num)

Submission status: Wrong Answer

Solution code:
N = int(input())
a1 = list(input())
a2 = list(input())
t, i = 0, 0
x = 1

while (i < len(a1) - 1):
	if(t == 0):
		if(a1[i] == a1[i + 1]):
			x = x*6
			t = 1
			i += 2
		
		else:
			x = x*3
			type = 2
			i += 1

		continue

	if(t == 1):
		if(a1[i] == a1[i + 1]):
			x = x*3
			t = 1
			i += 2

		else:
			x = x*2
			t = 2
			i += 1

		continue

	if(t == 2):
		if(a1[i] == a1[i + 1]):
			x = x*3
			t = 1
			i += 2

		else:
			x = x*2
			t = 2
			i += 1

		continue



print(x % 1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input())
s1 = input()
s2 = input()
l = []
m = 1
mod = 10**9 + 7

after = False
for i in range(n):
	if i == n-1:
		if after:
			pass
		else:
			l.append(0)
	else:
		if after:
			after = False
			pass
		else:
			if s1[i] == s1[i+1]:
				l.append(1)
				after = True
			else:
				l.append(0)

for i, x in enumerate(l):
	if i == 0:
		if x == 0:
			m = 3
		else:
			m = 6 
	else:
		if x == 0 and l[i-1] == 0:
			m = m * 2
			m = m % mod
		elif x == 0 and l[i-1] == 1:
			m = m * 2
			m = m % mod
		elif x == 1 and l[i-1] == 0:
			pass
		else:
			m = m * 3
			m = m % mod

print(m)

Submission status: Wrong Answer

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

mod = 1000000007

num = 3
i = 1
b = 0
tmp_t = 0
if s1[0] == s2[0]:
    tmp_t = 0
else:
    tmp_t = 1
    b += 1

while(b + i < n):
    if s1[i + b] == s2[i + b]: # t 0
        if tmp_t == 0:
            num = (num * 2) % mod
        else:
            num = (num * 2) % mod
        tmp_t = 0
    else: # t 1
        if tmp_t == 0:
            num = (num * 1) % mod
        else:
            num = (num * 3) % mod
        tmp_t = 1
        b += 1
    i += 1

print(num)

Submission status: Wrong Answer

Solution code:
n = int(input())
s1 = input()
s2 = input()
l = []
m = 3
mod = 10**9 + 7

after = False
for i in range(n):
	if i == n-1:
		if after:
			pass
		else:
			l.append(0)
	else:
		if after:
			after = False
			pass
		else:
			if s1[i] == s1[i+1]:
				l.append(1)
				after = True
			else:
				l.append(0)

for i, x in enumerate(l):
	if i == 0:
		pass
	else:
		if x == 0 and l[i-1] == 0:
			m = m * 2
			m = m % mod
		elif x == 0 and l[i-1] == 1:
			m = m * 2
			m = m % mod
		elif x == 1 and l[i-1] == 0:
			pass
		else:
			m = m * 3
			m = m % mod

print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
s1 = input()
s2 = input()
l = []
m = 3
mod = 10**9 + 7
 
after = False
for i in range(n):
	if i == n-1:
		if after:
			pass
		else:
			l.append(0)
	else:
		if after:
			after = False
			pass
		else:
			if s1[i] == s1[i+1]:
				l.append(1)
				after = True
			else:
				l.append(0)

 
for i, x in enumerate(l):
	if i == 0:
		pass
	else:
		if x == 0 and l[i-1] == 0:
			m = m * 2
		elif x == 0 and l[i-1] == 1:
			m = m * 2
		elif x == 1 and l[i-1] == 0:
			pass
		else:
			m = m * 3
 
print(m % mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
s1 = input()
s2 = input()
l = []
m = 3
mod = 10**9 + 7

after = False
for i in range(n):
	if i == n-1:
		if after:
			pass
		else:
			l.append(0)
	else:
		if after:
			after = False
			pass
		else:
			if s1[i] == s1[i+1]:
				l.append(1)
				after = True
			else:
				l.append(0)

print(l)

for i, x in enumerate(l):
	if i == 0:
		pass
	else:
		if x == 0 and l[i-1] == 0:
			m = m * 2
		elif x == 0 and l[i-1] == 1:
			m = m * 2
		elif x == 1 and l[i-1] == 0:
			pass
		else:
			m = m * 3

print(m % mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = 1

s = 0
for i in range(N):
    p = 1
    if A[i] == A[i-1]:
        continue
    elif i+1 < N and A[i] == A[i+1]:
        p = [6, 3, 2][s]
        s = 1
    else:
        p = [3, 1, 2][s]
        s = 2
    ans = (ans * p) % (int(1e9) + 7)

print(ans)

Submission status: Wrong Answer

Solution code:
y=[]
n=int(raw_input())
for i in range(2):
    y.append(raw_input())
mod=10**9+7
mul=1
for i in range(n):
    if i%3==0:
        mul*=3
    elif i%3==1:
        mul*=2
    mul%=mod
print mul

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import sys

def main():
	n = int(input())
	str1 = input()
	str2 = input()

	ptrn = []
	i = 0
	while True:
		if str1[i] == str2[i]:
			ptrn.append("t")
			i += 1
		else:
			ptrn.append("y")
			i += 2
		if i >= n:
			break
	
	print(ptrn)

	if ptrn[0] == "t":
		n_ptrn = 3
	else:
		n_ptrn = 6

	for i in range(1, len(ptrn)):
		print(n_ptrn)
		if ptrn[i - 1] == "t" and ptrn[i] == "t":
			n_ptrn = n_ptrn * 2
		elif ptrn[i - 1] == "t" and ptrn[i] == "y":
			n_ptrn = n_ptrn * 2
		elif ptrn[i - 1] == "y" and ptrn[i] == "y":
			n_ptrn = n_ptrn * 3

	print(n_ptrn % 1000000007)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N = int(input())
S = [input()+".", input()+","]
mod = 10**9+7

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

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

while i < N:
    if S[0][i] == S[1][i]:
        if S[0][i-1] == S[1][i-1]:
            ans *= 2
        else:
            pass
        ans %= mod
        i += 1
    
    else:
        if S[0][i-1] == S[1][i-1]:
            ans *= 2
        else:
            ans *= 3
        ans %= mod
        i += 2

print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    L1 = [None] + list(input()) + [None]
    L2 = [None] + list(input()) + [None]
    seq = []
    if L1[1] == L2[1]:  # 縦ドミノ
        L1[1] = L2[1] = "#"
        seq.append("X")
    elif L1[1] == L1[2]:  # 横ドミノ
        L1[1] = L1[2] = L2[1] = L2[2] = "#"
        seq.append("Y")

    for i in range(1, n + 1):
        if L1[i] == "#":
            continue
        else:
            if L1[i] == L2[i]:
                seq.append("X")
                L1[i] = "#"
            elif L1[i] == L1[i + 1]:
                seq.append("Y")
                L1[i] = L1[i + 1] = "#"
    if seq[0] == "X":
        ans = 3
    elif seq[0] == "Y":
        ans = 6

    for i in range(1, len(seq)):
        if seq[i - 1] == "X":
            if seq[i] == "X":
                ans *= 2
            elif seq[i] == "Y":
                ans *= 2
        elif seq[i - 1] == "Y":
            if seq[i] == "X":
                ans *= 1
            elif seq[i] == "Y":
                ans *= 3
        ans %= 1000000007
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

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

N=intput()
S1=input()
S2=input()
i=0
ans=1
# first,tate,yoko
tmp=0
same=[3,2,1]
diff=[6,2,3]
while i<N:
    if S1[i]==S2[i]:
        ans*=same[tmp]
        tmp=1
        i+=1
    else:
        ans*=diff[tmp]
        tmp=2
        i+=2
    ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7


def get_pattern(A, B, pos, pre):
    if pre == 0:
        if A[pos] == B[pos]:
            return 3, pos+1, 1
        elif A[pos] == A[pos+1]:
            return 6, pos+2, 2
    if pre == 1:
        if A[pos] == B[pos]:
            return 2, pos+1, 1
        elif A[pos] == A[pos+1]:
            return 2, pos+2, 2
    if pre == 2:
        if A[pos] == B[pos]:
            return 1, pos+1, 1
        elif A[pos] == A[pos+1]:
            return 3, pos+2, 2

def run():
    N = int(input())
    S1 = input()
    S2 = input()
    pos = 0
    pre = 0
    ans = 1
    while pos < N:
        val, pos, pre = get_pattern(S1, S2, pos, pre)
        #print(val)
        ans *= val
        ans %= mod

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

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

if S1[0] == S2[0]:
  ans = 3
  cnt = 1
  tmp = 0
else:
  ans = 6
  cnt = 2
  tmp = 1
  
while cnt < N:
  if tmp == 0:
    if S1[cnt] == S2[cnt]:
      ans *= 2
      cnt += 1
    else:
      ans *= 2
      cnt += 2
      tmp = 1
  else:
    if S1[cnt] == S2[cnt]:
      cnt += 1
      tmp = 0
    else:
      ans *= 3
      cnt += 2
print(ans%1000000007)

Submission status: Accepted

Solution code:
N = int(input())
S = [list(input()) for _ in range(2)]
prev = S[0][0] == S[1][0]
if prev:
    x = 3
    i = 1
else:
    x = 6
    i = 2
while i < N:
    nxt = S[0][i] == S[1][i]
    i += 1 if nxt else 2
    if prev and nxt:
        x *= 2
    elif prev:
        x *= 2
    elif nxt:
        x = x
    else:
        x *= 3
    prev = nxt
print(x % (10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
ans = 1
i = 1
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]:
        if s1[i] == s2[i]:
            ans = (ans * 2) % mod
            i += 1
            continue
        else:
            ans = (ans * 2) % mod
            i += 2
            continue
    else:
        if s1[i] == s2[i]:
            ans = (ans * 1) % mod
            i += 1
            continue
        else:
            ans = (ans * 3) % mod
            i += 2
            continue
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
S = input()
Do = Counter(S)
Ans = 0
i = 0
if Do[S[0]] == 1:
    Ans = 3
    i += 1
    sig = 1
else:
    Ans = 6
    i += 2
    sig = 2
while not i >= n:
    if Do[S[i]] == 1:
        if sig == 1:
            Ans *= 2
        else:
            Ans *= 1
        sig = 1
        i +=1
    else:
        if sig == 1:
            Ans *=2
        else:
            Ans *=3
        sig = 2
        i += 2
    Ans = Ans%(10**9+7)
print(Ans)

Submission status: Accepted

Solution code:
N=int(input())
l=""
mod=10**9+7
Sa=list(input())
Sb=list(input())
for i in range(N):
   if Sa[i]==Sb[i]:
      l+="X"
   else:
      l+="Y"
l=l.replace("YY","Y")
ans=6 if l[0]=="Y" else 3
for i in range(1,len(l)):
   if l[i]=="Y" and l[i-1]=="Y":
      ans*=3
   if l[i]=="X" and l[i-1]=="X":
      ans*=2
   if l[i]=="Y" and l[i-1]=="X":
      ans*=2
   ans=ans%mod
print(ans)

Submission status: Accepted

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

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

while i < N:
  pre_s1, pre_s2 = S1[i-1], S2[i-1]
  s1, s2 = S1[i], S2[i]
  if pre_s1 == pre_s2:
    ans *= 2
    ans %= MOD
    if s1 == s2:
      i += 1
    else:
      i += 2
  else:
    if s1 == s2:
      i += 1
    else:
      ans *= 3
      ans %= MOD
      i += 2

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S1 = input()
S2 = input()
ans = 1
MOD = 10**9+7
i = 0
flag = True

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())

Mod=10**9+7
S=input()
T=input()

if S[0]==T[0]:
    K,I=3,1
    Mode=True
else:
    K,I=6,2
    Mode=False

#Mode:True->縦,False->横

while I<N:
    if S[I]==T[I]:
        if Mode:
            K*=2
        else:
            K*=1
        Mode=True
        I+=1
    else:
        if Mode:
            K*=2
        else:
            K*=3
        Mode=False
        I+=2
    K%=Mod
print(K)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
s1 = input()
s2 = input()
if s1[0] == s2[0]:
    a = 3
    l = 0
    v = True
else:
    a = 6
    l = 1
    v = False
mod = 10**9+7
def mult_mod(x,y):
    return (x*y) % mod
while l+1 < n:
    if v:
        if s1[l+1] == s2[l+1]:
            l += 1
            a = mult_mod(a,2)
        else:
            l += 2
            a = mult_mod(a,2)
            v = False
    else:
        if s1[l+1] == s2[l+1]:
            l += 1
            v = True
        else:
            l += 2
            a = mult_mod(a,3)

print(a%mod)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7
yoko = True
if s1[0]==s2[0]:
    ans = 3
    cur = 1
    yoko = False
else:
    ans = 6
    cur = 2

while cur<n:
    if s1[cur]==s2[cur]:
        ans *= 1 if yoko else 2
        ans %= mod
        cur += 1
        yoko = False
    else:
        ans *= 3 if yoko else 2
        ans %= mod
        cur += 2
        yoko = True

print(ans)

Submission status: Accepted

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

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

if S1[0] == S1[1]:
    dp = 6
    start = 2
    state = 0
else:
    dp = 3
    start = 1
    state = 1

i = start
while i<L-1:
    if S1[i] == S1[i+1]:
        if state == 0:
            dp *= 3
            dp %= MOD
        else:
            dp *= 2
            dp %= MOD
        state = 0
        i += 2
    else:
        if state == 1:
            dp *= 2
            dp %= MOD
        state = 1
        i += 1
if state == 1:
    dp *= 2
    dp %= MOD
print(dp)

Submission status: Accepted

Solution code:
N = int(input())
grid = [input(),input()]
MOD = 10**9 + 7

cnt = 3 if grid[0][0] == grid[1][0] else 6

for i in range(1,N):
    a,b = grid[0][i-1],grid[1][i-1]
    c,d = grid[0][i],grid[1][i]

    if a == b:
        cnt *= 2
    elif c != d and a != c:
        cnt *= 3
    cnt %= MOD

print(cnt)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    l = []
    res = 1
    while res < N:
        if S1[res - 1] == S1[res]:
            l.append(2)
            res += 2
        else:
            l.append(1)
            res += 1
    if res == N:
        l.append(1)

    n = len(l)
    if l[0] == 1:
        ans = 3
    else:
        ans = 6

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

    print(ans)


if __name__ == '__main__':
    main()