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

Solution (Python):
n = int(input())
s = input()+"0"
s2 = input()

i = 0

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

ans = 1

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

    
print(ans)

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

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

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

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

Solution (Python):


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

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

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

print(ans % MOD)

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

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

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

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

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

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

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

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

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

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

print(answer % mod)

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

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

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

MOD = 10 ** 9 + 7

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

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

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

print(ans)

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

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

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

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

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

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

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

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

		tmp = S[i]

print(ans)

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

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

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

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

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

print(ans)

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

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

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

print(ans)

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

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

Solution (Python):


import sys

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

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

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


if grid[1][1] == grid[2][1]:
    cnt = 3
else:
    cnt = 6
for i in range(2, N+1):
    
    if grid[1][i-1] == grid[2][i-1]:
        cnt *= 2
    
    elif grid[1][i-1] != grid[2][i-1] and grid[1][i] != grid[2][i] and grid[1][i-1] != grid[1][i]:
        cnt *= 3
print(cnt % MOD)

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

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

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

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

	print(ans%MOD)

if __name__ == '__main__':
	main()

Solution (Python):
N = int(input())
S = [input(), input()]
mod = 10**9+7
i = 1 + (S[0][0] != S[1][0])
ans = 3 * i

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

print(ans)

Solution (Python):
import sys

MOD = 10 ** 9 + 7

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

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

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

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

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

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

Solution (Python):
n = int(input())
s = [input() for _ in range(2)]
ans = 1
pre_vertical = False
start = 1
flag = False
if s[0][0] == s[1][0]:
    pre_vertical = True
    ans *= 3
else:
    start = 2
    ans *= 6
for i in range(start, n):
    if flag:
        flag = False
        continue
    if s[0][i] == s[1][i]:
        if pre_vertical:
            ans *= 2
        else:
            ans *= 1
        pre_vertical = True
    else:
        if pre_vertical:
            ans *= 2
        else:
            ans *= 3
        pre_vertical = False
        flag = True
    ans %= 1000000007
print(ans)

Solution (Python):
from collections import defaultdict
from collections import deque
mod = int(1e9+7)
N = int(input())
S1 = input()
S2 = input()

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

if S1[0] == S1[1]:
    ans = 6
    for i in range(2, N):
        if S1[i-1] == S1[i]:
            continue
        if S1[i] == S2[i]:
            if S1[i-1] == S2[i-1]:
                ans *= 2
                ans %= mod
            else:
                continue
        else:
            if S1[i-1] == S2[i-1]:
                ans *= 2
                ans %= mod
            else:
                ans *= 3
                ans %= mod
else:
    ans = 3
    for i in range(1, N):
        if S1[i-1] == S1[i]:
            continue
        if S1[i] == S2[i]:
            if S1[i-1] == S2[i-1]:
                ans *= 2
                ans %= mod
            else:
                continue
        else:
            if S1[i-1] == S2[i-1]:
                ans *= 2
                ans %= mod
            else:
                ans *= 3
                ans %= mod

print(ans)

Solution (Python):

si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=int(input())
s1=list(input())
s2=list(input())
i=0
mod=1000000007
 
ans=0
p=0
while i<n:
    if s1[i]==s2[i]:
        
        if p==0:
            ans=3
        elif p==1:
            ans*=2
            ans=ans%mod
        elif p==2:
            ans*=1
            ans=ans%mod
        i+=1
        p=1
    else:
        
        if p==0:
            ans=6
        elif p==1:
            ans*=2
            ans=ans%mod
        elif p==2:
            ans*=3
            ans=ans%mod
        i+=2
        p=2
print(ans)

Solution (Python):
MOD = 1000000007
N = int(input())
S1 = input()
S2 = input()
if S1[0] == S2[0]:
    ans = 3
    p = 1
    i = 1
else:
    ans = 6
    p = 0
    i = 2

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = [input() for i in range(2)]
prev = 0 
if s[0][0] == s[1][0]:
    res = 3
    i = 1
    prev = 1
else:
    res = 6
    i = 2
while i < n:
    if s[0][i] == s[1][i]:
        if prev:
            res = (res*2) % mod
        i += 1
        prev = 1
    else:
        if prev:
            res = (res*2) % mod
        else:
            res = (res*3) % mod
        i += 2
        prev = 0
print(res)

Solution (Python):
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)

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):
        
        if x[i-1]==0:
            c*=2
        else:
            if x[i]==1:
                c*=3
        c%=1000000007

    print(c%1000000007)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
S, _ = input()+'_', input()

A = []

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

p = A[0]
ans = 3 if p==1 else 6
mod = 10**9+7
for a in A[1:]:
    d = 2 if p==1 else (1 if a==1 else 3)
    ans = (ans*d)%mod
    p = a

print(ans)

Solution (Python):
N=int(input())
S=input()
DIV=1000000007
ans=1
import itertools
wasTate=True
first=True
for key,g in itertools.groupby(S):
  if len(list(g))==1:
    
    if first:
      
      ans=((ans%DIV)*3)%DIV
      first=False
    elif wasTate:
      
      ans=((ans%DIV)*2)%DIV
      wasTate=True
    else:
      
      wasTate=True
  else:
    
    if first:
      ans=((ans%DIV)*6)%DIV
      
      
      
      first=False
      wasTate=False
    elif wasTate:
      
      ans=((ans%DIV)*2)%DIV
      wasTate=False
    else:
      
      
      
      ans=((ans%DIV)*3)%DIV
      wasTate=False
      
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

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

main()

Solution (Python):
N = int(input())
S1 = list(input())
S2 = list(input())
ans = 1
MOD = 1000000007
flag_1 = False

if S1[0] == S2[0]:
    ans *= 3
    flag = 'X'
else:
    ans *= 6
    flag = 'Y'

for i in range(1,N):
    if i == 1 and flag == 'Y':
        continue
    if flag_1:
        flag_1 = False
        continue
    if S1[i] == S2[i]:
        if flag == 'X':
            ans *= 2
        else:
            flag = 'X'
    else:
        if flag == 'X':
            ans *= 2
            flag = 'Y'
        else:
            ans *= 3
        flag_1 = True
    ans %= MOD
print(ans)

Solution (Python):
n = int(input())
b = []
s1, s2 = input(), input()
now = 0
while now < n:
  if s1[now] == s2[now]:
    b.append(1)
    now += 1
  else:
    b.append(0)
    now += 2
if b[0]:
  ans = 3
else:
  ans = 6
for i in range(len(b)-1):
  if b[i]:
    ans *= 2
  elif not b[i+1]:
    ans *= 3
  ans %= 10**9+7
print(ans)

Solution (Python):

import sys

MOD = 1000000007  


def solve(N: int, S: "List[str]"):
    """
    0は縦に入っている1は横に入っていることを表す
    """
    dominos = []
    i = 0
    while i < N:
        if S[0][i] == S[1][i]:
            dominos.append(0)
        else:
            dominos.append(1)
            i += 1
        i += 1

    answer = 3 if dominos[0] == 0 else 6
    for i in range(1,len(dominos)):
        if dominos[i] == 0 and dominos[i-1] == 0:
            answer *= 2
        elif dominos[i] == 1 and dominos[i-1] == 0:
            answer *= 2
        elif dominos[i] == 0 and dominos[i-1] == 1:
            answer *= 1
        elif dominos[i] == 1 and dominos[i-1] == 1:
            answer *= 3
        answer %= MOD
    print(answer%MOD)
    return


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

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = input()
T = input()
ans = 3 if S[0] == T[0] else 6
for i in range(1, N):
    if S[i-1] == T[i-1]:
        ans *= 2
    elif S[i] == S[i-1]:
        pass
    else:
        ans *= 1 if S[i] == T[i] else 3
print(ans % (10**9+7))

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

ans = 1
prev = 0
i = 0
while i < len(s1):
    if s1[i] == s2[i]:
        ans *= (3 - prev)
        prev = 1
        i += 1
    else:
        if prev == 0:
            ans *= 6
        elif prev == 1:
            ans *= 2
        else:
            ans *= 3
        prev = 2
        i += 2
    ans %= 1000000007
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
s = SRL(2)
i = 0
ans = 1
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)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[list(input()) for _ in range(2)]
    ans=1
    i=0
    while(i<n):
        
        if(A[0][i]==A[1][i]):
            if(i==0): ans*=3
            elif(A[0][i-1]==A[1][i-1]): ans*=2
            else: pass
            i+=1
        
        else:
            if(i==0): ans*=6
            elif(A[0][i-1]==A[1][i-1]): ans*=2
            else: ans*=3
            i+=2

    print(ans%MOD)
resolve()

Solution (Python):
N = int(input())
S1 = list(input())
S2 = list(input())

mod = 1000000007

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

Solution (Python):
N = int(input())
s12 = [list(input()), list(input())]
index = 0
left_block = None
point_dict = {"X": {"X": 2, "Y": 1}, "Y": {"X": 2, "Y": 3}}
point = 1
n3 = 0
n2 = 0
n1 = 0
while True:
    if index >= N:
        break
    if left_block:
        if s12[0][index] == s12[1][index]:
            now_block = "X"
            index += 1
        else:
            now_block = "Y"
            index += 2
        point *= point_dict[now_block][left_block]
        left_block = now_block
    else:
        if s12[0][0] == s12[1][0]:
            left_block = "X"
            index += 1
            point *= 3
        else:
            left_block = "Y"
            index += 2
            point *= 6

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

Solution (Python):
N = int(input())
grids = [[s for s in input()],[s for s in input()]]
MOD = 1000000007

if grids[0][0] == grids[1][0]:
  prv_row_type = 1
  ans = 3
  posx = 1
else:
  prv_row_type = -1
  ans = 6
  posx = 2

while posx < N:
  if grids[0][posx] ==  grids[1][posx]:
    if prv_row_type == 1: ans  *= 2
    else: ans *= 1
    prv_row_type = 1
    posx += 1
  else:
    if prv_row_type == 1: ans *= 2
    else: ans *= 3
    prv_row_type = -1
    posx += 2

print(ans%MOD)

Solution (Python):
N = int(input())
s1 = input()
s2 = input()
p = 0
n = 0
ans = 1
while n < N:
    if p == 1:
        if s1[n] == s2[n]:
            ans *= 2
            n += 1
        else:
            ans *= 2
            n += 2
            p = 2
    elif p == 2:
        if s1[n] == s2[n]:
            
            n += 1
            p = 1
        else:
            ans *= 3
            n += 2
    else:
        if s1[n] == s2[n]:
            ans *= 3
            n += 1
            p = 1
        else:
            ans *= 6
            n += 2
            p = 2
    ans %= 1000000007
    
print(ans)

Solution (Python):

N = int(input())
Sone = list(input())
Stwo = list(input())

mod_by = 7 + 10**9


if Sone[0]==Stwo[0]:
    
    ans = 3
    before_domino = 1
    i = 1
else:
    
    ans = 6 
    before_domino = 0
    i = 2








    
while i < N:
    if Sone[i] == Stwo[i] and before_domino == 1:
        ans *= 2
        before_domino = 1
        i += 1
    elif Sone[i] != Stwo[i] and before_domino == 1:
        ans *= 2
        before_domino = 0
        i += 2
    elif Sone[i] == Stwo[i] and before_domino == 0:
        ans *= 1
        before_domino = 1
        i += 1
    elif Sone[i] != Stwo[i] and before_domino == 0:
        ans *= 3
        before_domino = 0
        i += 2
        
print(ans%mod_by)

Solution (Python):
N = int(input())
S1 = list(input())
S2 = list(input())
cnt= 0
ans = 0
flag= 0
while cnt<N:
  if S1[cnt]==S2[cnt]:
    if cnt==0:
      ans+=3
    elif flag==1:
      ans*=2
    elif flag==2:
      ans*=1
    flag=1
    cnt+=1
  elif S1[cnt]!=S2[cnt]:
    if cnt==0:
      ans +=6
    elif flag==1:
      ans*=2
    elif flag==2:
      ans*=3
    flag=2
    cnt+=2
  ans %=(10**9+7)
print(ans)

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

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
cur = 0
ans = []; S = [[] for _ in range(2)]
for i in range(2):
    S[i] = str(input())

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

cur = int(1)
for i in range(len(C)):
    if i==0:
        if C[i]==0:
            cur *= 3
        else:
            cur *= 6
    else:
        if not (C[i-1]==1 and C[i]==0):
            if (C[i-1]==1 and C[i]==1):
                cur *=3
            else:
                cur *= 2

ans = cur%mod
print(ans)

Solution (Python):
n = int(input())

s1 = input()
s2 = input()

INF = 1000000007

left = None
index = 0
cnt = 0
while index < n:
    
    if s1[index] == s2[index]:
        index += 1
        if left is None:
            left = 1
            cnt = 3
        
        elif left == 1:
            cnt *= 2
        
        else:
            cnt *= 1
        left = 1

    
    else:
        index += 2
        if left is None:
            left = 2
            cnt = 6
        
        elif left == 1:
            cnt *= 2
        
        else:
            cnt *= 3
        left = 2
    cnt = cnt % INF
print(cnt)