Harryxun/stf_run huggingface dataset:
import math


def divisor(num):
    if num < 0:
        return 0
    elif num == 1:
        return 1
    else:
        divisor_list =[1,]
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i== 0:
                divisor_list.append(i)
        return divisor_list


N,M = map(int,input().split(' '))
P = M // N
divisor_list = divisor(M)
for i in reversed(range(len(divisor_list))):
    num = M // divisor_list[i]
    divisor_list.append(num)

for i in reversed(range(len(divisor_list))):
    if divisor_list[i] <= P:
        print(divisor_list[i])
        break

### FIXED CODE ###

import math


def divisor(num):
    if num < 0:
        return [0,]
    elif num == 1:
        return [1,]
    else:
        divisor_list =[1,]
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i== 0:
                divisor_list.append(i)
        return divisor_list


N,M = map(int,input().split(' '))
P = M // N
divisor_list = divisor(M)

for i in reversed(range(len(divisor_list))):
    num = M // divisor_list[i]
    divisor_list.append(num)

for i in reversed(range(len(divisor_list))):
    if divisor_list[i] <= P:
        print(divisor_list[i])
        break
import math


def is_prime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    i = 3
    while i <= math.sqrt(x):
        if x % i == 0:
            return False
        i = i + 2

    return True


n = int(input())
numbers = [int(input()) for i in n]


count = 0
for i in range(n):
    if is_prime(numbers[i]) is True:
        count += 1

print(count)



### FIXED CODE ###

import math


def is_prime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    i = 3
    while i <= math.sqrt(x):
        if x % i == 0:
            return False
        i = i + 2

    return True


n = int(input())
numbers = [int(input()) for i in range(n)]


count = 0
for i in range(n):
    if is_prime(numbers[i]) is True:
        count += 1

print(count)
N, A, B = int(raw_input().split(' '))

print(min(int(A) * int(N), int(B)))


### FIXED CODE ###

N, A, B = raw_input().split(' ')
 
print(min(int(A) * int(N), int(B)))
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(m):
        x, y = dat[j:j+2]
        xt[j] = la[y]
        xt[j+1] = la[x]
        la[y] = j
        la[x] = j + 1
        j += 2
    done = [None] * (n + 1)
    x = 1
    po = []
    while 1:
        po.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    pa = []
    while 1:
        pa.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    po = po[::-1] + pa[1:]
    print len(po)
    print ' '.join(map(str, po))
main()
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(m):
        x, y = dat[j:j+2]
        xt[j] = la[y]
        xt[j+1] = la[x]
        la[y] = j
        la[x] = j + 1
        j += 2
    done = [None] * (n + 1)
    x = 1
    po = []
    while 1:
        po.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    pa = []
    while 1:
        pa.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    po = po[::-1] + pa[1:]
    print len(po)
    print ' '.join(map(str, po))
main()


### FIXED CODE ###

from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(m):
        x, y = dat[j:j+2]
        xt[j] = la[y]
        xt[j+1] = la[x]
        la[y] = j
        la[x] = j + 1
        j += 2
    done = [None] * (n + 1)
    x = 1
    po = []
    while 1:
        po.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    x = 1
    pa = []
    while 1:
        pa.append(x)
        done[x] = 1
        y = la[x]
        while y is not None:
            z = dat[y]
            if done[z] is None:
                x = z
                break
            y = xt[y]
        else:
            break
    po = po[::-1] + pa[1:]
    print len(po)
    print ' '.join(map(str, po))
main()
import  math
lis = []

N,M = [int(i) for i in input().split()]

for i in range(1,int(math.sqrt(M))):
    if M % i == 0:
        lis.append(i)
        lis.append(M//i)


lis.sort()
for i in lis:
    if i >= N:
        break

print(M//i )


### FIXED CODE ###

import  math
lis = []

N,M = [int(i) for i in input().split()]

for i in range(1,int(math.sqrt(M))):
    if M % i == 0:
        lis.append(i)
        lis.append(M//i)


lis.sort()
i =1
for i in lis:
    if i >= N:
        break

print(M//i )
from math import ceil
a,b =map(int,input(),split())
ss = (ceil(a/2)*ceil(b/2))+(a//2*b//2)
if a>1 and b>1:
	print(ss-hf)
else:
  print(1)


### FIXED CODE ###

a,b =map(int,input().split())
ss = a*b
hf =ss//2
if a>1 and b>1:
	print(ss-hf)
else:
  print(1)
from collections import Counter

n=int(input())
a=list(map(int,input().split()))

c=Counter(a)
l=c.most_common()
rectangle=[]
square=[]
x=len(l)
for i in range(x):
    if l[i][1]>=2:
        rectangle.append(l[i][0])
    if l[i][1]>=4:
        square.append(l[i][0])
rectangle.sort()
square.sort()
ans1=rectangle[-1]*rectangle[-2]
ans2=square[-1]**2
if ans1<ans2:
    print(ans2)
else:
    print(ans1)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))

c=Counter(a)
l=c.most_common()
rectangle=[]
square=[]
x=len(l)
for i in range(x):
    if l[i][1]>=2:
        rectangle.append(l[i][0])
    if l[i][1]>=4:
        square.append(l[i][0])
rectangle.sort()
square.sort()
if len(rectangle)<2 and len(square)<1:
    print(0)
elif len(rectangle)>=2 and len(square)<1:
    print(rectangle[-1]*rectangle[-2])
elif len(rectangle)<2 and len(square)>=1:
    print(square[-1]**2)
else:
    ans1=rectangle[-1]*rectangle[-2]
    ans2=square[-1]**2
    if ans1<ans2:
        print(ans2)
    else:
        print(ans1)
import numpy as np

h,w = map(int,input().split())

s = [ list(input()) for i in range(h)]
s = np.array(s)

dy = [-1,0,1,0]
dx = [0,-1,0,1]

ans =True

for i in range(0,h):
    for j in range(0,w):
        flag = False
        if s[i][j] == '#' :
            for k in range(4):
                y = i+dy[k]
                x = i+dx[k]
                if  x < 0 or x >=w or y >= h or y < 0 :continue
#                print(x,y)
                if s[x][y] == '#':
                    flag = True

        if flag :ans = False


if ans :print("No")
else:print("Yes")




### FIXED CODE ###

h, w = list(map(int, input().split()))
s = ['.'*(w+2)]

for i in range(h):
	s.append('.'+input()+'.')
s.append('.'*(w+2))

ans = True

for i in range(1, h+1):
	for j in range(1, w+1):
		if s[i][j]=='#':
			if s[i-1][j]=='.' and s[i+1][j]=='.' and s[i][j-1]=='.' and s[i][j+1]=='.':
				ans = False

print('Yes' if ans else 'No')
a,b,c,k=map(int,input().split()),int(input())
print((a+b+c-max(a,b,c))+max(a,b,c)*2**k)

### FIXED CODE ###

a,b,c=map(int,input().split())
k=int(input())
print((a+b+c-max(a,b,c))+max(a,b,c)*2**k)
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s[:-1]:
        eng_dict[i] += 1
    ans = 1
    for i in eng_dict.values():
        ans = (ans*i)%(10**9+7)
    print(ans-1)


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        try:
            eng_dict[i] += 1
        except KeyError:
            eng_dict[i] = 2
    ans = 1
    size = 10**9+7
    for i in eng_dict.values():
        ans = (ans*i)%size
    print((ans-1)%size)
n, m = (int(i) for i in input().split())  
a = [[int(i) for i in input().split()] for i in range(n)] 
dic = {}
lis = []

for x in a:
  if x[0] not in dic:
  	dic[x[0]] = x[1]
  else:
    dic[x[0]] += x[1]

sorted_dict = sorted(dic.items(), key=lambda x:x[0])

count = 0
for x in sorted_dict:
  if len(lis) > m - 2:
    break
  else:
    lis += [x[0]] * x[1]
    count += x[1]
  
#print(lis)
print(sum(lis[:m]))

### FIXED CODE ###

n, m = (int(i) for i in input().split())  
a = [[int(i) for i in input().split()] for i in range(n)] 
dic = {}
lis = []

a.sort()
ans = 0
for x in a:
  if x[1] >= m:
    ans += x[0] * m
    break
  else:
    ans += x[0] * x[1]
    m -= x[1]

print(ans)
100 4 16

### FIXED CODE ###

N,A,B=map(int,input().split(' '))
ans=0
for i in range(N):
  if A<=sum([int(s) for s in list(str(i+1))])<=B:
    ans+=(i+1)
print(ans)
import sympy
N = int(input())
div_arr = sympy.divisors(N)

if len(div_arr) == 1:
    print(1)
else:
    memo = []
    if len(div_arr) % 2 == 0:
        last_idx = -1
        count = 0
        for i in range(len(div_arr)):
            count += 1
            if N == div_arr[i] * div_arr[last_idx] and count != len(div_arr) // 2:
                last_idx -= 1
                memo.append(len(str(div_arr[last_idx])))
            else:
                break
    else:
        target_index = len(div_arr) // 2
        memo.append(len(str(div_arr[target_index])))
    print(min(memo))

### FIXED CODE ###

N = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
div_arr = make_divisors(N)

if len(div_arr) == 1:
    print(1)
elif len(div_arr) == 2:
    ans_num = max(div_arr)
    print(len(str(ans_num)))
else:
    memo = []
    if len(div_arr) % 2 == 0:
        last_idx = -1
        count = 0
        for i in range(len(div_arr)):
            count += 1
            if N == div_arr[i] * div_arr[last_idx] and count != len(div_arr) // 2:
                last_idx -= 1
                memo.append(len(str(div_arr[last_idx])))
            else:
                break
    else:
        target_index = len(div_arr) // 2
        memo.append(len(str(div_arr[target_index])))
    print(min(memo))
N,K=map(int,input().split())
li=[map(int,input().split())]
li_sort=sorted(li,reverse=True)
print(sum(li_sort[:K]))

### FIXED CODE ###

N,K=map(int,input().split())
li=list(map(int,input().split()))
li_sort=sorted(li,reverse=True)
print(sum(li_sort[:K]))
N, M = stdin()
X = stdin()
X.sort()
dif = [0] * (len(X) - 1)
for i in range(len(X) - 1):
    dif[i] = X[i + 1] - X[i]

dif.sort()
ans = X[-1] - X[0] - sum(dif[-1:-N:-1])
print(0 if ans <= 0 else ans)


### FIXED CODE ###

import math as mt
import itertools as it
import functools as ft
import random as rnd

stdin = lambda type_ = "int", sep = " ": list(map(eval(type_), input().split(sep)))
joint = lambda sep = " ", *args: sep.join(str(i) if type(i) != list else sep.join(map(str, i)) for i in args)

N, M = stdin()
X = stdin()
X.sort()
dif = [0] * (len(X) - 1)
for i in range(len(X) - 1):
    dif[i] = X[i + 1] - X[i]

dif.sort()
ans = X[-1] - X[0] - sum(dif[-1:-N:-1])
print(0 if ans <= 0 else ans)
import sys
sys.setrecursionlimit(100000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])

q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)
n = 10**2
k = [0]*10**2
for x in range(1,9):
    for y in range(1,9):
        for z in range(1,9):
            for i in range(n+1):
                if (x+y+z)**2 -(x*y+y*z+z*x) == i:
                    k[i-1] += 1
for i in range(int(input())):
    print(k[i])

### FIXED CODE ###

n = 10**4
ans = [0]*10**4
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            a = (x+y+z)**2 -(x*y+y*z+z*x)
            if a <= n:
                ans[a-1] += 1
for i in range(int(input())):
    print(ans[i])
N,M = map(int,input().split())

T = (1900*M)+(100*(N-M))
C = [pow(2,M),pow(2,M)-1]

if M==4: M_set[1]=3

a = T*C[0]
if a//C[1] %C[1]==0:
    print(a//C[1])
else:
    print(a)

### FIXED CODE ###

N,M = map(int,input().split())

T = (1900*M)+(100*(N-M))
C = [pow(2,M),pow(2,M)-1]

print(T*C[0])
a,b,c = int[int(i) for i in input().split()]

if a < b < c:
    print('Yes')

else:
    print('No')

### FIXED CODE ###

a,b,c = [int(i) for i in input().split()]

if a < b < c:
    print('Yes')

else:
    print('No')
A=[int(input()) for i in range(6)]
def Five(A):
	for i in range(len(A)-2):
  		if A[i+1]-A[i] > A[-1]:
    		return print(":(")
	return print("Yay!")
Five(A)

### FIXED CODE ###

A=[int(input()) for i in range(6)]
def Five(A):
    if A[-2]-A[0] > A[-1]:
        return print(":(")
    return print("Yay!")
Five(A)
N = int(input())
A = list(map(int, input().split()))

A.sort()
num = A[0]
for a in A[1:]:
  num *= a
  if num > 10 ** 18:
    print(-1)
    exit()
print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
A.sort()
num = A[0]
for a in A[1:]:
  num *= a
  if num > 10 ** 18:
    print(-1)
    exit()
print(num)
import sys

n = int(input())
for s in sys.stdin:
    x1,y1,x2,y2,x3,y3,x4,y4 = map(float, s.strip().split())
    angle1 = (y2-y1)/(x2-x1)
    angle2 = (y4-y3)/(x4-x3)
    if angle1 == angle2:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

N = input()
 
for n in range(N):
    data = map(float,raw_input().split( ))
    slopes = []
    for i in range(2):
        _x1 = data.pop(0)
        _y1 = data.pop(0)
        _x2 = data.pop(0)
        _y2 = data.pop(0)
         
        if _x1 != _x2:
            slopes.append((_y1 - _y2)/(_x1 - _x2))
     
    if len(slopes) == 0:
        print "YES"
    elif len(slopes) == 1:
        print "NO"
    elif abs(slopes[0] - slopes[1]) < 1e-10:
        print "YES"
    else:
        print "NO"
x = input()
if x = "0":
  print(1)
elif x = "1":
  print(0)  

### FIXED CODE ###

x = input()
if x == "0":
  print(1)
else:
  print(0)
R, G, B, N = map(int, input().split())
ans = 0
for x in range(N // R + 1):
	for y in range(N // G + 1):
		if (N - R * x - G * y) % B == 0 and 0 <= (N - R * x - G * y) // B <= N // B:
			ans += 1
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
print(N - K + 1)
n = int(input())
s = input()
ans = 0
for i in range(n):
    if s[i] == "A" and s[i + 1] == "B" and s[i + 2] == "C":
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n):
    if s[i:i+3] == "ABC":
        ans += 1
print(ans)
L=input("始まりの数")
L=int (L)
R=input("終わりの数")
R=int (R)
d=input("倍数の元となる数")
d=int(d)
for i in range(R):
    if d*i>=R:
      max=i
      break

for i in range(L):
    if d*i>=L:
        min=i
        break

print(str(max-min))

### FIXED CODE ###

L,R,d = (int(x) for x in input().split())
cnt=0
for i in range(L,R+1):
 if i%d==0:
        cnt+=1

print(cnt)
n, a, b = (int(i) for i in input().split())
count = 0
for i in range(1, n):
    res = sum([int(j) for j in str(i)])
    if(a <= res && res <= b):
        count = count + 1
print(count)

### FIXED CODE ###

n, a, b = (int(i) for i in input().split())
result = 0
for i in range(1, n + 1):
    res = sum([int(j) for j in str(i)])
    if(a <= res & res <= b):
        result = result + i
print(result)
import numpy as np
N, K = map(int,input().split())
A= list((map(int, input().split())))
an = (K*(K+1))//2
a = ((K-1)*K)//2
au =0
al = 0
for i in range(N):
    for j in range(N):
        au += 1 if A[i]<A[j] and i>j else 0
        al += 1 if A[i]<A[j] and i<j else 0
print((au*an+al*a)%(10**9+7))

### FIXED CODE ###


N, K = map(int,input().split())
A= list((map(int, input().split())))
an = (K*(K+1))//2
a = ((K-1)*K)//2
au =0
al = 0
for i in range(N):
  for j in range(N):
    au += 1 if A[i]<A[j] and i>j else 0
    al += 1 if A[i]<A[j] and i<j else 0
print((au*an+al*a)%(10**9+7))
lst = list(map(int, input().split()))

x = lst[0]
a = lst[1]
b = lst[2]

if abs(b-x) > (a-x):
    return "A"
else:
    return "B"

### FIXED CODE ###

lst = list(map(int, input().split()))

x = lst[0]
a = lst[1]
b = lst[2]

if abs(b-x) > abs(a-x):
    print("A")
else:
    print("B")
from operator import mul
from functools import reduce
def cmb(n, r):
    if r > n:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

N, K = map(int, input().split())

r_cnt = N - K
b_cnt = K

for i in range(1, K+1):
    print(( cmb( r_cnt+1, i ) * cmb( b_cnt-

### FIXED CODE ###

from operator import mul
from functools import reduce
def cmb(n, r):
    if r > n:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

N, K = map(int, input().split())

r_cnt = N - K
b_cnt = K

for i in range(1, K+1):
    print(( cmb( r_cnt+1, i ) * cmb( b_cnt-1, i-1 )) % (10**9+7))
n=int(input())
a=list(map(int,input().split()))
if n==1:
  if a==[0,1]:
    print(2)
  elif a==[0,2]:
    print(3)
  else:
    print(-1)
  exit()
subt=[0]*(n)
if a[0] == 0:
  subt[0]=2
elif a[0]== 1:
  subt[0]=1
else:
  print(-1)
  exit()

for i in range(n-1):
  if a[i+1] > subt[i]-1:
    if i<n-1:
      print(-1)
      exit()
    elif a[i+1] > subt[i]:
      print(-1)
      exit()
  else:  
    subt[i+1]=(subt[i]-a[i+1])*2
if a[n]> subt[-1]:
  print(-1)
  exit()
if a[n] > subt[-2]:
  subt[-1]=a[n]
else:
  subt[-1]=a[n]
  for j in range(2,n):
    if (subt[-j]-a[-j])*2 < subt[1-j]:
      print(-1)
      exit()
    if (subt[-j]-a[-j]) <= subt[1-j]:
      pass
    else:
      subt[-j]=subt[1-j]+a[-j]
print(sum(subt)+1)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if n==1:
  if a==[0,1]:
    print(2)
  elif a==[0,2]:
    print(3)
  else:
    print(-1)
  exit()
if n==0:
  if a==[1]:
    print(1)
  else:
    print(-1)
  exit()



subt=[0]*(n)
if a[0] == 0:
  subt[0]=2
elif a[0]== 1:
  subt[0]=1
else:
  print(-1)
  exit()

for i in range(n-1):
  #subt[i+1]=subt[i]-subt[i]*2
  #print(subt[i])
  if a[i+1] > subt[i]-1:
    if i<n-1:
      print(-1)
      #print(n)
      #print(subt[i])
      exit()
      #pass
    elif a[i+1] > subt[i]:
      print(-1)
      exit()
      #pass
  else:  
    subt[i+1]=(subt[i]-a[i+1])*2
if a[n]> subt[-1]:
  print(-1)
  exit()
if a[n] > subt[-2]:
  subt[-1]=a[n]
else:
  subt[-1]=a[n]
  for j in range(2,n):
    if (subt[-j]-a[-j])*2 < subt[1-j]:
      print(-1)
      exit()
    if (subt[-j]-a[-j]) <= subt[1-j]:
      pass
    else:
      subt[-j]=subt[1-j]+a[-j]
  
    #pass
  
print(sum(subt)+1)
    
#print(subt)
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    mod = 1000000007

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

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    mod = 1000000007

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

if __name__ == '__main__':
    main()