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):
import sys

N=int(input())

S=input()

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

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



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

Solution (Python):
MOD = 10**9+7

N = int(input())

X = input()
input()

from itertools import chain

d = {(2,2):3, (1,2):1, (2,1):2, (1,1):2, (2,0):6, (1,0):3, (0,0):1}

r = 1
p = 0
n = 0
l = None
for x in chain(X,(None,)):
  if x == l:
    n += 1
  else:
    l = x
    r *= d[(n,p)]
    r %= MOD
    p = n
    n = 1

print(r)

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


if S1[i] != S2[i]:
    res = 6
    i+=2
    rear = 1
else :
    res = 3
    i+=1
    rear = 0

while i != N:
    if S1[i] != S2[i]:
        if rear == 1:
            res *= 3
        else:
            res *= 2
        rear = 1
        i += 2

    else:
        if rear == 0:
            res *= 2
        i += 1
        rear = 0


print(res%1000000007)

Solution (Python):

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

domino = []

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

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

for n in range(1, len(domino)):
    if domino[n]: 
        if domino[n-1]: 
            res *= 2
    else:
        if domino[n-1]:
            res *= 2
        else:
            res *= 3
     
print(res%1000000007)

Solution (Python):
import numpy as np


def getInput():
    separator = ' '
    ret_array = []
    while True:
        try:
            row = input().split(sep=separator)
            ret_array.append(row)
        except EOFError:
            break
    return ret_array


g = getInput()

N = np.int32(g[0][0])


ls = 0
cs = None
l = []
i = 0
hoge=[]
try:
    while True:
        
        hoge.append(g[2][0][i])
        if g[1][0][i] == g[2][0][i]:
            cs = 2
            i += 1
        else:
            cs = 1
            i += 2

        if ls == 0:
            if cs == 1:
                l.append(6)
            else:
                l.append(3)
        elif ls == 1:
            if cs == 1:
                l.append(3)
            else:
                l.append(1)
        else:
            l.append(2)

        ls = cs

except IndexError:
    print(np.mod(np.prod(np.array(l, dtype=np.int32)),1000000007))

Solution (Python):


def ColoringDominoes(N, S1, S2):

    pattern = list()
    i = 0
    while True:
        if S1[i] == S2[i]:
            pattern.append(True)
            i += 1
        else:
            pattern.append(False)
            i += 2
        if i >= N:
            break

    if pattern[0]:
        n_pattern = 3
    else:
        n_pattern = 6
    for i in range(1, len(pattern)):
        if pattern[i-1] and pattern[i]:
            n_pattern *= 2
        elif pattern[i-1] and not(pattern[i]):
            n_pattern *= 2
        elif not(pattern[i-1]) and not(pattern[i]):
            n_pattern *= 3

    return n_pattern % 1000000007




if __name__ == "__main__":
    N = int(input())
    S1 = list(str(input()))
    S2 = list(str(input()))
    print(ColoringDominoes(N, S1, S2))

Solution (Python):
a = []
x = input()
str1 = raw_input()
str2 = raw_input()
count = 0
while True:
    if count>x-1:
        break
    if str1[count] == str2[count]:
        a.append("v")
        count+=1
    else:
        a.append("h")
        count+=2
total = 1
if a[0] == "h":
    total*=6
if a[0] == "v":
    total*=3
for i in range(1, len(a)):
    if a[i] == "v" and a[i-1] == "h":
        total *=1
        total = total%1000000007
    elif a[i] == "h" and a[i-1] == "v":
        total*=2
        total = total%1000000007
    elif a[i] == "v" and a[i-1] == "v":
        total*=2
        total = total%1000000007
    elif a[i] == "h" and a[i-1] == "h":
        total*=3
        total = total%1000000007
print total

Solution (Python):
n = input()
st1 = raw_input()
st2 = raw_input()
m = 1
mod = 1000000007
pat = 0 
bl = False
for i in range(n):
  
  if pat == 2 and bl:
    bl = False
    continue
  if st1[i] == st2[i] and pat == 0:
    m = m*3%mod
    pat = 1
  elif st1[i] == st2[i] and pat == 1:
    m = m*2%mod
    pat = 1
  elif st1[i] == st2[i] and pat == 2:
    pat = 1
  elif st1[i] != st2[i] and pat == 0:
    m = m*6%mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat == 1:
    m = m*2%mod
    pat = 2
    bl = True
  elif st1[i] != st2[i] and pat == 2:
    m = m*3%mod
    pat = 2
    bl = True
print m

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


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


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

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

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

    print(cases % 1000000007)

Solution (Python):
input()

a =raw_input()

edge = []

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

ans = 1

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

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

print ans

Solution (Python):
n = int(input())
s1 = input() + " "
s2 = input() + " "
 
mod = 1000000007
 
num = 1
i = 0
b = 0
tmp_t = -1
while(b + i < n):
    if s1[i + b] == s2[i + b]: 
        if tmp_t == 0:
            num = (num * 2) % mod
        elif tmp_t == 1:
            num = (num * 1) % mod
        else:
            num = 3
        tmp_t = 0
    else: 
        if tmp_t == 0:
            num = (num * 2) % mod
        elif tmp_t == 1:
            num = (num * 3) % mod
        else:
            num = 6
        tmp_t = 1
        b += 1
    i += 1
 
print(num)

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

mod = 1000000007

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

print(num)

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

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

M=1000000007

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

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

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

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

    b=a[:]

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

print(count%M)

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

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

			if(i == len(a1) - 1):
				x = x*2

		continue

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

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

			if(i == len(a1) - 1):
				x = x*2


		continue

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

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

			if(i == len(a1) - 1):
				x = x*2

		continue


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

else:
	print(x % 1000000007)

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

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

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

print(m)

Solution (Python):


MOD = 1000000007
N = int(input())
U = input() + ' '
D = input()

s = ''
c = 0
while c < len(U)-1:
    if U[c] == U[c+1]:
        s += 'L'
        c += 2
    else:
        s += 'S'
        c += 1


l = s[0]
a = 3 if l == 'S' else 6
for i in s[1:]:
    if l == i == 'S':
        a = (a * 2) % MOD
    elif l == i == 'L':
        a = (a * 3) % MOD
    elif l == 'S' and i == 'L':
        a = (a * 2) % MOD
    l = i
print(a)

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

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

ans = 1

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

print(ans)

Solution (Python):
N = int(input())
board = [input(), input()]

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


if board[0][0] == board[0][1]:
    cnt, prev = 6, 0
else:
    cnt, prev = 3, 1
mod = 10 ** 9 + 7

for i in range(1, N):
    if board[0][i] == board[0][i - 1]:
        continue
    elif i < N - 1 and board[0][i] == board[0][i + 1] and prev == 0:
        cnt *= 3
        cnt %= mod
    elif i < N - 1 and board[0][i] == board[0][i + 1] and prev == 1:
        cnt *= 2
        cnt %= mod
        prev = 0
    elif board[0][i] == board[1][i] and prev == 0:
        prev = 1
    else:
        cnt *= 2
        cnt %= mod
print(cnt)

Solution (Python):
def solve(s1):
    div = 1000000007
    s1 = iter(s1)
    try:
        a = next(s1)
        b = next(s1)
    except:
        return 3
    if a != b:
        a = b
        try:
            b = next(s1)
        except:
            return 6
    ans = 3
    state = 0
    while True:
        if a == b:
            ans *= 3 if state else 2
            ans %= div
            try:
                a = next(s1)
                b = next(s1)
            except:
                return ans
            state = 1
        else:
            ans *= 1 if state else 2
            ans %= div
            try:
                a = b
                b = next(s1)
            except:
                return ans * 2 % div
            state = 0


input()
print(solve(input().strip()))

Solution (Python):
def main():
    N = int(input())
    S1 = list(input())
    S2 = list(input())
    d = 10**9 + 7
    

    skip = False
    Map = {("p","v"):3, ("p","h"):6, ("v","h"):2, ("h","v"):1, ("h","h"):3, ("v","v"):2}
    pre = "p"

    possibles = 1
    for n in range(N):
        if skip:
            skip = False
            continue
        pass
        if S1[n] == S2[n]:  
            
            now = "v"
        else:  
            
            now = "h"
            skip = True
        possibles *= Map[(pre,now)]
        possibles %= d
        
        pre = now

    print(possibles)

        
if __name__ == "__main__":
    main()

Solution (Python):
import sys
N=int(input())
S=str(input())
M=str(input())
Mo=10**9+7
ans=1
i=0
if S[i]==M[i]:
  Ag=1
  ans=ans*3
  i+=1
else:
  Ag=2
  ans=ans*6
  i+=2
while i<N:
  if S[i]==M[i]:
    if Ag==1:
      ans=ans*2%Mo
      Ag=1
      i+=1
    elif Ag==2:
      Ag=1
      i+=1
  else:
    if Ag==1:
      ans=ans*2%Mo
      Ag=2
      i+=2
    elif Ag==2:
      ans=ans*3%Mo
      Ag==2
      i+=2
print(ans%Mo)

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
s3 = ""
i = 0
while i < len(s1):
    if s1[i] == s2[i]:
        s3 += "T"
    else:
        s3 += "Y"
        i += 1
    i += 1
ret = 1
for i in range(len(s3)):
    if i == 0:
        if s3[i] == "T":
            ret *= 3
        else:
            ret *= 6
    else:
        if s3[i] == "T" and s3[i-1] == "T":
            ret *= 2
        if s3[i] == "Y":
            if s3[i-1] == "T":
                ret *= 2
            else:
                ret *= 3
        ret %= 1000000007
print(ret)

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

ans = 0
tate = False
i = 0
if (s1[i] == s2[i]):
    ans = 3
    tate = True
    i = 1
else:
    ans = 6
    i = 2

while i < n:
    if (s1[i] == s2[i]):
        if tate:
            ans *= 2
            ans %= 1000000007
        tate = True
        i += 1
    else:
        if tate:
            ans *= 2
            ans %= 1000000007
        else:
            ans *= 3
            ans %= 1000000007
        tate = False
        i += 2

print(ans)

Solution (Python):
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))
def plis(a): return " ".join(list(map(str, a)))

N = ri()
S1 = rls()
S2 = rls()
mode = None
mode_p = None
ans = 0
mod = 10**9 + 7

i = 0
while(i < N):
    if(S1[i] == S2[i]):
        if(mode is None):
            mode = "c"
        else:
            mode_p = mode
            mode = "c"
    else:
        i += 1
        if(mode is None):
            mode = "r"
        else:
            mode_p = mode
            mode = "r"
    
    if(mode_p is None):
        ans = 3 if mode == "c" else 6
    else:
        if(mode_p == "c"):
            ans = ans*2%mod
        elif(mode == "r"):
            ans = ans*3%mod
    i += 1

print(ans)

Solution (Python):

import sys

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

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

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

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

	print(n_ptrn % 1000000007)



if __name__ == '__main__':
	main()

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

MOD = 1000000007
if s1[0] == s2[0]:
    ans = 3
    vertical = True
    i = 1
else:
    ans = 6
    vertical = False
    i = 2
while i < n:
    if s1[i] == s2[i]:
        if vertical:
            ans *= 2
        vertical = True
        i += 1
    else:
        if vertical:
            ans *= 2
        else:
            ans *= 3
        vertical = False
        i += 2
    ans %= MOD
print(ans)

Solution (Python):
modulus = 1000000007

n = input()
s = list(zip(input(), input()))

def sliding_window(it):
    it = iter(it)
    fst = next(it)
    for snd in it:
        yield fst, snd
        fst = snd

if n == 1:
    print(3)
elif n == 2:
    print(6)
else:
    ans = 0
    if s[0][0]==s[0][1]:
        ans += 3
    else:
        ans += 6
    for x in sliding_window(s):
        if x[0][0] == x[0][1]:
            ans = ans * 2 % modulus
        elif x[0][0] != x[1][0]:
            if x[1][0] != x[1][1]:
                ans = ans * 3 % modulus
    print(ans)

Solution (Python):



from math import *
import random

def readln():
    return list(map(int,(input().split(" "))))

def add(x,y):
    return (x + y) % 1000000007

N = int(input())
A = input()
B = input()

F = [0 for i in range(N)]
sum = [0 for i in range(N)]

F[0] = [[0 for j in range(3)] for i in range(3)]
if(A[0] == B[0]):
    for i in range(3):
        F[0][i][i] = 1
    sum[0] = 3
else:
    for i in range(3):
        for j in range(3):
            if(i != j):
                F[0][i][j] = 1
    sum[0] = 6

for idx in range(1,N):
    F[idx] = [[0 for j in range(3)] for i in range(3)]

    if(A[idx] == B[idx]):
        for i in range(3):
            for j in range(3):
                for k in range(3):
                    if((k != i) and (k != j)):
                        value = F[idx-1][i][j]
                        F[idx][k][k] = add(F[idx][k][k],value)
                        sum[idx] = add(sum[idx],value)
    else:
        if(A[idx] == A[idx-1]):
            for i in range(3):
                for j in range(3):
                    F[idx][i][j] = F[idx-1][i][j]
                    sum[idx] = sum[idx-1]
        else:
            for i in range(3):
                for j in range(3):
                    for k in range(3):
                        for l in range(3):
                            if((i != k) and (j != l) and (k != l)):
                                value = F[idx-1][i][j]
                                F[idx][k][l] = add(F[idx][k][l],value)
                                sum[idx] = add(sum[idx],value)
print(sum[N-1])

Solution (Python):

def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    S_1 = str(input())
    S_2 = str(input())
    return N, S_1, S_2


def solve(N, S_1, S_2):
    ind = 0
    l_sum = []
    while ind <= N - 1:
        if ind == N - 1:
            l_sum.append("a")
            ind += 1
            continue
        now = S_1[ind]
        next = S_1[ind + 1]
        if now == next:
            l_sum.append("b")
            ind += 2
        else:
            l_sum.append("a")
            ind += 1

    if l_sum[0] == "a":    
        ans = 3
    else:
        ans = 6
    for i in range(1, len(l_sum)):
        pre = l_sum[i - 1]
        now = l_sum[i]
        if pre == "a":
            ans *= 2
        else:
            if now == "b":
                ans *= 3

    return ans % (10 ** 9 + 7)


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Solution (Python):
MOD = 1000000007


def solve(n, s1, s2, allowed):
    if n == 0:
        return 1

    if s1[0] == s2[0]:
        return (allowed * solve(n - 1, s1[1:], s2[1:], 2)) % MOD
    else:
        if allowed == 3:
            mul = 6
        elif allowed == 2:
            mul = 2
        else:
            mul = 3
        return (mul * solve(n - 2, s1[2:], s2[2:], 1)) % MOD


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

if __name__ == '__main__':
    main()

Solution (Python):
n = input()
S = [raw_input() for i in xrange(2)]

dp = [[[0]*3 for i in xrange(3)] for j in xrange(n)]

MOD = 10**9 + 7

if S[0][0] == S[1][0]:
    for i in xrange(3):
        dp[0][i][i] = 1
else:
    for i in xrange(3):
        for j in xrange(3):
            if i == j:
                continue
            dp[0][i][j] = 1

for i in xrange(1, n):
    if S[0][i-1] == S[0][i]:
        for p in xrange(3):
            for q in xrange(3):
                dp[i][p][q] = dp[i-1][p][q]
    else:
        if S[0][i-1] == S[1][i-1]:
            if S[0][i] == S[1][i]:
                
                
                for s in xrange(3):
                    for t in xrange(3):
                        if s == t:
                            continue
                        dp[i][s][s] += dp[i-1][t][t]
                        dp[i][s][s] %= MOD
            else:
                
                
                for u in xrange(3):
                    for s in xrange(3):
                        if u == s:
                            continue
                        for t in xrange(3):
                            if u == t or t == s:
                                continue
                            dp[i][s][t] += dp[i-1][u][u]
                            dp[i][s][t] %= MOD
        else:
            if S[0][i] == S[1][i]:
                
                
                for u in xrange(3):
                    for s in xrange(3):
                        if u == s:
                            continue
                        for t in xrange(3):
                            if u == t or t == s:
                                continue
                            dp[i][u][u] += dp[i-1][s][t]
                            dp[i][u][u] %= MOD
            else:
                
                
                for p in xrange(3):
                    for q in xrange(3):
                        if p == q:
                            continue
                        for s in xrange(3):
                            if p == s:
                                continue
                            for t in xrange(3):
                                if s == t or q == t:
                                    continue
                                dp[i][s][t] += dp[i-1][p][q]
ans = 0
for i in xrange(3):
    for j in xrange(3):
        ans += dp[n-1][i][j]
print ans % MOD

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    s1 = S()
    s2 = S()
    r = 6
    i = 2
    c = 2
    if s1[0] == s2[0]:
        r = 3
        i = 1
        c = 1
    while i < n:
        if s1[i] == s2[i]:
            if c == 1:
                r *= 2
            else:
                pass
            c = 1
            i += 1
        else:
            if c == 1:
                r *= 2
            else:
                r *= 3
            c = 2
            i += 2
        r %= mod

    return r

print(main())

Solution (Python):
n = int(input())
ans = 1
s1 = input()
s2 = input()
i = 0
last = ""
MOD = 1000000007

while i < n:
    if s1[i] == s2[i]:
        if last == "": ans = 3
        elif last == "V": ans = (ans*2) % MOD
        last = "V"
        i+= 1
    else:
        if last == "": ans = 6
        elif last == "V": ans = (ans*2) % MOD
        else: ans = (ans*3) % MOD
        last = "H"
        i+= 2
print(ans)