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
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(10000)



def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))



def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]




dp = None


def main():
    N = int(input())
    S = [input() for _ in range(2)]
    is_cols = []

    i = 0
    while i < N:
        if S[0][i] == S[1][i]:
            is_cols.append(True)
            i += 1
        else:
            is_cols.append(False)
            i += 2

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

    i = 1
    while i < len(is_cols):
        if is_cols[i] and is_cols[i - 1]:
            ans *= 2
        elif not is_cols[i] and not is_cols[i - 1]:
            ans *= 3
        elif not is_cols[i] and is_cols[i - 1]:
            ans *= 2

        i += 1

    print(ans % 1000000007)


main()

Solution (Python):
N = int( input())
SU = list( input())
SD = list( input())
Q = 10**9 + 7
i = 0
yokocnt = 0
tatecnt = 0
ans = 3
while i <= N-1:
    if SU[i] == SD[i]:
        yokocnt = 0
        i += 1
        tatecnt += 1
        if tatecnt >= 2:
            ans = (ans*2)%Q
    else:
        tatecnt = 0
        i += 2
        yokocnt += 1
        if yokocnt >= 2:
            ans = (ans*3)%Q
        else:
            ans = (ans*2)%Q
print(ans)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

N = int(input())
S1 = input()
S2 = input()
li = []

i = 0
while i < N:
	if i == N-1 or S1[i] != S1[i+1]:
		li.append(1)
		i += 1
	else:
		li.append(2)
		i += 2

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

L = len(li)

for i in range(1,L):
	bef = li[i-1]
	now = li[i]
	if bef == 2 and now == 2:
		ans *= 3
	elif bef == 2 and now == 1:
		ans *= 1
	elif bef == 1 and now == 2:
		ans *= 2
	elif bef == 1 and now == 1:
		ans *= 2
	ans %= mod

print(ans)

Solution (Python):
n = int(input())
S1 = input()
S2 = input()
m = 1000000007

if S1[0] == S2[0]:
    p = 3
    v = True
    i = 1
else:
    p = 6
    v = False
    i = 2
while(i < n):
    if S1[i] == S2[i]:
        p = (p*2 if v else p) % m
        v = True
        i += 1
    else:
        p = (p*2 if v else p*3) % m
        v = False
        i += 2
print(p)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
patterns = []
flag = False
for i in range(N):
    if S1[i] == S2[i]:
        patterns.append('row')
    elif flag is False:
        patterns.append('column')
        flag = True
    else:
        flag = False

if patterns[0] == 'row':
    count = 3
else:
    count = 6
for i in range(1, len(patterns)):
    prev = patterns[i-1]
    current = patterns[i]
    if prev == 'row':
        if current == 'row':
            count *= 2
        else:
            count *= 2
    else: 
        if current == 'row':
            count *= 1
        else:
            count *= 3
print(count % (10**9  + 7))

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

mod = 10 ** 9 + 7

ans = 0
ptn = 0
i = 0
if S1[i] == S2[i]:
    ans = 3
    ptn = 0
    i += 1
else:
    ans = 6
    ptn = 1
    i += 2

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

Solution (Python):
n = int(input())
s_1 = list(input())
s_2 = list(input())
m = 1000000007




combi, hist = 0, ''
for i in range(n):
    try:
        if s_1[i] == s_2[i]: 
            if hist == '':
                combi = 3
            elif hist == 'h':
                combi *= 2
            else:
                combi *= 1
            hist = 'h'
        else: 
            if hist == '':
                combi = 6
            elif hist == 'h':
                combi *= 2
            else:
                combi *= 3
            hist = 'w'
            s_1.pop(i)
            s_2.pop(i)
    except:
        break
print(combi%m)
exit(0)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S1, S2):
    ans = 0
    MOD = 1000000007

    if S1[0] == S2[0]:
        ans = 3
        i = 1
        p = 0
    else:
        ans = 6
        i = 2
        p = 1

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

    return ans


def main():
    N = read_int()
    S1 = read_str()
    S2 = read_str()

    print(slv(N, S1, S2))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
upper = list(input())
lower = list(input())
ans = 0

def count(upper, lower, state):
    global ans
    if upper[0] == lower[0]:
        if state == 1:
            ans *= 2
            try:
                count(upper[1:],lower[1:],state=1)
            except:
                return ans
        if state == 2:
            try:
                count(upper[1:], lower[1:], state=1)
            except:
                return ans
    else:
        if state == 1:
            ans *= 2
            try:
                count(upper[2:], lower[2:], state=2)
            except:
                return ans
        if state == 2:
            ans *= 3
            try:
                count(upper[2:], lower[2:], state=2)
            except:
                return ans

if upper[0] == lower[0]:
    ans = 3
    try:
        count(upper[1:], lower[1:], state=1)
    except:
        pass
else:
    ans = 6
    try:
        count(upper[2:], lower[2:], state=2)
    except:
        pass

print(ans%1000000007)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
res = 6
idx = 0
s = []
mod = 1000000007
while idx < N:
    if S1[idx] == S2[idx]:
        s.append(0)
    else:
        s.append(1)
        idx += 1
    idx += 1

res = 3 if s[0] == 0 else 6

for idx in range(1, len(s)):
    prev, cur = s[idx-1], s[idx]
    if prev == 0:
        if cur == 0:
            res *= 2
        else:
            res *= 2
    else:
        if cur == 0:
            res *= 1
        else:
            res *= 3

res %= mod

print(res)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
res = 6
idx = 0
s = []
mod = 1000000007
while idx < N:
    if S1[idx] == S2[idx]:
        s.append(0)
    else:
        s.append(1)
        idx += 1
    idx += 1

res = 3 if s[0] == 0 else 6

for idx in range(1, len(s)):
    prev, cur = s[idx-1], s[idx]
    if prev == 0:
        if cur == 0:
            res *= 2
        else:
            res *= 2
    else:
        if cur == 0:
            res *= 1
        else:
            res *= 3

    res %= mod

print(res)

Solution (Python):
n = int(input())
u = list(input())
v = list(input())

mod = 10**9+7

l = []

pointer = 0
while pointer < n:
    if u[pointer] == v[pointer]:
        pointer += 1
        l.append(0)
    else:
        pointer += 2
        l.append(1)


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

print(a)

Solution (Python):

"""
Created on Tue Jul  3 10:58:30 2018

@author: ashida
"""
N=int(input())

S1=list(input())
S2=list(input())

if len(S1)>1:
    if S1[0]==S1[1]:
        st=2
        ans=6
        flag=1
    else:
        st=1
        ans=3
        flag=-1
else:
    st=1
    ans=3
    flag=-1

while st<N:
    if st+1<N:
        if S1[st]==S1[st+1]:
            if flag<0:
                ans*=2
            else:
                ans*=3
            st+=2
            flag=1
        else:
            if flag<0:
                ans*=2
            else:
                ans*=1
            st+=1
            flag=-1
    else:
        if flag<0:
            ans*=2
        else:
            ans*=1
        st+=1
        
ans=ans%1000000007
print(ans)

Solution (Python):
n=int(input())
s1=input()
s2=input()
comb=0
tateyoko=''
i=0
while i<n:
  if i==0:
    if s1[0]==s2[0]:
      comb+=3
      tateyoko='tate'
      i+=1
    else:
      comb+=6
      tateyoko='yoko'
      i+=2
  elif s1[i]==s2[i]:
    i+=1
    if tateyoko=='tate':
      comb*=2
      comb%=1000000007
    else:
      tateyoko='tate'
  else:
    i+=2
    if tateyoko=='tate':
      tateyoko='yoko'
      comb*=2
      comb%=1000000007
    else:
      comb*=3
      comb%=1000000007
print(comb)

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

ds = []

i = 0
while i < N:
    if S1[i] == S2[i]:
        ds.append('X')
        i += 1
    else:
        ds.append('Y')
        i += 2

n = 0
if ds[0] == 'X':
    n = 3
else:
    n = 6
for i in range(1, len(ds)):
    if ds[i] == 'X':
        if ds[i - 1] == 'X':
            n *= 2 % 1000000007
        else:
            n *= 1 % 1000000007
    else:
        if ds[i - 1] == 'X':
            n *= 2 % 1000000007
        else:
            n *= 3 % 1000000007
print(n % 1000000007)

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

P = 1000000007
prev = None
i = 0
ans = 1
while i < N:
    split = S1[i] != S2[i]
    if prev is None:
        ans = 6 if split else 3
    elif prev:
        if split:
            ans = ans*3%P 
    else:
        ans = ans*2%P
    prev = split
    i += 2 if split else 1
print(ans)

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

M = 1000000007

c = 0
i = 0
result = 1

while i < N:
    if S1[i] == S2[i]:
        if c == 0:
            result = (result * 3) % M
        elif c == 1:
            result = (result * 2) % M
        elif c == 2:
            result = (result * 1) % M
        c = 1
        i += 1
    else:
        if c == 0:
            result = (result * 3 * 2) % M
        elif c == 1:
            result = (result * 2) % M
        elif c == 2:
            result = (result * 3) % M
        c = 2
        i += 2

print(result)

Solution (Python):
def mul_mod(x, y):
    return x * y % 1000000007


N = int(input())
S1 = input()
S2 = input()
L = []
i = 0
while i < N-1:
    if S1[i] == S1[i+1]:
        L.append(2)
        i += 2
    else:
        L.append(1)
        i += 1
if i == N-1:
    L.append(1)
ans = 1
if L[0] == 1:
    ans = 3
else:
    ans = 6
for i in range(1, len(L)):
    if L[i] == 1:
        if L[i-1] == 1:
            ans = mul_mod(ans, 2)
    else:
        if L[i-1] == 1:
            ans = mul_mod(ans, 2)
        else:
            ans = mul_mod(ans, 3)
print(ans)

Solution (Python):
n = int(input())
a = list(input())
b = list(input())
ans = 1
mod = 10**9 + 7
i = 0
while i <= n-1:
  
  if i == 0:
    if a[i] == b[i]:
      ans *= 3
      i += 1
    elif not a[i] == b[i]:
      ans *= 6
      i += 3
  else:
    if a[i-1] == b[i-1]:
      if a[i] == b[i]:
        ans *= 2
        i += 1
      else:
        ans *= 2
        i += 2
    elif not a[i-1] == b[i-1]:
      if not a[i] == b[i]:
        ans *= 3
        i += 2
      else:
        i += 1

print(ans % mod)

Solution (Python):
n = int(input())
S = list(input())
input()
MOD = 10**9+7

x = []
p = S[0]
c = 1
for s in S[1:]:
    if s == p:
        c += 1
    else:
        x.append(c)
        c = 1
    p = s
x.append(c)

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

Solution (Python):
MOD = 1000000007

def m():
    N = int(input())
    if N == 1:
        return 3
    s = str(input())
    s2 = str(input())
    a = []
    past = s[0]
    point = 0
    while point < len(s):
        if s[point] == s[point+1]:
            a.append('y')
            point += 2
        else:
            a.append('x')
            point += 1

        if point == len(s) -1:
            a.append('x')
            break

    ans = 0
    if a[0] == 'x':
        ans = 3
    else:
        ans = 6

    for j in range(1, len(a)):
        if a[j-1] == 'x' and a[j] == 'x':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'x':
            ans *=1 % MOD
        elif a[j-1] == 'x' and a[j] == 'y':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'y':
            ans *=3 % MOD

    return ans % MOD
print(m())

Solution (Python):
MOD = 1000000007

def m():
    N = int(input())
    if N == 1:
        return 3
    s = str(input())
    s2 = str(input())
    a = []
    past = s[0]
    point = 0
    while point<len(s):
        if point == N-1:
            a.append('x')
            point+=1
        elif s[point] == s[point+1]:
            a.append('y')
            point+=2
        else:
            a.append('x')
            point+=1

    ans = 0
    if a[0] == 'x':
        ans = 3
    else:
        ans = 6

    for j in range(1, len(a)):
        if a[j-1] == 'x' and a[j] == 'x':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'x':
            ans *=1 % MOD
        elif a[j-1] == 'x' and a[j] == 'y':
            ans *=2 % MOD
        elif a[j-1] == 'y' and a[j] == 'y':
            ans *=3 % MOD

    return ans % MOD

print(m())

Solution (Python):
def someone_ans():
    n=int(input())
    a=input()
    b=input()
    c=[]
    i=0
    while i<n:
        if i == n-1:
            c.append(1)
            i+=1
        elif a[i] == a[i+1]:
            c.append(0)
            i +=2
        else:
            c.append(1)
            i+=1

    if c[0] ==0: count=6
    else: count=3
    for i in range(len(c)-1):
        if c[i]==1:count*=2
        elif c[i]==0 and c[i+1]==0: count*=3
    return count % 1000000007


print(someone_ans())

Solution (Python):
P=10**9+7
N=int(input())
S1=input()
S2=input()
L=[1]
k=0
P=10**9+7
for i in range(1,N):
    if S1[i]!=S1[i-1]:
        L.append(0)
        k+=1
    L[k]+=1
M=len(L)
S=1
if L[0]==1:
    S=3
else:
    S=6
for i in range(1,M):
    if L[i-1]==1:
        S=(S*2)%P
    else:
        if L[i]==2:
            S=(S*3)%P
print(S)

Solution (Python):
def read():
    return int(input())


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


def readmap():
    return map(int, input().split())


MOD = 1000000007
N = read()
S1 = input()
S2 = input()

if S1[0] == S2[0]:
    ans = 3
    same = True
    n = 1
else:
    ans = 6
    same = False
    n = 2

while n < N:
    if S1[n] == S2[n]:
        n += 1
        if same:
            ans = (ans * 2) % MOD
        else:
            same = True
    else:
        n += 2
        if same:
            ans = (ans * 2) % MOD
            same = False
        else:
            ans = (ans * 3) % MOD

print(ans)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
dominos = []
yokoflag = 0
for u, l in zip(S1, S2):
    if u == l:
        dominos.append(1)
    else:
        if yokoflag == 0:
            yokoflag = 1
            continue
        else:
            dominos.append(2)
            yokoflag = 0
combi = 1
if dominos[0] == 1:
    combi = 3
else: combi = 6
for i in range(1, len(dominos)):
    if dominos[i-1] == 1 and dominos[i] == 1:
        combi *= 2
    elif dominos[i-1] == 1 and dominos[i] == 2:
        combi *= 2
    elif dominos[i-1] == 2 and dominos[i] == 1:
        combi *= 1
    elif dominos[i-1] == 2 and dominos[i] == 2:
        combi *= 3
    combi = combi % 1000000007
print(combi)

Solution (Python):
n = int(input())
S = input()
a = []
while(S != ""):
  if len(S) != 1 and S[0] == S[1]:
    a.append(2)
    S = S[2:]
  else:
    a.append(1)
    S = S[1:]
if a[0] == 1:
  ans = 3
else:
  ans = 6
for i in range(0,len(a)-1):
  if a[i] == 1:
    ans *= 2
    ans %= 1000000007
  else:
    if a[i+1] == 2:
      ans *= 3
      ans %= 1000000007
print(ans)

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
i = 0
T = []
while i < N:
    if S1[i]==S2[i]:
        T.append("C")
    else:
        T.append("R")
        i += 1
    i += 1
Ans = 3 if T[0]=="C" else 6
for i in range(1,len(T)):
    if T[i-1] == "C":
        if T[i] == "C":
            Ans *= 2
        else:
            Ans *= 2
    else:
        if T[i] == "C":
            Ans *= 1
        else:
            Ans *= 3
    Ans %= 10**9+7
print(Ans)

Solution (Python):
n=int(input())
a=input()
b=input()
c=[]
i=0
while i<n:
    if i==n-1:
        c.append(1)
        i+=1
    elif a[i]==a[i+1]:
        c.append(0)
        i+=2
    else:
        c.append(1)
        i+=1
if c[0]==0: count=6
else: count=3
    
for i in range(len(c)-1):
    if c[i]==1: count*=2
    elif c[i]==0 and c[i+1]==0: count*=3
print(count%1000000007)

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

cnt=0
stat=0
ans=1
if S1[cnt]==S2[cnt]:
  cnt+=1
  ans*=3
else:
  cnt+=2
  stat=1
  ans*=6

while cnt!=N:
  if stat:
    if S1[cnt]==S2[cnt]:
      stat=0
      cnt+=1
    else:
      ans*=3
      ans%=mod
      cnt+=2
  else:
    if S1[cnt]==S2[cnt]:
      cnt+=1
      ans*=2
      ans%=mod
    else:
      cnt+=2
      ans*=2
      ans%=mod
      stat=1
print(ans)

Solution (Python):
n = int(input())
x = input()
y = input()
if x[0]==y[0]: num,flag,place = 3,True,1
else: num,flag,place = 6,False,2
while place!=n:
	if flag:
		num = (num*2)%(10**9+7)
		if x[place]!=y[place]:
			flag = False
			place += 2
		else: place+=1
	else:
		if x[place]==y[place]:
			flag = True
			place += 1
		else:
			num = (num*3)%(10**9+7)
			place += 2
print(num)

Solution (Python):
N = int(input())
S_1 = input()
S_2 = input()
ans = 1
i = 0
while True:
    if i >= N:
        break
    if i == 0:
        if S_1[i] == S_2[i]:
            ans *= 3
            i += 1
        else:
            ans *= 6
            i += 2
    else:
        if S_1[i-1] == S_2[i-1] and S_1[i] == S_2[i]:
            ans *= 2
            i += 1
        elif S_1[i-1] != S_2[i-1] and S_1[i] == S_2[i]:
            ans *= 1
            i += 1
        elif S_1[i-1] == S_2[i-1] and S_1[i] != S_2[i]:
            ans *= 2
            i += 2
        elif S_1[i-1] != S_2[i-1] and S_1[i] != S_2[i]:
            ans *= 3
            i += 2
    ans = ans % 1000000007
print(ans)

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

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

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

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

l=[]
flag=-1
for i in range(N):
	if S1[i]==S2[i]:
		l.append("X")
		flag=0
	else:
		if i==0:
			l.append("Y")
		elif S1[i-1]!=S1[i]:
			l.append("Y")
		else:
			pass

ans=-1
for ind,i in enumerate(l):
	if ind==0:
		if i=="X":
			ans=3
		else:
			ans=6
	else:
		if i=="Y" and l[ind-1]=="X":
			ans*=2
		elif i=="Y" and l[ind-1]=="Y":
			ans*=3
		elif i=="X" and l[ind-1]=="Y":
			ans*=1
		elif i=="X" and l[ind-1]=="X":
			ans*=2

print ans%1000000007

Solution (Python):

n = int(input())
s = input()
t = input()


def head(u):
    if u[0] == u[1]:
        return 3
    else:
        return 6

def conn(u, v):
    if u[0] == u[1]:
        """
        AX
        AX

        or

        AX
        AY
        """
        return 2
    else:
        if v[0] == v[1]:
            """
            AX
            BX
            """
            return 1
        else:
            if u[0] == v[0] and u[1] == v[1]:
                """
                AA
                BB
                """
                return 1
            else:
                """
                AY
                BX
                """
                return 3

m = 1
u = None
for v in zip(s, t):
    if u is None:
        m = head(v) 
    else:
        m = (m * conn(u, v)) % 1000000007
    u = v
print(m)

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

MOD = int(1e9) + 7

tate = "tate"
yoko = "yoko"

i = 0
ans = 0
pre = ""
if s1[i] == s2[i]:
    ans = 3
    i += 1
    pre = tate
else:
    ans = 6
    i += 2
    pre = yoko

while i < N:
    if s1[i] == s2[i]:
        if pre == tate:
            ans *= 2
        elif pre == yoko:
            ans *= 1
        i += 1
        pre = tate
    else:
        if pre == tate:
            ans *= 2
        elif pre == yoko:
            ans *= 3
        i += 2
        pre = yoko
    ans %= MOD
print(ans)

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

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

if S1[0] == S1[1]:
	i = 2
	ans = 6
	prev_flag = 2
else:
	i = 1
	ans = 3
	prev_flag = 1

while i < (N-1):
	if S1[i] == S1[i+1]:
		i += 1
		if prev_flag == 2:
			ans *= 3
		else:
			ans *= 2

		prev_flag = 2

	else:
		if prev_flag == 1:
			ans *= 2

		prev_flag = 1

	i += 1

if i == (N-1) and prev_flag == 1:
	ans *= 2

print(ans%mod)

Solution (Python):
N = int(input())
s1 = input()
s2 = input()
MOD = 1000000007

dp = [0] * (N + 1)
if s1[0] == s2[0]:
    dp[0] = 3
    i = 1
else:
    dp[0] = 6
    i = 2
p1, p2 = s1[0], s2[0]
j = 0
while i < N:
    c1, c2 = s1[i], s2[i]
    if c1 == c2:
        if p1 == p2:
            dp[j+1] = dp[j] * 2 % MOD
        else:
            dp[j+1] = dp[j]
        i += 1
    elif c1 != c2:
        if p1 == p2:
            dp[j+1] = dp[j] * 2 % MOD
        else:
            dp[j+1] = dp[j] * 3 % MOD
        i += 2
    j += 1
    p1, p2 = c1, c2

print(dp[j])

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

i = 0
ans = 1
MOD = int(1e9) + 7
before = True  
while i < N:
    
    if S1[i] == S2[i]:
        if i == 0:
            ans = 3
        else:
            if before:
                ans *= 2
                ans %= MOD
            else:
                ans *= 1
        before = True
        i += 1
    
    else:
        if i == 0:
            ans = 6
        else:
            if before:
                ans *= 2
            else:
                ans *= 3
                ans %= MOD
        before = False
        i += 2
print(ans)

Solution (Python):
YOKO = 0
TATE = 1

MOD = 1000000007

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

if s1[0] == s2[0]:
    state = TATE
    n_pattern = 3
    i = 1
else:
    state = YOKO
    n_pattern = 6
    i = 2

while i < n:
    current = int(s1[i] == s2[i])
    if state == TATE:
        n_pattern *= 2
        if n_pattern >= MOD:
            n_pattern = n_pattern % MOD
    else:
        if current == YOKO:
            n_pattern *= 3
            if n_pattern >= MOD:
                n_pattern = n_pattern % MOD

    state = current
    if state == TATE:
        i += 1
    else:
        i += 2
print(n_pattern % MOD)

Solution (Python):
N = int(input())
S_1 = list(input())
S_2 = list(input())



if S_1[0] == S_2[0]:
    res = 3
    flag = 0
    i = 1
else:
    res = 6
    flag = 1
    i = 2

while i != N:
    if S_1[i] == S_2[i]:
        if flag == 0:
            res *= 2 
        else:
            res *= 1
            flag = 0
        i += 1

    else:
        if flag == 0:
            res *= 2
            flag = 1
        else:
            res *= 3
        i += 2
        
ans = res%1000000007

print(ans)

Solution (Python):
from collections import defaultdict
from itertools import product, groupby
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10
MOD = 1000000007


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

    pre_is_v = S1[0] == S2[0]
    ans = 3 if pre_is_v else 6
    i = 1 if pre_is_v else 2
    while i < N:
        is_v = S1[i] == S2[i]
        if pre_is_v and not is_v:
            ans = (ans * 2) % MOD
        elif pre_is_v and is_v:
            ans = (ans * 2) % MOD
        elif not pre_is_v and not is_v:
            ans = (ans * 3) % MOD

        pre_is_v = is_v
        i += 1 if is_v else 2

    print(ans % MOD)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S1 = input()
S2 = input()
 
result = 3
if N != 1:
    i=1
    while i < N:
        if i==1:
            result *= 2
        elif S1[i-1]==S2[i-1]:
            result *=2
        elif S1[i-1]!=S1[i]:
            if S1[i] != S2[i]:
                result *= 3
        i += 1
 
print(result%1000000007)

Solution (Python):

"""
"""



def solve(line1, line2):
    seq = []
    if len(line1) == 0:
        return 0
    elif len(line1) == 1:
        return 3
    else:
        prev_mark = line1[0]
        for m in line1[1:]:
            if prev_mark is None:
                prev_mark = m
                continue
            if m == prev_mark:
                seq.append('h')
                prev_mark = None
            else:
                seq.append('v')
                prev_mark = m
        if prev_mark:
            seq.append('v')

    if len(seq) == 1:
        return 6
    if seq[0] == 'h':
        ans = 6
        prev_p = 'h'
    else:
        ans = 3
        prev_p = 'v'

    for d in seq[1:]:
        if prev_p == 'h' and d == 'h':
            ans *= 3
            prev_p = 'h'
        elif prev_p == 'h' and d == 'v':
            prev_p = 'v'
        elif prev_p == 'v' and d == 'h':
            ans *= 2
            prev_p = 'h'
        else:
            ans *= 2
            prev_p = 'v'
    return ans % 1000000007




def main():
    n = int(input())
    line1 = input()
    line2 = input()
    result = solve(line1, line2)
    print(result)




if __name__ == '__main__':
    main()

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

ans = 3
left = None
j = 0
while j < N:
    if S1[j] == S2[j]:
        if left == 'V':
            ans *= 2

        left = 'V'
        j += 1
    else:
        if left == 'H':
            ans *= 3
        else:
            ans *= 2
        left = 'H'
        j += 2

print(ans % 1000000007)

Solution (Python):
import sys
N = int(raw_input())
row1 = raw_input()
row2 = raw_input()

power2 = 0
power3 = 0

if row1[0] == row2[0]:
    power3 += 1
    i = 1
    previous_tate = True
else:
    power2 += 1
    power3 += 1
    i = 2
    previous_tate = False

while i < N:
    if row1[i] == row2[i]:
        
        i += 1
        if previous_tate:
            power2 += 1
        previous_tate = True
    else:
        i += 2
        if not previous_tate:
            power3 += 1
        else:
            power2 += 1
        previous_tate = False
print (pow(2, power2) * pow(3, power3)) % 1000000007

Solution (Python):
n = int(input())
s1 = input()
s2 = input()
mod = 10 ** 9 + 7
table = []
y = 0
for i in range(len(s1)):
    if s1[i] == s2[i]:
        table.append("x")
    else:
        if y == 0:
            table.append("y")
            y += 1
        else:
            y -= 1
if table[0] == "x":
    ans = 3
else:
    ans = 6

for i in range(len(table))[1:]:
    if table[i] == "x":
        if table[i - 1] == "x":
            ans *= 2 % mod
        else:
            pass
    else:
        if table[i - 1] == "x":
            ans *= 2 % mod
        else:
            ans *= 3 % mod
print(ans % mod)

Solution (Python):






n=int(input())
s1 = list(input())
s2 = list(input())
s1p="!"
s2p="!"
arr=[]
for i in range(n):
    if s1[i]==s2[i]:
        arr.append(1)
    elif s1[i]==s1p:
        arr.append(2)
    s1p=s1[i]
    s2p=s2[i]

prv=0
ans=1
for a in arr:
    if prv==0 and a==1:
        ans*=3
        ans%=1000000007
    elif prv==0 and a==2:
        ans*=6
        ans%=1000000007
    elif prv==1:
        ans*=2
        ans%=1000000007
    elif prv==2 and a==2:
        ans*=3
        ans%=1000000007
    prv=a
print(ans)

Solution (Python):
def calc_vh(S):
  res = []
  N = len(S)
  pos = 0
  while pos < N:
    if(pos == N-1 or S[pos+1] != S[pos]):
      res.append("v")
      pos += 1
    else:
      res.append("h")
      pos += 2
  return res

N = int(input())
S = input()
S2 = input()

vh = calc_vh(S)
if vh[0]=="v":
  res = 3
else:
  res = 6
length = len(vh)
multiple = {("v", "v"): 2, ("v", "h"): 2, ("h", "v"): 1, ("h", "h"): 3}

for pos in range(1, length):
  v = vh[pos-1], vh[pos]
  res *= multiple[v]

print(res %  1000000007 )

Solution (Python):
N = int(input())
S = str(input())
_ = input()

l = []
i = 0

while(i < N):
    if i == N-1:
        l.append(1)
        i += 1
        continue

    if S[i] == S[i + 1]:
        l.append(2)
        i += 2
    else:
        l.append(1)
        i += 1

acc = 1
for j in range(len(l)):
    if j == 0:
        if (l[j] == 1):
            acc *= 3
            continue
        else:
            acc *= 6
            continue

    if l[j-1] == 1:
        acc *= 2
    else:
        if (l[j] == 1):
            acc *= 1
        else:
            acc *= 3

print(acc % 1000000007)