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:
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]
print ans

Submission status: Wrong Answer

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

MOD = 10 ** 9

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

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

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()
elif N == 2:
	print(6)
	sys.exit()
else:
	tmp = ""
	ans = 1
	cnt = 0
	for i in range(N):
		if S[i] == tmp:
			mode = 2
		else:  # 切り替わり
			if i != N-1 and S[i] == S[i+1]:
				if cnt == 0:
					ans *= 3
				elif cnt == 1:
					ans *= 2
				elif mode == 1:
					ans = (ans*2)%mod
				elif mode == 2:
					ans = (ans*3)%mod
			else:
				if cnt == 0:
					ans *= 3
				elif cnt == 1:
					ans *= 2
				elif mode == 1:
					ans = (ans*2)%mod
				elif mode == 2:
					pass
			
			cnt += 1
			mode = 1

		tmp = S[i]

print(ans)

Submission status: Wrong Answer

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 len(S) == 1:
	print(3)
	sys.exit()
else:
	tmp = ""
	ans = 1
	cnt = 0
	for i in range(N):
		if S[i] == tmp:
			mode = 2
		else:  # 切り替わり
			if i != N-1 and S[i] == S[i+1]:
				if cnt == 0:
					ans *= 3
				elif cnt == 1:
					ans *= 2
				elif mode == 1:
					ans = (ans*2)%mod
				elif mode == 2:
					ans = (ans*3)%mod
			else:
				if cnt == 0:
					ans *= 3
				elif cnt == 1:
					ans *= 2
				elif mode == 1:
					ans = (ans*2)%mod
				elif mode == 2:
					pass
			
			cnt += 1
			mode = 1

		tmp = S[i]

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=input()
s2=input()
x=[]
f=0
for i in range(n):
    if f==1:
        f=0
    else:
        if s1[i]==s2[i]:
            x.append(0)
        else:
            x.append(1)
            f=1
l=len(x)
#print(x)
if l==1:
    if x[0]==0:
        print(3)
    else:
        print(9)
else:
    if x[0]==0:
        c=3
    else:
        c=6
    for i in range(1,l):
        #print(c)
        if x[i-1]==0:
            c*=2
        else:
            if x[i]==1:
                c*=3
        c%=1000000007
    if x==[0]*l:
        c+=3
    if x==[1]*l:
        c+=3

    print(c%1000000007)

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=input()
s2=input()
x=[]
f=0
for i in range(n):
    if f==1:
        f=0
    else:
        if s1[i]==s2[i]:
            x.append(0)
        else:
            x.append(1)
            f=1
l=len(x)
#print(x)
if l==1:
    if x[0]==0:
        print(3)
    else:
        print(6)
else:
    if x[0]==0:
        c=3
    else:
        c=6
    for i in range(1,l):
        #print(c)
        if x[i-1]==0:
            c*=2
        else:
            if x[i]==1:
                c*=3
        c%=1000000007
    if x==[0]*l:
        c+=3
    if x==[1]*l:
        c+=3

    print(c%1000000007)

Submission status: Wrong Answer

Solution code:
n=int(input())
s1=input()
s2=input()
x=[]
f=0
for i in range(n):
    if f==1:
        f=0
    else:
        if s1[i]==s2[i]:
            x.append(0)
        else:
            x.append(1)
            f=1
l=len(x)
#print(x)
if l==1:
    if x[0]==0:
        print(3)
    else:
        print(6)
else:
    if x[0]==0:
        c=3
    else:
        c=6
    for i in range(1,l):
        #print(c)
        if x[i-1]==0:
            c*=2
        else:
            if x[i]==1:
                c*=3
        c%=1000000007

    if x==[0]*l or x==[1]*l:
        c+=1

    print(c%1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input())

s1 = input()
s2 = input()

INF = 1000000007

left = None
index = 0
cnt = 0
while index < n:
    # 右側が縦テトリス1つ
    if s1[index] == s2[index]:
        index += 1
        if left is None:
            left = 1
            cnt = 3
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 1
        left = 1

    # 右側が横テトリス2つ
    else:
        index += 2
        if left is None:
            left = 2
            cnt = 6
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 3
        left = 2
    cnt = cnt % INF
    print(cnt, index)
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

s1 = input()
s2 = input()

INF = 1000000009

left = None
index = 0
cnt = 0
while index < n:
    # 右側が縦テトリス1つ
    if s1[index] == s2[index]:
        index += 1
        if left is None:
            left = 1
            cnt = 3
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 1
        left = 1

    # 右側が横テトリス2つ
    else:
        index += 2
        if left is None:
            left = 2
            cnt = 6
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 3
        left = 2
    cnt = cnt % INF
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
v=[0]
w=0
for i in range(1,n):
    if s[i]==s[i-1]:
        v[-1]=1
        v.append(1)
        
    else:
        v.append(0)



for i in range(1,n):
    if v[i]!=v[i-1]:
        w+=1
mod=1000000007
print((3*2**(n-1-w))%mod)

Submission status: Wrong Answer

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

if N == 1:
    answer = 3
elif N == 2 or N == 3:
    answer = 6
else:
    answer = 6
    for i in range(3, N):
        if s1[i] == s2[i]:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            else:
                pass
        else:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            elif s1[i - 1] != s1[i]:
                answer = answer * 3 % mod
            else:
                pass

print(answer)

Submission status: Wrong Answer

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

if N == 1:
    answer = 3
elif N == 2 or N == 3:
    answer = 6
else:
    answer = 6
    for i in range(2, N):
        if s1[i] == s2[i]:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            else:
                pass
        else:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            elif s1[i - 1] != s1[i]:
                answer = answer * 3 % mod
            else:
                pass

print(answer)

Submission status: Wrong Answer

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

if N == 1:
    answer = 3
elif N == 2 or N == 3:
    answer = 6
else:
    answer = 6
    for i in range(2, N):
        if s1[i] == s2[i]:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            else:
                pass
        else:
            if s1[i - 1] == s2[i - 1]:
                answer = answer * 2 % mod
            elif s1[i - 1] != s2[i - 1] and s1[i - 1] != s1[i]:
                answer = answer * 3 % mod
            else:
                pass

print(answer)

Submission status: Wrong Answer

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

if N == 1:
    print(3)
    exit()
elif N == 2 or N == 3:
    print(6)
    exit()

for i in range(1, N):
    if s1[i] == s2[i]:
        if s1[i - 1] == s2[i - 1]:
            answer = answer * 2 % mod
        else:
            pass
    else:
        if s1[i - 1] == s2[i - 1]:
            answer = answer * 2 % mod
        elif s1[i - 1] != s1[i]:
            answer = answer * 3 % mod
        else:
            pass

print(answer)

Submission status: Wrong Answer

Solution code:
INFTY = 10**9+7
N = int(input())
S1 = input().strip()
S2 = input().strip()
if N==1:
    cnt = 3
elif N==2:
    cnt = 6
else:
    dp = [0 for _ in range(N)]
    if S1[0]==S2[0]:
        dp[0] = 3
    elif S1[0]==S1[1]:
        dp[0] = 6
    if S1[1]==S1[0]:
        dp[1]=dp[0]
    elif S1[1]==S2[1]:
        dp[1]=dp[0]*2
    for i in range(2,N):
        if S1[i]==S1[i-1] or (S1[i-1]!=S2[i-1] and S1[i]==S2[i]):
            dp[i] = dp[i-1]
        elif S1[i-1]==S2[i-1]:
            dp[i] = (dp[i-1]*2)%INFTY
        elif S1[i-1]!=S2[i-1] and S1[i]!=S2[i] and S1[i]!=S1[i-1]:
            dp[i] = (dp[i-1]*3)%INFTY
    cnt = dp[N-1]
print(cnt)

Submission status: Wrong Answer

Solution code:
INFTY = 10**9+7
N = int(input())
S1 = input().strip()
S2 = input().strip()
if N==1:
    cnt = 3
elif N==2:
    cnt = 6
else:
    dp = [0 for _ in range(N)]
    if S1[0]==S2[0]:
        dp[0] = 3
    elif S1[0]==S1[1]:
        dp[0] = 6
    if S1[1]==S1[0]:
        dp[1]=dp[0]
    elif S1[1]==S1[2]:
        dp[1]=dp[0]*2
    for i in range(2,N):
        if S1[i]==S1[i-1] or (S1[i-1]!=S2[i-1] and S1[i]==S2[i]):
            dp[i] = dp[i-1]
        elif S1[i-1]==S2[i-1]:
            dp[i] = (dp[i-1]*2)%INFTY
        elif S1[i-1]!=S2[i-1] and S1[i]!=S2[i] and S1[i]!=S1[i-1]:
            dp[i] = (dp[i-1]*3)%INFTY
    cnt = dp[N-1]
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(input())
b=list(input())
ans=1
i=0
f=0
mod=1000000007
while i!=n:
    if i==0:
        if a[i]==b[i]:
            i+=1
            ans*=3
            ans%=mod
            f=1
        else:
            i+=2
            ans*=6
            ans%=mod
            f=2
    else:
        if a[i]==b[i] and f==1:
            i+=1
            ans*=2
            ans%=mod
            f=1
        elif a[i]==b[i] and f==2:
            i+=1
            f=1
        elif a[i]!=b[i] and f==1:
            i+=2
            ans*=2
            ans%=mod
            f=2
        else:
            i+=2
            ans*=2
            ans%=mod
            f=2
print(ans%mod)

Submission status: Wrong Answer

Solution code:
n=int(input())
s="1"+input()
a=[]
for i in range(n):
  if s[i]!=s[i+1]:a+=[1]
  else:a[-1]+=1
x=3
for i in range(1,len(a)):
  if a[i-1]==a[i]==1:x*=2
  elif a[i-1]==a[i]==2:x*=3
  elif a[i]==1:x*=1
  else:x*=2
  x%=10**9+7
print(x)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

print(ans % mod)

Submission status: Wrong Answer

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



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

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

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
MOD  = 1000000007

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

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

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

Submission status: Wrong Answer

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


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

# print(PST)

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

print(res)

Submission status: Wrong Answer

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

		pointer += 1
		if ans[1] in [0,1]:
			ans[0] = ans[0] *3
		#ans[0] = ans[0] % mod
		ans[1] = 1

	else:

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

print(ans[0] % mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

MOD = 10. ** 9 + 7

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

print(int(ans))

Submission status: Wrong Answer

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

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

    ans %= 10**9+7
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(2)]
MOD = 10**9+7
i = 0
ans = 3
pre = 0
while i < n:
    if S[0][i] == S[1][i]:
        n = 1
        i += 1
    else:
        n = 2
        i += 2
    if pre == 0 and n == 2:
        ans *= 2
    elif pre == 1:
        ans = (ans*2) % MOD
    elif pre == 2 and n == 2:
        ans = (ans*3) % MOD
    pre = n
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

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

    if N == 1:
        return 3
    if N == 2:
        return 6
    if N == 3:
        return 6

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


    return ans % MOD


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
S1,S2=input(),input()
MOD=1000000007
if n==1:
    ans=3
elif n==2:
    ans=6
elif n==3:
    ans=6
else:
    F=[0]*n
    if S1[0]==S2[0]:
         F[0],F[1],F[2]=3,0,6
    else:
        F[0],F[1],F[2]=0,6,6
    for i in range(3,n):
        if S1[i]==S2[i]:
            if S1[i-1]==S2[i-1]:
                F[i]=(2*F[i-1])%MOD
            else:
                F[i]=F[i-1]%MOD
        else:
            if S1[i]!=S1[i-1]:
                F[i]=0
            else:
                if S1[i-2]==S2[i-2]:
                    F[i]=(2*F[i-2])%MOD
                else:
                    F[i]=(3*F[i-2])%MOD
    ans=F[n-1]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
S1,S2=input(),input()
MOD=1000000007
if n==1:
    ans=3
elif n==2:
    ans=6
elif n==3:
    ans=6
else:
    F=[0]*n
    F[0],F[1],F[2]=3,6,6
    for i in range(3,n):
        if S1[i]==S2[i]:
            if S1[i-1]==S2[i-1]:
                F[i]=(2*F[i-1])%MOD
            else:
                F[i]=F[i-1]%MOD
        else:
            if S1[i]!=S1[i-1]:
                F[i]=0
            else:
                if S1[i-2]==S2[i-2]:
                    F[i]=(2*F[i-2])%MOD
                else:
                    F[i]=(3*F[i-2])%MOD
    ans=F[n-1]%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
S1,S2=input(),input()
MOD=1000000007
if n==1:
    ans=3
elif n==2:
    ans=6
elif n==3:
    ans=6
else:
    F=[0]*n
    F[0],F[1],F[2]=3,6,6
    for i in range(3,n):
        if S1[i]==S2[i]:
            if S1[i-1]==S2[i-1]:
                F[i]=(2*F[i-1])%MOD
            else:
                F[i]=F[i-1]%MOD
        else:
            if S1[i]!=S1[i-1]:
                F[i]=0
            else:
                if S1[i-2]==S2[i-2]:
                    F[i]=(2*F[i-2])%MOD
                else:
                    F[i]=(3*F[i-2])%MOD
    ans=F[n-1]
print(ans)

Submission status: Wrong Answer

Solution code:
"""
横スタートなら6通り
縦スタートなら3通り
横、横なら＊3通り
横、縦なら＊1通り
縦、横なら＊2通り
縦、縦なら＊2通り
"""
from sys import stdin
input = stdin.readline

n = int(input())
tot = 1
MOD = 10**9 + 7
S = list(input())
nums = []

if n == 1:
    nums.append(1)
for i in range(n-1):
    s = S[i]
    s_ = S[i+1]
    if s == s_:
        nums.append(0)
        S[i] = 0
        S[i+1] = 0
    elif s == 0:
        pass
    else:
        nums.append(1)

l = len(nums)
for i in range(l):
    if i == 0 and nums[i] == 0:
        tot = (tot*6) % MOD
    elif i == 0 and nums[i] == 1:
        tot = (tot*3) % MOD
    elif nums[i-1] == 0 and nums[i] == 0:
        tot = (tot*3) % MOD
    elif nums[i-1] == 1:
        tot = (tot*2) % MOD
print(tot)