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())
S1 = input()
S2 = input()
S1 += "0"
old_shape = ""

if S1[0] == S1[1]:
    ans = 6
    old_shape = "yoko"
    i = 2
else:
    ans = 3
    old_shape = "tate"
    i = 1

while i < N:
    if S1[i] == S1[i+1]:
        if old_shape == "tate":
            ans = (ans*2)%1000000007
            
        else:
            ans = (ans*3)%1000000007
            
        i += 2
        old_shape = "yoko"
    
    else:
        if old_shape == "tate":
            ans = (ans*2)%1000000007
        
        i += 1
        old_shape = "tate"

print(ans)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
S = S1 + "0"
ans = 3
status = ""
i = 0
while i<N:
    if S[i]==S[i+1]:
        if status == "y":
            ans *= 3
        else:
            ans *= 2
        status = "y"
        i += 2
    else:
        if status == "t":
            ans *= 2
        status = "t"
        i += 1
    ans %= 1000000007
print(ans)

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

result = 3
if N != 1:
    i=1
    while i < N:
        if S1[i-1] == S2[i-1]:
            result *= 2
        elif S1[i-1] != S1[i]:
            if S1[i] != S2[i]:
                result *= 3
        elif i == 1:
            result *= 2
        i += 1

print(result%1000000007)

Solution (Python):
N=int(input())
S1=input()
S2=input()
c=1

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

Solution (Python):
N=input()
s1=input()+"000"
s2=input()+"000"
ans=3
status=1
place=0
while True:
    if s1[place]=="0":
        break
    if status==1:
        if s1[place]==s2[place]:
            status=3
            place+=1
        else:
            ans=ans*2
            status=2
            place+=2
    elif status==2:
        if s1[place]==s2[place]:
            status=3
            place+=1
        else:
            ans=ans*3
            place+=2
    elif status==3:
        ans=ans*2
        if s1[place]==s2[place]:
            place+=1
        else:
            status=2
            place+=2
print(ans%1000000007)

Solution (Python):
n = int(raw_input())
s1 = raw_input()
s2 = raw_input()
used = 0
pat = 1
i = 0
while i < n:
    if s1[i] == s2[i]:
        pat = pat*(3 - used) % (10**9+7)
        used = 1
        i += 1
    else:
        if used == 0:
            pat = pat*6 % (10**9+7)
        else:
            pat = pat*(used + 1) % (10**9+7)
        used = 2
        i += 2
print pat

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

mod=1000000007
if s1[0]==s2[0]:
    anser=3
    p=1
else:
    anser=6
    p=2

while p<n:
    if s1[p]==s2[p]:
        if s1[p-1]==s2[p-1]:
            anser*=2
        p+=1
    else:
        if s1[p-1]==s2[p-1]:
            anser*=2
        else:
            anser*=3
        p+=2
    anser%=mod
print(anser)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
data = []
i = 0
while i < N:
    try:
        if S1[i] == S1[i + 1]:
            data.append(2)
            i += 2
        else:
            data.append(1)
            i += 1
    except IndexError:
        data.append(1)
        break
ans = 6 if data[0] == 2 else 3
for j in range(len(data[1:])):
    if data[j] == 1:
        ans *= 2
    elif data[j + 1] == 2:
        ans *= 3
    ans %= 1000000007
print(ans)

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

    mod_ = 1000000007
    n = N
    if S1[0] == S2[0]:
        fill = 3
        i = 1
    else:
        fill = 6
        i = 2

    while i < N:
        if S1[i] == S2[i]:
            if S1[i-1] == S2[i-1]:
                fill *= 2
            i += 1
        else:
            if S1[i-1] == S2[i-1]:
                fill *= 2
            else:
                fill *= 3
            i += 2

    print(fill % mod_)

main()

Solution (Python):
def D_Coloring_Dominoes(N, S1, S2):
    from collections import deque
    S1, S2 = deque(S1), deque(S2)

    def decisionBlock(s1, s2):
        
        if s1[0] == s2[0]:
            block = 'X'  
            s1.popleft()
            s2.popleft()
        elif s1[0] == s1[1] and s2[0] == s2[1]:
            block = 'Y'
            s1.popleft()
            s1.popleft()
            s2.popleft()
            s2.popleft()
        else:
            tmp = 'NotBlock'  
        return block

    combination = 0

    
    firstblock = decisionBlock(S1, S2)
    if firstblock == 'X':
        combination += 3
    else:
        combination += 6

    
    leftblock = firstblock
    while S1 != deque([]):
        block = decisionBlock(S1, S2)
        if (leftblock, block) == ('X', 'X'):
            combination *= 2
        elif (leftblock, block) == ('Y', 'X'):
            combination *= 1
        elif (leftblock, block) == ('X', 'Y'):
            combination *= 2
        elif (leftblock, block) == ('Y', 'Y'):
            combination *= 3
        leftblock = block
    return combination%(10**9+7)

N = int(input())
S1 = input()
S2 = input()
print(D_Coloring_Dominoes(N, S1, S2))

Solution (Python):
import sys




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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


M = 10 ** 9 + 7


def main():
    n = read_int()
    a = [read_str(), read_str()]
    res = 1
    last_vertical = None
    i = 0
    while i < n:

        vertical = a[0][i] == a[1][i]
        if i == 0:
            if vertical:
                res = 3
            else:
                res = 6
        else:
            if vertical:
                if last_vertical:
                    res *= 2
            else:
                if last_vertical:
                    res *= 2
                else:
                    res *= 3
        last_vertical = vertical
        if vertical:
            i += 1
        else:
            i += 2
        res %= M
    print(res)


main()

Solution (Python):
num=raw_input()
tmp=raw_input()
tmp2=raw_input()
bef="none"
n_state=0
af_state=0
if len(tmp)==1:
    out=3
else:
    if tmp[0]==tmp[1]:
        out=6
        n_state=1
        init=2
    else:
        out=3
        init=1
    

    for i in range(init,len(tmp)):
        if tmp[i]!=bef:
            
            if i<int(num)-1:
                if tmp[i]==tmp[i+1]:
                    if n_state==0:
                        out=out*2
                    else:
                        out=out*3
                        n_state=0
                else:
                    if n_state==0:
                        out=out*2
                    else:
                        out=out*1
                        n_state=0
            else:
                if n_state==0:
                    out=out*2
                else:
                    out=out*1
                    n_state=0
        else:
            n_state=1
        bef=tmp[i]
print out % 1000000007

Solution (Python):
from math import factorial

N = int(input())
S1 = input()
S2 = input()
S = list(zip(S1,S2))

new = []
z = 0
while z != len(S):
    if S[z][0] == S[z][1]:
        new.append("V")
    else:
        new.append("H")
        z += 1
    z += 1

if new[0] == "H":
    result = 6
else:
    result = 3
    
for i in range(len(new)-1):
    if new[i] == "H" and new[i+1] == "H":
        result = (result * 3) % 1000000007
    elif new[i] == "H" and new[i+1] == "V":
        result = (result * 1) % 1000000007
    elif new[i] == "V":
        result = (result * 2) % 1000000007
print(result)

Solution (Python):
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n,  = read_line(int)

m = 1000000007

domino = []
domino.append(input())
domino.append(input())




def compress(line):
    x = [line[0]]
    for c in line[1:]:
        if x[-1] != c:
            x.append(c)
    return x

domino[0] = compress(domino[0])
domino[1] = compress(domino[1])

xs = []
for i in range(len(domino[0])):
    xs.append(domino[0][i] != domino[1][i])


patterns = None
if xs[0]:
    patterns = 6
else:
    patterns = 3

lastX = xs[0]
for x in xs[1:]:
    if x:
        
        if lastX:
            patterns *= 3
        else:
            
            patterns *= 2
    else:
        
        if lastX:
            patterns *= 1
        else: 
            patterns *= 2
    lastX = x

print(patterns % m)

Solution (Python):
mod = 1000000007
N = int(input())
S = input()
T = input()
a = 1
b = 0 
i = 0
while i < N:
	if i == 0: 
		if N == 1:
			a *= 3
			break
		if N == 2:
			a *= 6
			break
		else:
			if S[0] == S[1]:
				a *= 6
				i += 2
				b = 0
			else:
				a *= 3
				i += 1
				b = 1
	if i == N-1:
		if b == 0: 
			a *= 1
			i += 1
			b = 1
			break
		if b == 1: 
			a *= 2
			i += 1
			b = 1
			break
	if S[i] == S[i+1]:
		if b == 0: 
			a *= 3
			i += 2
			b = 0
			continue
		if b == 1: 
			a *= 2
			i += 2
			b = 0
			continue
	else:
		if b == 0: 
			a *= 1
			i += 1
			b = 1
			continue
		if b == 1: 
			a *= 2
			i += 1
			b = 1
			continue
print(a % mod)

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


MOD = 1000000007

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




b=[]
bSkip = False

for i in range(N):
	if bSkip:
		bSkip = False
		continue
	if i==N-1:
		b.append(1)
	else:
		if a[i] == a[i+1]:
			b.append(2)
			bSkip = True
		else:
			b.append(1)




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


for i in range(1, len(b)):
	if b[i-1]==1:
		ans = (ans * 2) % MOD
	else:
		if b[i]==2:
			ans = (ans * 3) % MOD


print(ans % MOD)

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
count = 1
j = 0
if s1[0] == s2[0]:
  count *= 3
else:
  count *= 6 
  j += 1
while j < n-1:
  if s1[j] == s2[j]:
    if s1[j+1] == s2[j+1]:
      count *= 2
      count %= 1000000007
    else:
      count *= 2
      count %= 1000000007
      j += 1
  else:
    if s1[j+1] == s2[j+1]:
      count *= 1
      count %= 1000000007
    else:
      count *= 3
      count %= 1000000007
      j += 1
  j += 1
print(count)

Solution (Python):
n=int(input())
s=input()
t=input()
p=i=0
if s[0]==t[0]:
    r=3
    p=1
    i+=1
else:
    r=6
    p=2
    i+=2
while i<n:
    if s[i]==t[i]:
        r=r*(3-p)%1000000007
        p=1
        i+=1
    else:
        r=r*(p+1)%1000000007
        p=2
        i+=2
print(r)

Solution (Python):
def d():
    N  = int(input())
    S1 = input()
    S2 = input()
    from collections import deque
    s = deque(S1)
    S = ''
    for _ in range(N):
        if len(s) >= 2:
            if s[0] == s[1]:
                S += 'Z'
                s.popleft()
                s.popleft()
            else:
                S += 'I'
                s.popleft()
        elif len(s) == 1:
            S += 'I'
            s.popleft()
        else:
            break
    res = 6 if S[0] == 'Z' else 3
    for i in range(len(S)-1):
        if S[i:i+2] == 'II':
            res *= 2
        if S[i:i+2] == 'IZ':
            res *= 2
        if S[i:i+2] == 'ZI':
            res *= 1
        if S[i:i+2] == 'ZZ':
            res *= 3
    print(res % 1000000007)

d()

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

t = 0
dominoes = []
while (t<n):
    if(s1[t]==s2[t]):
        dominoes.append("X")
        t+=1
    else:
        dominoes.append("Y")
        t+=2

ans = 3 if(dominoes[0]=="X") else 6
for i, d in enumerate(dominoes):
    if(i==0):
        temp = d
        continue
    if(temp=="X" and d == "X"):
        ans *= 2 % mod
    elif(temp=="X" and d == "Y"):
        ans *= 2 % mod
    elif(temp=="Y" and d == "Y"):
        ans *= 3 % mod
    temp = d

print(ans % mod)

Solution (Python):
mod = 1000000007

N = int(input())
u = input()
d = input()

c = 1
t = 0

if u[t] == d[t]:
    t += 1
    c *= 3
    lh = 'l'
else:
    t += 2
    c *= 6
    lh = 'h'

while t < N:
    if u[t] == d[t]:
        t += 1
        if lh == 'l':
            c = (c * 2) % mod
        lh = 'l'
    else:
        t += 2
        if lh == 'l':
            c = (c * 2) % mod
        else:
            c = (c * 3) % mod
        lh = 'h'
print(c)

Solution (Python):
def main():
    """
    2 * N, square
    N domino
    domino, 2 * 1 or 1 * 2

    [pattern 1]
    aabb
    ccdd
    (a, d) and (b, c) => 2 colors
    (a, d) and c and b => 3 colors
    (c, b) and a and d => 3 colors

    [pattern 2]
    aab
    ccb
    => 3 colors

    [pattern 3]
    abc
    abc
    2 or 3 colors

    このような塗り方が何通りあるかを
    mod 1000000007 で求めてください．
    """
    N = int(input())
    S1 = input()
    S2 = input()

    a = 1
    before = "f"
    
    
    
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            
            if before == "f":
                a *= 3
            elif before == "v":
                a *= 2
            else:
                pass
            before = "v"
            i += 1
        else:
            
            if before == "f":
                
                a *= 6
            elif before == "v":
                a *= 2
            else:
                a *= 3
            before = "h"
            i += 2

    print(a % 1000000007)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque


MOD = 10 ** 9 + 7

def main():
    n = int(input())
    ds = [input(), input()]

    total = 1
    i = 0

    while i < n:
        if ds[0][i] == ds[1][i]: 
            if i == 0: 
                x = 3
            else:
                if ds[0][i - 1] == ds[1][i - 1]: 
                    x = 2
                else:
                    x = 1
        else: 
            if i == 0: 
                x = 6 
            else:
                if ds[0][i - 1] == ds[1][i - 1]: 
                    x = 2
                else:
                    x = 3

            i += 1

        total = (total * x) % MOD

        i += 1

    print(total)


if __name__ == "__main__":
    main()

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

if N == 1:
    ans = 3
else:
    if S1[0] == S1[1]:
        index = 2
        ans   = 6
        vertical = False
    else:
        index = 1
        ans = 3
        vertical = True
    while True:
        if (N - index) == 1:
            if vertical:
                ans *= 2
            index += 1
        elif (N - index) == 0:
            break
        else:
            if S1[index] == S1[index+1]:
                index += 2
                if vertical:
                    ans *= 2
                else:
                    ans *= 3
                vertical = False
            else:
                index += 1
                if vertical:
                    ans *= 2
                vertical = True

print(ans % 1000000007)

Solution (Python):

N = int(input())
s1 = input()
s2 = input()

if (s1[0]==s2[0]):
    c = 3
else:
    c = 6


for i in range(N-1):
    if (s1[i]==s2[i]):
        c*=2
    else:
        if (s1[i]!=s1[i+1]):
            if (s1[i+1]!=s2[i+1]):
                c*=3
print(c%1000000007)

Solution (Python):
M = 1000000007
N = int(input())
S = [input() for i in range(2)]

ans = 1
l = 1
i = 0
while i < N:
    if S[0][i] == S[1][i]:
        if i == 0:
            ans = ans * 3 % M
        else:
            if l == 1:
                ans = ans * 2 % M
        l = 1
        i += 1
    else:
        if i == 0:
            ans = ans * 6 % M
        else:
            if l == 1:
                ans = ans * 2 % M
            else:
                ans = ans * 3 % M
        l = 2
        i += 2

print(ans)

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

ans = 1
pt = 0
beforestate = 0 
if s1[0] == s2[0]:
    ans = 3
    pt = 1
    beforestate = 0 
else :
    ans = 6
    pt = 2
    beforestate = 1 

while pt < n:
    if beforestate == 0 and s1[pt] == s2[pt]:
        ans = ans * 2 % max
        beforestate = 0
        pt += 1
    elif beforestate == 1 and s1[pt] == s2[pt]:
        beforestate = 0
        pt += 1
    elif beforestate == 0 and s1[pt] != s2[pt]:
        ans = ans * 2 % max
        beforestate = 1
        pt += 2
    elif beforestate == 1 and s1[pt] != s2[pt]:
        ans = ans * 3 % max
        beforestate = 1
        pt += 2

print(ans)

Solution (Python):
n = input()
n = int(n)
s_1 = input()
s_2 = input()
s_list = []

nagasa = len(s_1)
i = 0
while i < nagasa:
    if s_1[i] == s_2[i]:
        s_list.append(0)
        i += 1
    else:
        s_list.append(1)
        i += 2

if s_list[0]==0:
    kotae = 3
else:
    kotae = 3*2
    
mod = 1000000007
mod = 1000000007
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

for i in range(len(s_list)-1):
    if s_list[i]==0:
        kotae = mul(kotae,2)
    elif s_list[i]==1 and s_list[i+1]==0:
        pass
    else:
        kotae = mul(kotae,3)
print(kotae)

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

ans_pt = []
ans = 1
i = 0
while i < N:
    if S1[i] == S2[i]:
        ans_pt.append("H")
        i += 1
    else:
        ans_pt.append("W")
        i += 2

if ans_pt[0] == "W":
    ans = ans*6
else:
    ans = ans*3

for i in range(1, len(ans_pt)):
    if ans_pt[i-1] == "W" and ans_pt[i] == "W":
        ans = ans*3
    elif ans_pt[i-1] == "W" and ans_pt[i] == "H":
        ans = ans*1
    elif ans_pt[i-1] == "H" and ans_pt[i] == "W":
        ans = ans*2
    else:
        ans = ans*2

print(ans % 1000000007)

Solution (Python):
N = int(input())
s1 = input()
s2 = input()
index = 0
ans = 3
def multi(x,y):
    return x*y % (10**9+7)
if s1[index] != s2[index]:
    ans = 6
    index += 2
else:
    index += 1
while index < N:
    if s1[index] == s2[index]:
        if s1[index-1] == s2[index-1]:
            ans = multi(ans, 2)
        index += 1
    else:
        if s1[index-1] == s2[index-1]:
            ans = multi(ans, 2)
        else:
            ans = multi(ans, 3)
        index += 2
print(ans)

Solution (Python):
N = int(input())
S = [input() for i in range(2)]

c = 0
if S[0][0] == S[1][0]:
    n = 3
    s = 'tate'
    c += 1
else:
    n = 6
    s = 'yoko'
    c += 2

while c < N:
    if S[0][c] == S[1][c]:
        if s == 'tate':
            n *= 2
            c += 1
        else:
            s = 'tate'
            c += 1
    else:
        if s == 'tate':
            n *= 2
            s = 'yoko'
            c += 2
        else:
            n *= 3
            c += 2

print(n % 1000000007)

Solution (Python):

n = int(input())
s1 = list(map(str,list(input())))
s2 = list(map(str,list(input())))

flag = 0
a = 0

x = 1
for i in range(n):
    if a == 1:
        a = 0
    elif flag == 0 and s1[i] == s2[i]:
        x *= 3
        flag = 1
    elif flag == 0 and s1[i] != s2[i]:
        x *= 3 * 2
        a = 1
        flag = 2
    elif flag == 1 and s1[i] == s2[i]:
        x *= 2
        flag = 1
    elif flag == 1 and s1[i] != s2[i]:
        x *= 2 * 1
        a = 1
        flag = 2
    elif flag == 2 and s1[i] == s2[i]:
        x *= 1
        flag = 1
    elif flag == 2 and s1[i] != s2[i]:
        x *= 3
        a = 1
        flag = 2
print(x%1000000007)

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):
n = int(raw_input())
d1 = raw_input()
d2 = raw_input()

ans = 3
flag = 0
for i in range(n):
    if flag == -1:
        flag = 1
        continue
    if i < n-1 and d1[i] == d1[i+1]:
        if flag == 1:
            ans *= 3
        elif flag in [0, 2]:
            ans *= 2
        flag = -1
    elif d1[i] == d2[i]:
        if flag in [0, 1]:
            ans *= 1
        else:
            ans *= 2
        flag = 2
    else:
        'error'
print ans % 1000000007

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

if s1[0] == s2[0]:
    res = 3
    state = 'v'
else:
    res = 6
    state = 'h1'


for i in range(1, n):
    if s1[i] == s2[i]: 
        if state == 'v':
            res = 2 * res % 1000000007
        else:
            pass

        state = 'v'

    else: 
        if state == 'h1':
            state = 'h2'

        elif state == 'h2':
            res = 3 * res % 1000000007
            state = 'h1'

        elif state == 'v':
            res = 2 * res % 1000000007
            state = 'h1'

print(res)

Solution (Python):



n = raw_input()
n = int(n)

s1 = raw_input()
s2 = raw_input()

ans = 1

mod = 1000000007

i = 0

if s1[i] == s2[i]:
    ans = ans * 3
    i += 1
else:
    ans = ans * 6
    i += 2

while i < n:
    if s1[i-1] == s2[i-1]:
        if s1[i] == s2[i]:
            ans = ans * 2 % mod
            i += 1
        else:
            ans = ans * 2 % mod
            i += 2
    else:
        if s1[i] == s2[i]:
            i += 1
        else:
            ans = ans * 3 % mod
            i += 2

print ans

Solution (Python):
N = int(input())
S = [input(), input()]
MOD = 1000000007

i = 0
ans = 3
prev_n = 0
while i < N:
    if S[0][i] == S[1][i]:
        n = 1
        i += 1
    else:
        n = 2
        i += 2
    if prev_n == 0 and n == 2:
        ans *= 2
    elif prev_n == 1:
        ans = (ans * 2) % MOD
    elif prev_n == 2 and n == 2:
        ans = (ans * 3) % MOD
    prev_n = n
print(ans)

Solution (Python):

hou=1000000007

N=int(input())

Sone=input()
Stwo=input()

tateyoko=[]
idx=0
owari=len(Sone)
while idx < owari:
    if Sone[idx] == Stwo[idx]:
        
        tateyoko.append(1)
        idx=idx+1
    else:
        
        tateyoko.append(2)
        idx=idx+2

ans=1
mae=None
for mono in tateyoko:
    if mono==1:
        
        if mae==None:
            kake=3
        elif mae==1:
            kake=2
        else:
            kake=1
    else:
        
        if mae==None:
            kake=6
        elif mae==1:
            kake=2*1
        else:
            kake=1+2

    mae=mono
    ans=(ans*kake)%hou

print(ans)

Solution (Python):
import sys
N=int(raw_input())
S=[]
for n in xrange(2):
    S.append(raw_input().strip())

M=1000000007
if N==1:
    cnt = 3
else:
    if S[0][0]==S[1][0]:
        cnt = 3
        i=1
        ant=1
    else:
        cnt = 6
        i = 2
        ant = 0
    while i<N:
        if S[0][i]==S[1][i]:
            if ant==1:
                cnt = (cnt +cnt)%M
            else:
                ant=1
            i += 1
        else:
            if ant==0:
                cnt = (cnt *3)%M
            else:
                cnt = (cnt + cnt)%M
                ant = 0
            i += 2
print cnt

Solution (Python):
n=int(raw_input())
a=raw_input()
b=raw_input()
res = 1
i=0
s=0
M=1000000007
if a[i]==b[i] :
    res = 3
    i+=1
    s=1
else :
    res = 6
    i+=2
    s=2
while i<n :
    if a[i]==b[i] :
        if s==1 :
            res *= 2
            res %= M
        i+=1
        s=1
    else :
        if s==1 :
            res *= 2
            res %= M
        else :
            res *= 3
            res %= M
        i+=2
        s=2
print res

Solution (Python):
import sys


def inp(t): return t(sys.stdin.readline().strip())


def inpm(t): return map(t, sys.stdin.readline().split())


def inpl(t): return list(map(t, sys.stdin.readline().split()))


n = inp(int)
a = [inp(str), inp(str)]
dp = [0] * n

if a[0][0] == a[1][0]:
    dp[0] = 3
    i = 1
else:
    dp[1] = 6
    i = 2

while i < n:
    if a[0][i - 1] == a[1][i - 1]:
        if a[0][i] == a[1][i]:
            dp[i] = dp[i - 1] * 2
            i += 1
        else:
            dp[i + 1] = dp[i - 1] * 2
            i += 2
    else:
        if a[0][i] == a[1][i]:
            dp[i] = dp[i - 1]
            i += 1
        else:
            dp[i + 1] = dp[i - 1] * 3
            i += 2

print(dp[n - 1] % 1000000007)

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

MOD = 1000000007

if S1[0] == S2[0]:
    ans = 3
    idx = 1
    yoko = False
else:
    ans = 6
    idx = 2
    yoko = True
    
while idx < N:
    if S1[idx] == S2[idx]:
        if yoko:
            ans *= 1 
        else:
            ans *= 2
        idx += 1
        yoko = False
    else:
        if yoko:
            ans *= 3
        else:
            ans *= 2
        idx += 2
        yoko = True
    
    ans %= MOD
    
print(ans%MOD)

Solution (Python):

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

MOD = 1000000007
i = 1
ans = 3
tp = 0
if S1[0] != S2[0]:
    i = 2
    ans = 6
    tp = 1
while i < N:
    if S1[i] == S2[i]:
        ans = (ans * [2, 1][tp]) % MOD
        i += 1
        tp = 0
    else:
        ans = (ans * [2, 3][tp]) % MOD
        i += 2
        tp = 1

print(ans)