Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# DP[0, 0], Aの数、ABの数、ABCの数
MOD = 10 ** 9 + 7
S = sr()
dp = [0, 0, 0]
total = 1
for s in S:
    if s == 'A':
        dp[0] += total
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[2] += dp[1]
    elif s == '?':
        dp[2] = dp[2]*3 + dp[1]
        dp[1] = dp[1]*3 + dp[0]
        dp[0] = dp[0]*3 + total
        total *= 3
    #print(dp, total)

print(dp[2]%MOD)


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()[::-1]
MOD = 10 ** 9 + 7
answer = 0
dp = [0, 0, 1] #Cの数, BC数, 総数
for i in range(len(S)):
    s = S[i]
    if s == 'A':
        answer += dp[1]
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[0] += dp[2]
    elif s == '?':
        answer *= 3
        answer += dp[1]
        dp[1] *= 3
        dp[1] += dp[0]
        dp[0] *= 3
        dp[0] += dp[2]
        dp[2] *= 3
    answer %= MOD
    dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
print(answer)
### BUGGY CODE ###

h, n = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
a, b = x[0]
dp = [-(-i // a) * b for i in range(h + 1)]
for j in range(1, n):
    a, b = x[j]
    for i in range(h + 1):
        if i >= a:
            dp[i] = min(dp[i], dp[i - a] + b)
        else:
            dp[i] = min(dp[i], b)
print(dp[-1])


### FIXED CODE ###

h, n = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
a, b = x[0]
dp = [-(-i // a) * b for i in range(h + 1)]
for j in range(1, n):
    a, b = x[j]
    for i in range(min(h + 1, a)):
        dp[i] = min(dp[i], b)
    for i in range(a, h + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(dp[-1])
### BUGGY CODE ###

######## 関数 ############

# insertion sort : 小さいものから順に並べる
# リストの途中までソートされている場合に時間を短縮
# A[0], ..., A[m-1]までソート済み、A[m],...,A[n]はソートされていない場合
# insertion_sort( A[m:n+1], A[0:m]) とすることで、時間短縮
def insertion_sort(unsorted, sorted = []):
    A = sorted + unsorted # リストを連結
    for i in range(len(sorted), len(A)): # i = len(sorted), len(sorted)+1, ..., len(A)-1
        for j in range(i, 0, -1): # j = i, i-1, ..., 1
            if A[j] < A[j-1]:
                temp = A[j]
                A[j] = A[j-1]
                A[j-1] = temp
    return A

##### プログラム ###############

# 入力を受け取る
N, M = input().strip().split()
N, M = [int(N), int(M)]
A = input().strip().split()
A = list(map(int, A))     # 整数に変換

# Aを安い順にソートする
A = insertion_sort(A)

for i in range(M): # 各割引券1枚ずつ、一番高い品物に使っていく
    A[N-1] //= 2   # 右端が一番高い。1枚使うと半額
    A = insertion_sort(A[N-1:N], A[0:N-1]) # 安い順に並び替え

total_price = 0
for i in range(N):
    total_price += A[i]

print(total_price)

### FIXED CODE ###

import heapq

######## クラス ############
class MaxHeap:
    def __init__(self, H=[]):
        self.heapify(H)

    def heapify(self, H):
        self._neg_heap = [ -a for a in H ] # マイナスをかける
        heapq.heapify( self._neg_heap )

    def push(self, value):
        heapq.heappush(self._neg_heap, -value)

    def pop(self):
        return (-1) * heapq.heappop(self._neg_heap)

    def get_heap(self):
        return [ -a for a in self._neg_heap ]



##### プログラム ###############

# 入力を受け取る
N, M = input().strip().split()
N, M = [int(N), int(M)]
A = input().strip().split()
A = [int(a) for a in A] # 整数に変換

price_heap = MaxHeap(A)

i = 0
for i in range(M):# 各割引券1枚ずつ、一番高い品物に使っていく
    price = price_heap.pop() # 一番高い品物
    price //= 2  # 一番高い商品に割引券を使って半額にする
    price_heap.push(price) # 半額になった商品をheapに戻す
    i += 1

total_price = 0
new_prices = price_heap.get_heap()

for i in range(N):
    total_price += new_prices[i]

print(total_price)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
answer = N

for i in range(N - 1):
    temp = A[i]
    right = i + 1
    while temp + A[right] == temp ^ A[right]:
        temp += A[right]
        answer += 1
        right += 1
        if right == N:
            break

print(answer)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
answer = 0
temp = A[0]
right = 0

for i in range(N):
    if right < N - 1:
        while temp + A[right + 1] == temp ^ A[right + 1]:
            right += 1
            temp += A[right]
            if right == N - 1:
                break
    temp -= A[i]
    answer += right - i + 1

print(answer)
### BUGGY CODE ###

from collections import Counter

n=int(input())
l=[input() for i in range(n)]
c=Counter(l)
max_list=[kv[0] for kv in c.items() if kv[1]==max(c.values())]
max_list.sort()
for j in max_list:
  print(j)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
d = {}
for w in s:
    if w not in d:
        d[w] = 0
    d[w] += 1
d2 = sorted(d.items(), key=lambda x:x[1], reverse=True)
maxcnts = [w[0] for w in d2 if w[1] == d2[0][1]]
maxcnts.sort()
for ans in maxcnts:
    print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(100000)  # RecursionError対策


def solve():
    N, K = list(map(int, input().split()))
    MOD = 10**9+7

    """
    青をi個のゾーンに区別可能か？
    """

    op_dict = {}
    for i in range(1, K+1):
        op_dict[i] = 0

    def dfs(depth, rest_r, rest_b, pre_ball, op_cnt):
        if depth == N or rest_b==0 or (rest_r==0 and pre_ball=="B"):
            op_dict[op_cnt] += 1
            op_dict[op_cnt] %= MOD
            return
        
        if rest_r != 0:
            dfs(depth+1, rest_r-1, rest_b, "R", op_cnt)
        
        if rest_b != 0:
            if pre_ball != "B":
                op_cnt += 1
            dfs(depth+1, rest_r, rest_b-1, "B", op_cnt)
        return
    
    dfs(0, N-K, K, "NULL", 0)

    for i in range(1, K+1):
        print(op_dict[i])
        




if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(100000)  # RecursionError対策

"""解説
(1) まず、赤いボールをN-K個一列に並べる

(2) 赤いボールと赤いボールの隙間をi箇所選んで、そこに青いボールをK個置くことを考える

 R R R R R
0 1 2 3 4 5

    この選び方は、(N-K+1)C(i)通り

(3) それぞれの選び方について、青いボールをそれぞれの隙間に何個割り当てるかを考える。
    それぞれ1個以上割り当てる必要があるので、決め方は(K-1)C(i-1)通り。


[入力例1]
B B B R R

・i=1
Bの塊を挿入する位置は、
 R R  |  R R  |  R R
^     |   ^   |     ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において1通り

よって、3*1 = 3通り


・i=2
 R R  |  R R   |  R R
^ ^   | ^   ^  |   ^ ^
の3通り

で、

Bを分配する場合の数はそれぞれの場合において、

- 少なくとも1個ずつ分配すると、自由におけるBの数は1個
- 2箇所に玉1つを分配する場合の数は
(2)C(1) = 2通り

よって3*2 = 6通り

・i=3
 R R
^ ^ ^
の1通り


[重複組み合わせの考え方]
http://www7b.biglobe.ne.jp/~math-tota/suA/tamahako.htm

B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
B-i個の玉と、i-1個の区切りの重複組み合わせ。

・6個の玉を、区別のできる3つの箱に分ける場合の数
6個の玉と、2個のしきりの重複組み合わせ

○○○○|○○| (4,2,0)の場合
|○○|○○○○ (0,2,4)の場合

「8個のオブジェクトのうち、2個を選んでしきりにする」と同じなので、(8)C(2) = 28

"""
from math import factorial

def combination_formula(n, r):
    return factorial(n) // (factorial(r)*factorial(n-r))

def solve():
    N, K = list(map(int, input().split()))
    B, R = K, N-K
    MOD = 10**9+7

    for i in range(1, K+1):
        if R+1-i < 0:
            print(0)
            continue
        
        # R+1から、i個選ぶ
        ans = combination_formula(R+1, i)
        if B-i == 0:
            print(ans%MOD)
            continue
        # B-i個の玉を、区別のできるi個の箱に分ける場合の数みたいな計算をしたい。これは言い換えると、
        # B-i個の玉と、i-1個の区切りの重複組み合わせ。
        if B-i+i-1-(i-1) >= 0:
            ans *= combination_formula(B-i+i-1, i-1)%MOD
        print(ans%MOD)



if __name__ == "__main__":
    solve()
### BUGGY CODE ###

N=int(input())
import math

for i in range(1,N+1):
    ans=0
    for x in range(1,33):
        x2=x*x
        for y in range(1,x+1):
                if x2+y^2<1000:
                    a=-(3*(x2)+3*(y*y)+2*x*y)/4+i
                    if a>0:
                        b=(math.sqrt(a)-(x+y)/2)
                        if b>0 and b%1==0.0:
                            if x==y:
                                ans+=1
                            else:
                                ans+=2

    print(ans)



### FIXED CODE ###

N=int(input())
li=[0]*N
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            temp=x**2+y**2+z**2+x*y+y*z+z*x
            if temp<=N:
                li[temp-1]+=1
for i in range(N):
    print(li[i])
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

for i in range(N):
    sam = P[i]
    P[i] = (sam+1)/2

ans = 0
total = 0

for i in range(N-K+1):
    total = sum(P[:K+i]) - sum(P[:i])

    if ans < total:
        ans = total

print(ans)
    



### FIXED CODE ###

N,K = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

for i in range(N):
    sam = P[i]
    P[i] = (sam+1)/2

total1 = 0

for i in range(K):
    total1 += P[i]

ans = total1
total2 = 0

for i in range(N-K):

    total1 += P[K+i]
    total2 += P[i]
    
    if ans < total1 - total2:
        ans = total1 - total2


print(ans)
### BUGGY CODE ###

K = int(input())
val = set()
if K % 2 == 0:
    print(-1)
    exit()
for i in range(1,200000):
    val.add(i*K)
j = 7
for i in range(1000000):
    if j in val:
        print(len(str(j)))
        exit()
    j *= 10
    j += 7
print(-1)


### FIXED CODE ###

K = int(input())
val = 7
for i in range(1,2000000):
    val %= K
    if val == 0:
        print(i)
        exit()
    else:
        val = val*10+7
print(-1)
### BUGGY CODE ###

N,M = map(int,input().split())
L=[]
R=[]
Nlist = list(range(1,N+1))
for i in range(M):
  L_n,R_n = map(int,input().split())
  L.append(L_n)
  R.append(R_n)
for i in range(M):
  Nlist = [k for k in Nlist if (k > (L[i]-1)) and (k < (R[i]+1))]
print(len(Nlist))

### FIXED CODE ###

N,M = map(int,input().split())
L=[]
R=[]
Nlist = list(range(1,N+1))
for i in range(M):
  L_n,R_n = map(int,input().split())
  L.append(L_n)
  R.append(R_n)

Lmax=max(L)
Rmin=min(R)
if Rmin < Lmax:
  print(0)
else:
  print(Rmin-Lmax+1)
### BUGGY CODE ###

from functools import lru_cache

def main(S):
    con = 10**9 + 7

    @lru_cache(maxsize=128, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 5
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    S = input()
    main(S)

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
l = n * m // gcd(n, m)
a = ["" for i in range(l)]
for i in range(n):
    a[i*l//n] = s[i]
for i in range(m):
    if a[i*l//m] != "":
        if a[i*l//m] == t[i]:
            continue
        else:
            print(-1)
            exit()
    else:
        continue
print(l)



### FIXED CODE ###

from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
g = gcd(n,m)
l = n*m//g
for k in range(g):
    if s[k*n//g] != t[k*m//g]:
        print(-1)
        exit()
print(l)
### BUGGY CODE ###

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    AB = []
    # AB.append=append
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])
    ABC = []
    for i in range(X * Y):
        for j in range(Z):
            ABC.append(AB[i] + C[j])
    ABC.sort()
    print('\n'.join(map(str, ABC[:-K-1:-1])))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    AB = []
    ABappend = AB.append
    for i in range(X):
        for j in range(Y):
            ABappend(A[i] + B[j])
    AB.sort(reverse=True)
    ABC = []
    ABCappend = ABC.append
    for i in range(min(K, X*Y)):
        for j in range(Z):
            ABCappend(AB[i] + C[j])
    ABC.sort(reverse=True)
    print('\n'.join(map(str, ABC[:K])))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#https://atcoder.jp/contests/agc033/tasks/agc033_a

HW = [int(i) for i in input().split()]
A = []
for i in range(HW[0]):
    A.append(list(str(input())))

B = []
for i in range(len(A)):
    B.append([])
    for j in range(len(A[i])):
        B[i].append(A[i][j])

count = 0
count2 = 0
flag = False
tmp = ['.'] * len(A[0])
while True:
    for i in range(len(A)):
        if i > 0:
            tmp = A[i-1]
        j = 0
        while True:
            if A[i][j] == '.':
                if flag == True:
                    B[i][j] = '#'
                    flag = False
                    j += 1
                else:
                    if tmp[j] == '#':
                        B[i][j] = '#'
                        j += 1
                    elif i < len(A) - 1 and A[i+1][j] == '#':
                        B[i][j] = '#'
                        j += 1
                    elif j < len(A[i]) - 1 and A[i][j+1] == '#':
                        B[i][j] = '#'
                        j += 2
                        count += 1
                        flag = True
                    else:
                        j += 1
            else:
                count += 1
                flag = True
                j += 1
            
            if j >= len(A[i]):
                break
    
    for i in range(len(A)):
        for j in range(len(A[i])):
            A[i][j] = B[i][j]
    if count == HW[0] * HW[1]:
        break
    else:
        count = 0
        count2 += 1

print(count2)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

h, w = MAP()
a = [STR() for _ in range(h)]
b = [[inf for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
for i in reversed(range(h)):
    for j in reversed(range(w)):
        if a[i][j] == '#':
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
ans = 0
for i in range(h):
    ans = max(ans, max(b[i]))
print(ans)
### BUGGY CODE ###

n=int(input())
s=0
while n!=0:
    s+=n%10
    n=n//10
if s%9==0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=str(input())
ans=0
for i in s:
    ans+=int(i)
if ans%9==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

mod=10**9+7
k=int(input())
s=input()
l=len(s)
fact=[1] #0!～(|S|+k)!の前計算を行う
for i in range(1,k+l+1):
 fact.append((fact[-1]*i)%mod)
revfact=[]
for i in range(k+l+1): #0!～(|S|+k)!の逆数の前計算を行う
 revfact.append(pow(fact[i],mod-2,mod))
pow1=[1]
pow2=[1]
for i in range(1,k+l+1): #25^Kと26^Kの前計算を行う
 pow1.append((pow1[-1]*25)%mod)
 pow2.append((pow2[-1]*26)%mod)
ans=0
for i in range(k+l): #Sの最後の文字を置く場所を|S|+Kマスの中からすべて試す
 coef1=(pow1[k-i]*pow2[i])%mod
 if i<=k:
   coef2=(fact[k+l-1-i]*revfact[l-1]*revfact[k-i])%mod
 else:
   coef2=0
 ans+=coef1*coef2
 ans%=mod
print(ans)


### FIXED CODE ###

import collections
import heapq

from collections import defaultdict
from heapq import heappush, heappop
import sys


def main(K, N):
    P = 10 ** 9 + 7

    P25 = [1] * (K + 1)
    P26 = [1] * (K + 1)
    F = [1] * (N + K)
    INV = [1] * (N + K)
    INVF = [1] * (N + K)

    p25 = 1
    p26 = 1
    for i in range(1, K + 1):
        p25 *= 25
        p25 %= P
        P25[i] = p25

        p26 *= 26
        p26 %= P
        P26[i] = p26

    f = 1
    invf = 1
    for i in range(2, N + K):
        f *= i
        f %= P
        F[i] = f
        q, r = divmod(P, i)
        INV[i] = -INV[r] * q % P
        invf *= INV[i]
        invf %= P
        INVF[i] = invf

    def comb_rep(n, r):
        return (F[n + r - 1] * INVF[r] % P) * INVF[n - 1] % P

    ret = 0
    for i in range(K + 1):
        ret += (
            P25[i] *
            P26[K - i] % P *
            comb_rep(N, i) % P
        )
    return (ret % P)


if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8)')(main)
    cc.compile()
    exit()
else:
    from my_module import main
    K = int(input())
    S = input()
    print(main(K, len(S)))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

if n <= k:
    print(0)
    exit()

for i in range(k):
    h.remove(max(h))
print(sum(h))


### FIXED CODE ###

n, k = map(int, input().split())
h = sorted(list(map(int, input().split())), reverse=True)

if n <= k:
    print(0)
    exit()
del h[0:k]
print(sum(h))
### BUGGY CODE ###

from itertools import permutations


def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


N, M, R = map(int, input().split())
r = list(map(int, input().split()))

d = [[1000000000] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i]][p[i + 1]]
    result = min(result, t)
print(result)


### FIXED CODE ###

from itertools import permutations


def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


N, M, R = map(int, input().split())
r = list(map(int, input().split()))

d = [[1000000000] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i]][p[i + 1]]
    result = min(result, t)
print(result)
### BUGGY CODE ###

H, W, A, B = map(int, input().split())

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

def rev(n):
    return mod_pow(n, m - 2, m)

def cr(c, r):
    return fc[c + r] * rev(fc[c] * fc[r] % m) % m


ans = 0
for c in range(B, W):
    ans = (ans + cr(c, H - 1 - A) * cr(W - 1 - c, A - 1)) % m
print(ans)

### FIXED CODE ###

H, W, A, B = map(int, input().split())

m = 10**9 + 7

import functools
@functools.lru_cache(maxsize=None)
def cr(c, r):
    return fc[c + r] * ic[c] * ic[r] % m

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m
ic = [pow(x, m-2, m) for x in fc]

ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1) % m
print(ans % m)
### BUGGY CODE ###

K = int(input())
A = list(map(int, input().split()))


l = 0
r = 10 ** 20
while r - l > 1:
    m = (r + l) // 2
    N = m
    for a in A:
        N = (N//a)*a

    if N > 2:
        r = m
    else:
        l = m
upper = l


l = 0
r = 10 ** 20
while r - l > 1:
    m = (r + l) // 2
    N = m
    for a in A:
        N = (N//a)*a

    if N < 2:
        l = m
    else:
        r = m
lower = r

if lower > upper:
    print(-1)
else:
    print(lower, upper)


### FIXED CODE ###

K = int(input())
A = tuple(map(int, input().split()))

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M <= 2:
        l = m
    else:
        r = m
ans_max = l

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M >= 2:
        r = m
    else:
        l = m
ans_min = r

if ans_min > ans_max:
    print(-1)
else:
    print(ans_min, ans_max)