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:
import sys
import heapq
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

#　素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# ここから書き始める
n = int(input())
s1 = input()
s2 = input()
ans = 1
v = False
h1 = False
h2 = False
for i in range(n):
    if i == 0:
        if s1[i] == s2[i]:
            ans *= 3
            v = True
        else:
            ans *= 6
            h1 = True
    else:
        if v:
            if s1[i] == s2[i]:
                ans *= 2
                v = True
                h1 = False
                h2 = False
            else:
                ans *= 2
                v = False
                h1 = True
                h2 = False
        elif h1:
            v = False 
            h1 = False
            h2 = True
        else:
            if s1[i] == s2[i]:
                v = True
                h1 = False
                h2 = False
            else:
                ans *= 3
                v = False
                h1 = True
                h2 = False
    ans %= mod
            
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

n = int(input())
s1 = input()
s2 = input()
ans = 1

if s1[0] == s2[0]:
    i = 1
    pre_pat = 0
    ans = 3
else:
    i = 2
    pre_pat = 1
    ans = 6

t = [[2, 2], [1, 3]]
while True:
    if i >= n:
        break
    if s1[i] == s2[i]:
        pat = 0
        i += 1
    else:
        pat = 1
        i += 2
    ans *= t[pre_pat][pat]
    ans %= MOD
    # print(pre_pat, pat, ans, i)
    pre_pat = pat
print(ans)

Submission status: Accepted

Solution code:
# 上一列だけ見るのでよくない？なんなら直前のやつだけでもいいんじゃない？
# あ 敷き詰め方は与えられるのか。それも含めて総数を出すのかと思ってた
# 雑に試したらいけたっぽい ifを重ねるたびに不安になる
# 直前が縦に同じ色で今が縦に同じ色 -> 2種類使える
# 直前が縦に同じ色で今が横に同じ色 -> （直前に使った色以外の2種類を縦に重ねる組み合わせで）2種類使える
# 直前が横に同じ色で今が縦に同じ色 -> （直前に2色使っているので）1色だけ使える
# 直前が横に同じ色で今が横に同じ色 -> （直下参照）3パターンある

# --- 縦に2種類使った後に縦に2種類使う組み合わせ ---
# 1 - 2,2,3
# 2 - 1,3,1
# よって3パターン

n = int(input())
s1, s2 = input(), input()
ans = 0
idx = 0
MOD = 10**9 + 7
pre = -1  # i-1の色の数 1or2
while idx < n:
    if s1[idx] == s2[idx]:
        if idx == 0:
            ans = 3
        else:
            if pre == 1:
                ans *= 2
            elif pre == 2:
                ans *= 1  # 直前で使ってない色だけ使える
        pre = 1
        idx += 1
    else:
        if idx == 0:
            ans = 6
        else:
            if pre == 1:
                ans *= 2
            elif pre == 2:
                ans *= 3
        pre = 2
        idx += 2
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
s = input()
t = []

if (len(s)==1):
    print(3)
    sys.exit()
if (len(s)==2):
    print(6)
    sys.exit()

for i in range(len(s)-1):
    if (i>0):
        if(s[i-1]==s[i]):
            if (i == len(s)-2):
                t.append(1)
                continue
            else:
                continue
        elif (i == len(s)-2 and s[i]!=s[i+1]):
            t.append(1)
            
    
    if (s[i]==s[i+1]):
        t.append(2)
    else:
        t.append(1)

if (t[0]==1):
    ans = 3
else:
    ans = 6

for i in range(len(t)-1):
    
    if (t[i]==1):
        if (t[i+1]==1):
            ans *= 2
        else:
            ans *= 2
    else:
        if (t[i+1]==1):
            ans *= 1
        else:
            ans *= 3
print(ans % 1000000007)

Submission status: Accepted

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

MOD = 1000000007
i = 0
C = []
while i < N:
    if S[0][i] == S[1][i]:
        C.append(0)
        i += 1
    else:
        C.append(1)
        i += 2

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
t = input()
u = []
flg = 0
mod = 10**9+7
for i in range(n):
	if s[i] == t[i]:
		u.append(1)
	else:
		if flg == 1:
			u.append(0)
			flg = 0
		else:
			flg = 1
if u[0] == 1:
	ans = 3
else:
	ans = 6
for i in range(len(u)-1):
	if u[i] == 1 and u[i+1] == 1:
		ans *= 2
	elif u[i] == 1 and u[i+1] == 0:
		ans *= 2
	elif u[i] == 0 and u[i+1] == 1:
		continue
	else:
		ans *= 3
	ans %= mod
print (ans)

Submission status: Accepted

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

MOD = 1000000007


pattern = []
i = 0
while i < N - 1:
    if S1[i] == S1[i + 1]:
        pattern.append('-')
        i += 2
    else:
        pattern.append('|')
        i += 1
else:
    if i == N - 1:
        pattern.append('|')

cnt = 3 if pattern[0] == '|' else 6
for i in range(1, len(pattern)):
    l = pattern[i - 1]
    r = pattern[i]
    if (l, r) == ('|', '|'):
        cnt *= 2
    elif (l, r) == ('|', '-'):
        cnt *= 2
    elif (l, r) == ('-', '|'):
        cnt *= 1
    elif (l, r) == ('-', '-'):
        cnt *= 3
    else:
        raise Exception
    cnt %= MOD

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = int(1e9) + 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:
    #print(ans, i,s1[i],s2[i],s1[i-1],s2[i-1])
    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: Accepted

Solution code:


def submit():
    n = int(input())
    s1 = input()
    s2 = input()
    modp = 1000000007

    curr = 0
    ans = 1
    prev = 0 # 縦向きなら1, 横向きなら2
    while curr < n:
        if s1[curr] == s2[curr]:
            # 縦向き
            if prev == 0:
                ans = 3
            elif prev == 1:
                ans *= 2
                ans %= modp
            prev = 1
            curr += 1
        else:
            if prev == 0:
                ans = 6
            elif prev == 1:
                ans *= 2
                ans %= modp
            else:
                ans *= 3
                ans %= modp
            prev = 2
            curr += 2
    print(ans)


submit()

Submission status: Accepted

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

def main():
    n = int(input())
    s1 = input()
    s2 = input()
    i = 0
    res = 1
    while i < n:
        if i == 0:
            if s1[i] == s2[i]:
                res *= 3
                i += 1
                pretwo = False
            else:
                res *= 6
                i += 2
                pretwo = True
        else:
            if s1[i] == s2[i]:
                res *= (1 if pretwo else 2)
                i += 1
                pretwo = False
            else:
                res *= (3 if pretwo else 2)
                i += 2
                pretwo = True
    print(res % (10 ** 9 + 7))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 1

T = [0] * len(S1)

if S1[0] == S2[0]:
    T[0] = 1
else:
    T[0] = T[1] = 1
    ans *= 2

ans *= 3
MOD = 10 ** 9 + 7

for i in range(len(S1)-1):
    if T[i] == 0:
        T[i] = 1
        if S1[i] == S1[i+1]:  # 2 or 4
            T[i+1] = 1
            if S1[i-1] == S2[i-1]:  # 2
                ans *= 2
                ans %= MOD
            else:  # 4
                ans *= 3
                ans %= MOD

        else:  # 1 or 3
            if S1[i-1] == S2[i-1]:  # 1
                ans *= 2
                ans %= MOD
            else:  # 3
                pass

if T[-1] == 0:
    if S1[-2] == S2[-2]:
        ans *= 2
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s1=input()
s2=input()
if s1[0]==s2[0]:
    i=1
else:
    i=0
ans=3

flag=False
while i<n:
    if s1[i]==s2[i]:
        if flag:
            flag=False
            i+=1
        else:
            ans*=2
            i+=1
    else:
        if flag:
            ans*=3
            i+=2
        else:
            ans*=2
            i+=2
            flag=True

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

Submission status: Accepted

Solution code:
n=int(input())
s1=input()
s2=input()
if n>1:
    if s1[0]==s1[1]:
        i=0
    else:
        i=1
else:
    i=1
ans=3

flag=False
while i<n:
    if i<n-1:
        if s1[i]==s1[i+1]:
            if flag:
                ans*=3
                i+=2
            else:
                ans*=2
                i+=2
                flag=True
        else:
            if flag:
                flag=False
                i+=1
            else:
                ans*=2
                i+=1
    else:
        if flag:
            flag=False
            i+=1
        else:
            ans*=2
            i+=1
print(ans%(10**9+7))

Submission status: Accepted

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

lis = []
i = 0
while i < N:
  if i == N-1:
    lis.append(1)
    i += 1
  elif S1[i] == S1[i+1]:
    lis.append(2)
    i += 2
  else:
    lis.append(1)
    i += 1
#print(lis)
ans = 3
if lis[0]==2:
  ans = 6
for i in range(len(lis)-1):
  if lis[i]==2:
    if lis[i+1]==2:
      ans *= 3
  else:
    ans *= 2
  ans %= 10**9+7
print(ans)

#print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#071_D
n = int(input())
s = [input() for _ in range(2)]
mod = 10 ** 9 + 7

dp = [0 for _ in range(n)]
tate = [s[0][i] == s[1][i] for i in range(n)]

if tate[0]:
    dp[0] = 3
    x = 1
else:
    dp[0] = dp[1] = 6
    x = 2

while x < n:
    if tate[x-1] and tate[x]:
        dp[x] = (dp[x-1] * 2) % mod
    elif tate[x-1]:
        dp[x] = (dp[x-1] * 2) % mod
        dp[x+1] = dp[x]
        x += 1
    elif tate[x-1] == False and tate[x]:
        dp[x] = dp[x-1]
    else:
        dp[x] = (dp[x-1] * 3) % mod
        dp[x+1] = dp[x]
        x += 1
    x += 1
    
print(dp[n-1])

Submission status: Accepted

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

ans = 1
mod = 1000000007
count = 0
flag = True

while count < n:
    if count == 0:
        if s[0][count] == s[1][count]:
            ans *= 3
            count += 1
        else:
            ans *= 3 * 2
            count += 2
            flag = False
    else:
        if flag:
            if s[0][count] == s[1][count]:
                ans *= 2
                count += 1
            else:
                ans *= 2 * 1
                count += 2
                flag = False
        else:
            if s[0][count] == s[1][count]:
                ans *= 1
                count += 1
                flag = True
            else:
                ans *= 3
                count += 2
    ans %= mod

print(ans)

Submission status: Accepted

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

# False->tate True->yoko
if S1[0] == S2[0] :
    ret = 3
    pre = False
    i = 1
else :
    ret = 6
    pre = True
    i = 2

while i < N :
    cur = (S1[i] != S2[i])
    if not pre :
        ret *= 2
    elif pre and cur :
        ret *= 3
    
    ret %= mod
    
    if cur :
        i += 2
    else :
        i += 1
    pre = cur
    
print(ret)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    S1 = input()
    S2 = input()
    MOD = 1000000007
    
    pattern = []
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            pattern.append(0)
            i += 1
        else:
            pattern.append(1)
            i += 2
    
    ans = 3 if pattern[0] == 0 else 6
    for i in range(1, len(pattern)):
        if pattern[i] == 0:
            if pattern[i - 1] == 0:
                ans = ans * 2 % MOD
        else:
            if pattern[i - 1] == 0:
                ans = ans * 2 % MOD
            else:
                ans = ans * 3 % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
seq = [[],[]]
seq[0] = input()
seq[1] = input()
i = 0

ans = 3
cnt_vert = 0
cnt_hor = 0
m = 1000000007
# print(seq)
while i < len(seq[0]):
    if seq[0][i] == seq[1][i]: # vert
        if cnt_vert == 0:
            mult = 1
        elif cnt_vert > 0:
            mult = 2
        else:
            raise ValueError("wtf?")
        cnt_vert += 1
        cnt_hor = 0

    else:
        if cnt_hor == 0:
            mult = 2
        elif cnt_hor > 0:
            mult = 3
        else:
            # print(i, cnt_hor, cnt_vert)
            raise ValueError("wtf hor")
        cnt_vert = 0
        cnt_hor += 1
        i += 1
    
    i += 1
    ans *= mult
    if ans > m:
        ans = ans % m
print(ans)

Submission status: Accepted

Solution code:

m = 1000000007

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

state = ""
ans = 1
for n in range(N):
    s1, s2 = S1[n], S2[n]

    if s1 == s2:
        if state == "":
            ans = (ans*3) % m
        elif state == "tate":
            ans = (ans*2) % m
        state = "tate"
    else:
        if state == "yoko_continue":
            state = "yoko"
            continue
        elif state == "":
            ans = (ans*3*2) % m
        elif state == "tate":
            ans = (ans*2) % m
        elif state == "yoko":
            ans = (ans*3) % m
        state = "yoko_continue"

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


MOD = 1000000007  # type: int


def solve(N: int, S: "List[str]"):
    ans = 1
    pdtype = 0
    i = 0
    while i < N:
        dtype = 2 if S[0][i] != S[1][i] else 1
        ans = {
            (0, 1): lambda: 3,
            (0, 2): lambda: 6,
            (1, 1): lambda: ans * 2,
            (1, 2): lambda: ans * 2,
            (2, 1): lambda: ans,
            (2, 2): lambda: ans * 3,
        }[pdtype, dtype]() % MOD
        i += dtype
        pdtype = dtype
    print(ans)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input().strip())
s1 = input().strip()
s2 = input().strip()
mod = 1000000007
vert = False
hor1 = False
hor2 = False

if s1[0] == s2[0]:
    ans = 3
    vert = True
else:
    ans = 6
    hor1 = True
for i in range(1, n):
    if s1[i] == s2[i]:
        if vert:
            ans = (ans * 2) % mod
        vert = True
        hor1 = False
        hor2 = False
    else:
        if vert:
            ans = (ans * 2) % mod
            vert = False
            hor1 = True
            hor2 = False
        elif hor1:
            vert = False
            hor1 = False
            hor2 = True
        elif hor2:
            ans = (ans * 3) % mod
            vert = False
            hor1 = True
            hor2 = False
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S1=input()
S2=input()
pr=10**9+7
t=0
a=1
c=0
while t<N:
    if S1[t]==S2[t]:
        a=a*(3-c)%pr
        t+=1
        c=1
    else:
        if c==0:
            a=6
        elif c==1:
            a=a*2%pr
        else:
            a=a*3%pr
        t+=2
        c=2
print(a)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

MOD = 10**9+7

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

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

while i < N:
    if S[0][i] == S[1][i]:
        if S[0][i-1] == S[1][i-1]: ans *= 2
        else: ans *= 1
        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:
n = int(input())
s = [input() for _ in range(2)]

ans = 1
law = 10 ** 9 + 7

i = 0
while i < n:
    if s[0][i] == s[1][i]:
        if i == 0:
            ans *= 3
        else:
            ans *= 3 - len({s[0][i-1], s[1][i-1]})
        i += 1
    else:
        if i == 0:
            ans *= 6
        else:
            if s[0][i-1] == s[1][i-1]:
                ans *= 2
            else:
                ans *= 3
        i += 2
    ans %= law
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
s1 = input()
s2 = input()

r = 0
ans = 1

pre_is_x = True
while r < N:
    if r == 0:
        if s1[r] == s2[r]:
            # x
            ans *= 3
            r += 1
            pre_is_x = True
        else:
            # y
            ans *= 6
            r += 2
            pre_is_x = False
    # if pre_is_x == True:

    elif s1[r] == s2[r]:
        # x
        if pre_is_x == True:
            # from x
            ans *= 2
        else:
            # from y
            ans *= 1
        r += 1
        pre_is_x = True
    else:
        # y
        if pre_is_x == True:
            # from x
            ans *= 2
        else:
            # from y
            ans *= 3
        r += 2
        pre_is_x = False

print(ans % mod)



    # ここからが左以外


# exit()
# while r > N:
#     if s1[r] == s2[r]:
#         # ans *= 1
#         if r == 0:
#             ans *= 1
#         # r-1
#         # r += 1
#         if s1[r-1] == s2[r-1]:
#             ans *= 2
#         if s1[r-1] == s2[r-1]:
#             ans *= 1
#         r += 1

#     else:
#         s1[r] != s2[r]:
#         ans *= 2
#         r += 2

Submission status: Accepted

Solution code:

N = int(input())
m = [input() for _ in range(2)]

i = 0
count = 0
prestate = -1
while i < N:
    if i == 0:
        if m[0][0] != m[1][0]:
            count = 6
            prestate = 0
            i += 2
        else:
            count = 3
            prestate = 1
            i += 1
    else:
        if m[0][i] == m[1][i]: 
            if prestate == 1:
                count *= 2
                count %= int(1e9+7)
            i += 1
            prestate = 1
        else:
            if prestate == 0:
                count *= 3
            else:
                count *= 2
            count %= int(1e9+7)
            i += 2
            prestate = 0
            
print(count)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

n = int(input())
s1 = input()
s2 = input()

ans = 1
index =0
if s1[0] == s2[0]:
  ans *= 3
  index = 1
else:
  ans *= 3 * 2
  index = 2
  
while index < n:
  if s1[index-1] == s2[index-1]:
    ans *= 2
    if s1[index] == s2[index]:
      index += 1
    else:
      index += 2
      
  else:
    if s1[index] == s2[index]:
      index += 1
    else:
      ans *= 3
      index += 2
  
  ans %= MOD
      
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
m = [0]
s1 = list(input())
s2 = list(input())
for i in range(n):
    if s1[i] == s2[i]:
        m.append(1)
    else:
        if i % 2 == 0:
            m.append(2)

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

Submission status: Accepted

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

if s1[0] != s2[0]:
    ans = 6
    i = 2
    b = 1
else:
    ans = 3
    i = 1
    b = 0

while i < n:
    if s1[i] != s2[i]:
        i += 2
        if b:
            ans = ans*3%mod
        else:
            ans = ans*2%mod
            b = 1
    else:
        i += 1
        if b:
            b = 0
        else:
            ans = ans*2%mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for _ in range(2)]
mod = 10 ** 9 + 7


def is_vertical(i):
    return s[0][i] == s[1][i]


i = 0
if is_vertical(i):
    ans = 3
    prev_is_vertical = True
    i += 1
else:
    ans = 3 * 2
    prev_is_vertical = False
    i += 2

while i < n:
    if is_vertical(i):
        if prev_is_vertical:
            ans *= 2
        else:
            ans *= 1
        prev_is_vertical = True
        i += 1

    else:
        if prev_is_vertical:
            ans *= 2
        else:
            ans *= 3
        prev_is_vertical = False
        i += 2

    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
mass=[input()]
mass.append(input())
MOD=10**9+7
if mass[0][0]==mass[1][0]:
    ans=3
    x=0
    y=1
    yoko=False
else:
    ans=6
    x=0
    y=2
    yoko=True
while y<n:
    if x==0:
        if mass[x][y]==mass[x+1][y]:#縦
            if yoko:
                y+=1
            else:
                ans*=2
                y+=1
            yoko=False
        else:#横
            if yoko:
                ans*=3
            else:
                ans*=2
            yoko=True
            y+=2
print(ans%MOD)

Submission status: Accepted

Solution code:
n=int(input())
mass=[input()]
mass.append(input())
MOD=10**9+7
if mass[0][0]==mass[1][0]:
    ans=3
    x=0
    y=1
    yoko=False
else:
    ans=6
    x=0
    y=2
    yoko=True
while y<n:
    if x==0:
        if mass[x][y]==mass[x+1][y]:#縦
            yoko=False
            if mass[0][y-1]==mass[1][y-1]:
                ans*=2
                y+=1
            else:
                y+=1
        else:#横
            if yoko:
                ans*=3
            else:
                ans*=2
            yoko=True
            y+=2
print(ans%MOD)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    mod = 1000000007

    N = int(input())
    d = input().rstrip()
    input()
    domino = []
    i = 0
    #横０縦1
    if len(d)==1:
        print(3)
        exit()
    if len(d)==2:
        print(6)
        exit()
    while 1:
        if d[i]==d[i+1]:
            domino.append(0)
            i += 2
        else:
            domino.append(1)
            i += 1
        if i==len(d)-1:
            domino.append(1)
            break
        if i==len(d):
            break
    if domino[0]:
        res = 3
    else:
        res = 6
    for i in range(1, len(domino)):
        if domino[i-1]:
            res *= 2
        else:
            if not domino[i]:
                res *= 3
    print(res%mod)
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
a = input()
b = input()
ans = 0
i = 0
beforeState = True
while i < N:
    if i == 0:
        if a[i] == b[i]:
            ans = 3
            beforeState = True
        else:
            ans = 6
            i += 1
            beforeState = False
    else:
        if a[i] == b[i]:
            if beforeState:
                ans *= 2
            else:
                ans *= 1
            beforeState = True
        else:
            if beforeState:
                ans *= 2
            else:
                ans *= 3
            beforeState = False
            i += 1
    ans = ans%MOD
    i += 1
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc071/tasks/arc081_b
# 横ドミノと縦ドミノの場合わけを考える
# 横ドミノ→横ドミノの場合 : いままでの通り*3通り
# 横ドミノ→縦ドミノ : いままで*1通り ok
# 縦ドミノ→横ドミノ : いままで*2通り ok
# 縦ドミノ→縦ドミノ : いままで*2通り ok

MOD = 10**9+7
N = int(input())
S1 = input()
S2 = input()
pre1 = S1[0]
pre2 = S2[0]

if pre1 != pre2:
    ans = 6
else:
    ans = 3
for s1, s2 in zip(S1[1:], S2[1:]):
    if pre1 == s1 and pre2 == s2:
        pass
    elif pre1 != pre2 and s1 != s2:
        # 横→横
        ans *= 3
    elif pre1 != pre2 and s1 == s2:
        # 横→縦
        pass
    elif pre1 == pre2 and s1 != s2:
        # 縦→横
        ans *= 2
    elif pre1 == pre2 and s1 == s2:
        # 縦→縦
        ans *= 2

    if ans >= MOD:
        ans %= MOD

    pre1, pre2 = s1, s2


print(ans % MOD)

Submission status: Accepted

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

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

# 探索済みかどうかの管理
s = set()

# 答え
ans = 1

if S1[0] == S2[0]:
    ans *= 3
    ans %= mod
    s.add(S1[0])
else:
    ans *= 3 * 2
    ans %= mod
    s.add(S1[0])
    s.add(S2[0])

for i in range(1, N):
    # タテ
    if S1[i] == S2[i]:
        if S1[i - 1] == S2[i - 1]:
            ans *= 2
            ans %= mod
        s.add(S1[i])
    
    # ヨコ
    elif S1[i] not in s and S1[i - 1] == S2[i - 1]:
        ans *= 2
        ans %= mod
        s.add(S1[i])
        s.add(S2[i])
    elif S1[i] not in s:
        ans *= 3
        ans %= mod
        s.add(S1[i])
        s.add(S2[i])

print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    S1=input()
    S2=input()
    L=[0]
    
    #最初：0 縦向き:1 横向き:2
    i=0
    for _ in range(N):
        if S1[i]==S2[i]:
            L.append(1)
            i+=1
        else:
            L.append(2)
            i+=2
        if i>=N:
            break
    ans=1
    
    for i in range(1,len(L)):
        if L[i-1]==0:
            if L[i]==1:
                ans*=3
            else:
                ans*=6
        elif L[i-1]==1:
            ans*=2
        else:
            if L[i]==1:
                continue
            else:
                ans*=3
        ans%=mod
    print(ans)
        
    

main()