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

import math
honsu,hp=map(int , input().split())
huru=[]
nageru=[]
for i in range(honsu):
  a,b=input().split()
  huru.append(int(a))
  nageru.append(int(b))
cc=list(filter(lambda v:v>=max(huru) , nageru))
cou=0
for i in reversed(sorted(cc)):
  hp-=i
  cou+=1
  if hp<=0:
    break
if hp>0:
  cou+=math.ceil(hp/max(huru))
print(cou)

### FIXED CODE ###

from math import ceil
 
N, H = map(int, input().split())
a, b = [], []
 
for _ in range(N):
    a_i, b_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
 
max_a = max(a)
b = sorted(b, reverse=True)
ans = float('inf')
th_po = 0
 
for i in range(N):
    th_po += b[i]
    
    if H >= th_po:
        ans_cand = i + 1 + ceil((H - th_po) / max_a)
    else:
        ans_cand = i + 1
    
    ans = min([ans, ans_cand])
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[43]:


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


# In[44]:


if sum(A) < sum(B):
    ans = -1
else:
    diff_plus = sorted([B[i]-A[i] for i in range(N) if B[i]-A[i]>0])
    diff_minus = sorted([A[i]-B[i] for i in range(N) if A[i]-B[i]>0],reverse=True)
    if len(diff_plus) > 0:
        j = 0
        cnt = len(diff_plus)
        for i,x in enumerate(diff_plus):
            while sum(diff_minus[:j+1]) < x:
                j += 1
            diff_minus[j] = sum(diff_minus[:j+1])-x
            for k in range(j):
                diff_minus[k] = 0
        ans = j+1+cnt
    else:
        ans = 0
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[43]:


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


# In[45]:


# if sum(A) < sum(B):
#     ans = -1
# else:
#     diff_plus = sorted([B[i]-A[i] for i in range(N) if B[i]-A[i]>0])
#     diff_minus = sorted([A[i]-B[i] for i in range(N) if A[i]-B[i]>0],reverse=True)
#     if len(diff_plus) > 0:
#         j = 0
#         cnt = len(diff_plus)
#         for i,x in enumerate(diff_plus):
#             while sum(diff_minus[:j+1]) < x:
#                 j += 1
#             diff_minus[j] = sum(diff_minus[:j+1])-x
#             for k in range(j):
#                 diff_minus[k] = 0
#         ans = j+1+cnt
#     else:
#         ans = 0
# print(ans)


# In[47]:


husoku = [a-b for a, b in zip(A, B) if a-b < 0]
amari = [a-b for a, b in zip(A, B) if a-b > 0]
amari.sort(reverse=True)
 
H = abs(sum(husoku))
if len(husoku) == 0:
    ans = 0
elif H > sum(amari):
    ans = -1
else:
    for i, a in enumerate(amari, start=1):
        H -= a
        if H <= 0:
            ans = len(husoku) + i
            break
print(ans)


# In[ ]:
### BUGGY CODE ###

import math
import random

def is_prime(n):
    if n == 1: return False
    if n == 2: return True

    for k in range(100):
        a = random.randint(2, n - 1)

        if gcd(n, a) != 1:
            return False

        if pow(a, n - 1, n) != 1:
            return False

    return True

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

n,m=(int(i) for i in input().split(' '))
if is_prime(m):
  print('1')
else:
  for i in range(1,m//n+1)[::-1]:
    if i==1:
      print(i)
      break
    if m%i==0 and m//i>=n:
      print(i)
      break


### FIXED CODE ###

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and (is_prime(i) or i==1) and is_prime(m//i) and (i==1 or m//i<n):
    print('1')
    exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m-i-n>0 and m%(m-i-n)==0 and m//(m-i-n)>n:
    print(m-i-n)
    break
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()
ans= max(a.count(a[0]) + a.count(a[0]+1),a.count(a[-1]) + a.count(a[-1]-1))

for i in range(len(a)):
  counter = a.count(a[i]-1) + a.count(a[i])+a.count(a[i]+1)
  if ans < counter:
    ans = counter
  
print(ans)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
cand = collections.Counter(a)
cand_list = cand.most_common(len(set(a)))
ans = 0
for i in range(len(set(a))):
  num = cand_list[i][0]
  count = cand[num] + cand[num + 1] + cand[num - 1]
  ans = max(ans,count)

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

import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
count=0
b=len(collections.Counter(a))
#print(b)
for i in range(min(k,b)):
    count+=collections.Counter(a).most_common()[i][1]
#    print(count)
ans=len(a)-count
print(ans)

### FIXED CODE ###

import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
count=0
b=len(collections.Counter(a))
c=collections.Counter(a).most_common()
#print(b)
for i in range(min(k,b)):
    count+=c[i][1]
#    print(count)
ans=len(a)-count
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
h = list(map(int,input().split()))
inf = 10 ** 10
dp = [inf] * n
dp[0] = 0
for i in range(n - 1):

    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
def ch_min(a,b):
    if a>b:
        return b
    
    return a
def solve():
    dp=[float('inf')]*n
    dp[0]=0

    for i in range(1,n):
    
        for j in range(1,1+k):
            if i-j>=0:
                dp[i]=ch_min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
                
                if dp[i]==0:
                    break
                
    print(dp[-1])
    

solve()
### BUGGY CODE ###

L, R = [[], []]
N, M = map(int, input().split())
for i in range(M):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)

count = 0
for i in range(1,N+1):
  s = True
  for j in range(M):
    if L[j]>i or i>R[j]:
      s = False
      break
  if s:
    count = count + 1

print('%d' % count)

### FIXED CODE ###

L, R = [[], []]
N, M = map(int, input().split())
for i in range(M):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)

count = 0
minR = min(R)
maxL = max(L)
if minR < maxL:
  count = 0
else:
  for i in range(maxL, minR+1):
    if i <= N:
      count = count + 1
      
print('%d' % count)
### BUGGY CODE ###

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

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(max(A)//2+1)

for i in range(2, max(A)//2+1):
    if checked[i]:
        continue
    
    tmp = 0
    for j in range(N):
        if A[j]%i == 0:
            tmp += 1
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    n = i
    while n < max(A)//2+1:
        checked[n] = 1
        n += i

if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)

# 素因数テーブルの作成
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因子をカウント
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        nums[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n = input()
val = 1
for num in range(1,(int(n,10) + 1)):
    val = num * val
else:
    print (val % (10**9 + 7))

### FIXED CODE ###

import math
n = int(input())
val = math.factorial(n)
print (val % (10**9 + 7))
### BUGGY CODE ###

def func_rfindr(str):
    return str.rfind('R')

def func_lfindw(str):
    return str.find('W')

def func_replace(target, pos, str):
    ret = ""
    if pos != 0:
        ret = target[0:pos]
    ret = ret + str
    if len(target) - 1 != pos:
        ret = ret + target[pos + 1:]
    return ret

N = int(input())
C = input()
ans = 0

posrr = func_rfindr(C)
poslw = func_lfindw(C)

while poslw != -1 and posrr != -1 and posrr > poslw:
    C = func_replace(C, posrr, "W")
    C = func_replace(C, poslw, "R")
    ans = ans + 1
    posrr = func_rfindr(C)
    poslw = func_lfindw(C)

print(ans)

### FIXED CODE ###

def func_rfindr(str):
    return str.rfind('R')

def func_lfindw(str):
    return str.find('W')

def func_replace(target, pos, str):
    ret = ""
    if pos != 0:
        ret = target[0:pos]
    ret = ret + str
    if len(target) - 1 != pos:
        ret = ret + target[pos + 1:]
    return ret

N = int(input())
C = input()
ans = 0

posrr = func_rfindr(C)
poslw = func_lfindw(C)

while poslw != -1 and posrr != -1 and posrr > poslw:
    #C = func_replace(C, posrr, "W")
    #C = func_replace(C, poslw, "R")
    C = C[poslw + 1:posrr]
    ans = ans + 1
    posrr = func_rfindr(C)
    poslw = func_lfindw(C)

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

import collections
N=int(input())
s=[sorted(list(input())) for _ in range(N)]
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        if s[i]==s[j]:
            ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
d={}
ans=0
for i in range(N):
    s=''.join(sorted(input()))
    if s in d:
        ans+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(ans)
### BUGGY CODE ###

A, B, N = map(int, input().split())

def floor(t):
  return int(t)

max = 0 
for x in range(1, N+1):
  y = floor(A*x/B)-A*floor(x/B)
  if y > max:
    max = y
    
print(max)

### FIXED CODE ###

A, B, N = map(int, input().split())

def g(x):
  return int(A*x/B)-A*int(x/B)

print(g(min(B-1, N)))
### BUGGY CODE ###

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

p = [0]+p

ansList =[]
for i in range(1,n+1):
  if min(p[1:i+1])==p[i]:
    ansList.append(p[i])
    
print(len(ansList))

### FIXED CODE ###

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

MIN = 10**10
cnt =0
for i in p:
  if i<=MIN:
    MIN = i
    cnt +=1
print(cnt)
### BUGGY CODE ###

import sys
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
_sum_ls = []
cnt = 0
for i in range(1,n-1):
    base = l_ls[i]
    next_base = l_ls[i+1]
    for j in range(0,i):
        _sum_ls.append(l_ls[j] + base)
    for _sum in _sum_ls:
        if next_base < _sum:
            cnt += 1
print(cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_left

n, m = li()
lrc = [list(li()) for _ in range(m)]

# l -> r の降順にソート
lrc = sorted((sorted(lrc, key=lambda x: x[1])), key=lambda x: x[0])

# 二分探索で距離更新
INF = float('inf')
dist = [INF]*n
dist[0] = 0

for left_idx, right_idx, ci in lrc:
    left_idx -= 1
    newleft_idx = bisect_left(dist, dist[left_idx] + ci)
    for idx in range(newleft_idx, right_idx):
        dist[idx] = dist[left_idx] + ci

if dist[-1] == INF:
    print(-1)
else:
    print(dist[-1])


### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

n, m = li()
lrc = [list(li()) for _ in range(m)]

# n = 10**5
# m = 10**5
# lrc = [[1, n, 5] for _ in range(m)]

# l -> r の降順にソート
lrc = sorted(lrc, key=lambda x: x[2])
lrc = sorted(lrc, key=lambda x: x[1])
lrc = sorted(lrc, key=lambda x: x[0])
#lrc = sorted((sorted(lrc, key=lambda x: x[1])), key=lambda x: x[0])

# 二分探索で距離更新
INF = float('inf')
dist = [INF]*n
dist[0] = 0

for left_idx, right_idx, ci in lrc:
    left_idx -= 1
    newleft_idx = bisect_right(dist, dist[left_idx] + ci)
    for idx in range(newleft_idx, right_idx):
        dist[idx] = dist[left_idx] + ci

if dist[-1] == INF:
    print(-1)
else:
    print(dist[-1])
### BUGGY CODE ###

n,x,y = map(int,input().split())
dis = [[0 for _ in range(n)]for p in range(n)]
dis[0][1] = 1
dis[n-1][n-2] = 1
dis[x-1][y-1] = 1
dis[y-1][x-1] = 1
for i in range(1,n-1):
    dis[i][i-1] = 1
    dis[i][i+1] = 1

def bfs(start):
    queue = [start]
    disq = [0]
    searched = [start]
    while(len(queue)):
        now = queue.pop(0)
        dnow = disq.pop(0)
        for goal in range(n):
            if not goal in searched:
                if dis[now][goal] == 1:
                    queue.append(goal)
                    disq.append(dnow + 1)
                    if dis[start][goal] == 0:
                        dis[start][goal] = dnow + 1
                    else:
                        dis[start][goal] = min(dnow + 1,dis[start][goal])
                    searched.append(now)

for i in range(n):
    bfs(i)

dissum = [0 for _ in range(n-1)]

for i in range(n):
    for j in range(i):
        dissum[dis[i][j]-1] += 1

for i in range(len(dissum)):
    print(dissum[i])

### FIXED CODE ###

n,x,y = map(int,input().split())
x -= 1
y -= 1
dis = [0 for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        dis[min(abs(j-i),min(abs(j-y)+abs(x-i)+1,abs(j-x)+abs(y-i)+1))] += 1
print("\n".join(map(str,dis[1:])))
### BUGGY CODE ###

import sys, math
sys.setrecursionlimit(200010)

def input():
    return sys.stdin.readline()[:-1]

def main():
    N, Q = map(int,input().split())
    G = [[] for k in range(N)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    V = [0]*N
    D = [0]*N
    for k in range(Q):
        p, x = map(int,input().split())
        D[p-1] += x

    def dfs(visited,distance,graph,ima):
        for e in graph[ima]:
            if visited[e] == 0:
                visited[e] = 1
                distance[e] += distance[ima]
                dfs(visited,distance,graph,e)
    V[0] = 1
    dfs(V,D,G,0)

    print(*D)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(200010)

def main():
    input = sys.stdin.readline
    N, Q = map(int,input().split())
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
    kyori = [0 for k in range(N+1)]
    for k in range(Q):
        p, x = map(int,input().split())
        kyori[p] -= x
    def dfs(now, dist):
        for tsugi in G[now]:
            if kyori[tsugi] <= 0:
                kyori[tsugi] = -kyori[tsugi]
                kyori[tsugi] += dist
                dfs(tsugi, kyori[tsugi])
    kyori[1] = -kyori[1]
    dfs(1,kyori[1])
    print(*kyori[1:], sep = " ")

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

def printt(x):
  print(x,flush=True)
  i=input()
  if i=="Vacant":exit()
  if i=="Male":return 0
  return 1
n=int(input())
ng=0
ok=n
f=printt(0)
while ng+1!=ok:
  mid=(ok+ng)//2
  if (printt(mid)==f)==((ng+mid)%2==0):ng=mid
  else:ok=mid

### FIXED CODE ###

n=int(input())
def out(i):
  print(i,flush=True)
  s=input()
  if s=="Male":return 0
  elif s=="Female":return 1
  else:exit()
f=out(0)
ng=0
ok=n
while ng+1!=ok:
  mid=(ng+ok)//2
  if (mid+f)%2==out(mid)%2:ng=mid
  else:ok=mid
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
for x in range(q):
    b.append(list(map(int, input().split())))

hikaku = 0
a_wa = sum(a)

for i in range(q):
    cou = collections.Counter(a)

    a_wa += cou[b[i][0]] * b[i][1] - cou[b[i][0]] * b[i][0]
    for l in range(cou[b[i][0]]):
        a.remove(b[i][0])
        a.append(b[i][1])

    print(a_wa)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
for x in range(q):
    b.append(list(map(int, input().split())))

hikaku = 0
a_wa = sum(a)
cou = collections.Counter(a)
for i in range(q):
    a_wa += cou[b[i][0]] * b[i][1] - cou[b[i][0]] * b[i][0]
    cou[b[i][1]] += cou[b[i][0]]
    cou[b[i][0]] = 0

    print(a_wa)
### BUGGY CODE ###

n,m = map(int,input().split())
L = [0]*m; R = [0]*m; cnt = 0
for i in range(m):
    L[i],R[i] = map(int,input().split())
for i in range(1, n+1):
    if max(L) <= i <= min(R):
        cnt += 1
print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
L = [0]*m; R = [0]*m; cnt = 0
for i in range(m):
    L[i],R[i] = map(int,input().split())
ml = max(L); mr = min(R)
print(mr-ml+1) if ml <= mr else print(0)
### BUGGY CODE ###

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

#index,h
pp =[]
pm = []
mp = []
mm = []
for i in range(N):
    pp.append(i + A[i])
    pm.append( i - A[i])
    mp.append(-i + A[i])
    mm.append(-i - A[i])
count = 0
for i in range(N):
    count += pp.count(pm[i])
    #count += pm.count(pp[i])
print(count)

### FIXED CODE ###

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

#index,h
pp =[]
pm = []
all_set = set()
for i in range(N):

    pp.append(i + A[i])
    pm.append( i - A[i])

count = 0
c = collections.Counter(pp)
#print(c)
for i in range(N):
    count += c[pm[i]] 
    #print(c[pm[i]])

    #count += pp.count(pm[i])
    #count += pm.count(pp[i])

print(count)
### BUGGY CODE ###

n = int(input())
S = list(map(int, input().split()))
b=[]
for i in range(n):
    b.append(S[i])
    b=b[::-1]
print(*b, sep=" ")

### FIXED CODE ###

n = int(input())
S = list(map(int, input().split()))
S=S[::-1]
x=S[::2]
y=S[1::2]
b=x+y[::-1]
print(*b, sep=" ")
### BUGGY CODE ###

# C
n, q = map(int, input().split())
s = str(input())
s_flag = [0] * n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        s_flag[i] = 1
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = sum(s_flag[l:r])
    if s_flag[r:r+1] == 1:
        ans -=1
    print(ans)

### FIXED CODE ###

# C
n, q = map(int, input().split())
s = str(input())
s_flag = [0] * n
v = 0
for i in range(n-1):
    if s[i:i+2] == 'AC':
        v += 1
    s_flag[i+1] = v

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = s_flag[r] - s_flag[l]
    print(ans)
### BUGGY CODE ###

n = int(input())
strs = list()
for _ in range(n):
    strs.append(sorted(list(input())))

total = 0
for i in range(n):
    for j in range(i + 1, n):
        if strs[i] == strs[j]:
            total += 1
print(total)


### FIXED CODE ###

n = int(input())
d = {}

for _ in range(n):
    s = ''.join(sorted(input()))
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

ans = 0
for k, v in d.items():
    ans += (v * (v - 1)) / 2

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

MOD=10**9+7

N=int(input())
xlist=list(map(int,input().split()))

fact_nm1=1
for i in range(1,N):
  fact_nm1*=i
  fact_nm1%=MOD
#print(fact_nm1)

answer=0
for i in range(N-1):
  for j in range(i+1,N-1):
    ji_inv=pow(j-i,MOD-2,MOD)
    ji1_inv=pow(j-i+1,MOD-2,MOD)
    term=(fact_nm1*ji_inv*ji1_inv)%MOD
    answer+=term*(xlist[j]-xlist[i])
    answer%=MOD    
    #print(i,j,term)
  
  ni_inv=pow(N-1-i,MOD-2,MOD)
  term=(fact_nm1*ni_inv)%MOD
  answer+=term*(xlist[N-1]-xlist[i])
  answer%=MOD
  #print(i,N-1,term)
  
print(answer)

### FIXED CODE ###

MOD=10**9+7
N=int(input())
xlist=list(map(int,input().split()))

fact_nm1=1
for i in range(1,N):
  fact_nm1*=i
  fact_nm1%=MOD
#print(fact_nm1)

answer_bunshi=0
answer_bumbo=1
inv_bunshi=0
inv_bumbo=1
for i in range(1,N):  
  inv_bunshi=(i*inv_bunshi+inv_bumbo)%MOD
  inv_bumbo=(inv_bumbo*i)%MOD
  #print(inv_bunshi,inv_bumbo)
  
  xdiff=xlist[i]-xlist[i-1]
  term_bunshi=(xdiff*inv_bunshi)%MOD
  answer_bunshi=(answer_bunshi*inv_bumbo+term_bunshi*answer_bumbo)%MOD
  answer_bumbo=(answer_bumbo*inv_bumbo)%MOD
#print(answer_bunshi,answer_bumbo)

answer_bunshi=(answer_bunshi*fact_nm1)%MOD
answer=answer_bunshi*pow(answer_bumbo,MOD-2,MOD)
answer%=MOD
print(answer)
### BUGGY CODE ###

#coding=UTF-8

def turn_check(zikan,direct,around):
    nokori_naka=zikan
    for idx in range(0,N,1):
        rem_hp=max(HP[idx]-around*zikan,0)
        myon= rem_hp//(direct-around) + (0 if rem_hp%(direct-around)==0 else 1)
        
        nokori_naka=nokori_naka-myon
        if nokori_naka < 0:
            return False

    return True


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
A=int(hyo[1])
B=int(hyo[2])

HP=[]
for idx in range(0,N,1):
    HP.append(int(input()))

kagen=max(HP)// B + 1
tansaku=kagen//2
while True:
    if turn_check(tansaku,A,B):
        kagen=tansaku
        tansaku=kagen//2
    else:
        if tansaku + 1 == kagen: #丁度境目を見付けたら
            break
        else:
            tansaku=(tansaku+kagen)//2

print(kagen)


### FIXED CODE ###

#coding=UTF-8
myon_chache={}
def turn_check(zikan,direct,around):
    nokori_naka=zikan
    for idx in range(0,N,1):
        rem_hp=kirei_HP[idx]-around*zikan
        if rem_hp > 0:
            if rem_hp in myon_chache:
                myon=myon_chache[rem_hp]
            else:
                myon= rem_hp//(direct-around) + (0 if rem_hp%(direct-around)==0 else 1)
                myon_chache[rem_hp]=myon
        
            nokori_naka=nokori_naka-myon
            if nokori_naka < 0:
                return False
        else: #以降も周辺攻撃のみで倒せる
            return True

    return True


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
A=int(hyo[1])
B=int(hyo[2])

HP=[]
for idx in range(0,N,1):
    HP.append(int(input()))

kirei_HP=sorted(HP,reverse=True)
dmg_mean= B
kagen=kirei_HP[0]// dmg_mean + 1
tansaku=kagen//2
ite=0
dame_jogen=0
while True:
    ite=ite+1
    if turn_check(tansaku,A,B):
        kagen=tansaku
        tansaku=(kagen+dame_jogen)//2
    else:
        if tansaku + 1 == kagen: #丁度境目を見付けたら
            break
        else:
            dame_jogen=tansaku
            tansaku=(tansaku+kagen)//2

#print(ite)
print(kagen)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N = int(input())
L = list(map(int, input().split()))
ans = 1

for n in range(N):
 ans = L[n]*ans

print(ans) if ans <= 1000000000000000000 else print(-1)

### FIXED CODE ###

# coding: utf-8
# Your code here!
N = int(input())
L = list(map(int, input().split()))
ans = 1

for n in range(N):
 ans = L[n]*ans
 if ans >= 1000000000000000001: ans = -1
 if ans == -1: break

for n in range(N):
 if L[n] == 0: ans = 0
print(ans)
### BUGGY CODE ###

import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
print(min(dp[h:]))


### FIXED CODE ###

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])