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=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 ###

n = int(input())
a = input().split()
a = [int(m) for m in a]
k = 1
i = 0
t = a[0]
count = 1
p = 0
while i < n:
    if i != 0:
        t -= a[i - 1]
        if p == 1:
            count += k - i + 1
        else:
            count += k - i
    if p != 1:
        for j in range(k, n):
            if t + a[j] == t ^ a[j]:
                t += a[j]
                count += 1
                if j == n - 1:
                    k = j
                    p = 1
                    i += 1
            else:
                k = j
                i += 1
                break
    else:
        i += 1

print(count)

### FIXED CODE ###

n = int(input())
a = input().split()
a = [int(m) for m in a]
k = 1
i = 0
t = a[0]
count = 1
p = 0
if n != 1:
    while i < n:
        if i != 0:
            t -= a[i - 1]
            if p == 1:
                count += k - i + 1
            else:
                count += k - i
        if p != 1:
            for j in range(k, n):
                if t + a[j] == t ^ a[j]:
                    t += a[j]
                    count += 1
                    if j == n - 1:
                        k = j
                        p = 1
                        i += 1
                else:
                    k = j
                    i += 1
                    break
        else:
            i += 1
    print(count)
else:
    print(count)
### BUGGY CODE ###

#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

from math import gcd
import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
for i in range(2,LIMIT+1):
    if minPrime[i] == 0:
        minPrime[i] = i
        for j in range(i+i,LIMIT+1,i):
            if minPrime[j] == 0:
                minPrime[j] = i

# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while 1 != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

for i in range(N):
    acc = gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    #f = set(factrial(e))
    f = factrial(e)
    if p & f != set():
        pairwise = False
    p = p | f

if pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")
# for s:
#     acc = math.gcd(acc,a[i])
# if acc != 1:
#     print("not coprime")
#     exit()
# print("pairwise coprime")
# for i in range(N):
#     for j in range(i+1,N):
#         b = gcd(a[i],a[j])
#         if b != 1:
#             print("setwise coprime")
#             exit()
# if pairwise == True:
#     print("pairwise coprime")
# else:
#     print("not coprime")


### FIXED CODE ###

import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)
 
        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i
 
    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num
 
    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret
 
sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])
 
for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)

  for i in range(N):
    first_1_count = base_1_count
    if X[i] == "1":
      first_1_count -= 1
      Xi = X_int - 2**(N-i-1)
    else:
      first_1_count += 1
      Xi = X_int + 2**(N-i-1)
    count = 0
    num_of_1 = first_1_count
    while Xi != 0:
      Xi = Xi % num_of_1
      num_of_1 = bin(Xi).count("1")
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

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

N = int(input())
se = []
for i in range(N):
  Si = input()
  if Si not in se:
    se.append(Si)
print(len(se))

### FIXED CODE ###

N = int(input())
se = {-1}
for i in range(N):
  se.add(input())
print(len(se)-1)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import dijkstra, shortest_path
from scipy.sparse import lil_matrix, csr_matrix
K = int(input())

D = lil_matrix((K, K))
for i in range(K-1):
    D[i, i + 1] = 1
    D[i, (i * 10) % K] = 10**(-8)
D[K - 1, 0] = 1
D[K - 1, ((K - 1) * 10) % K] = 10**(-8)

d = dijkstra(D.tocsr(), directed=True, indices=1)
print(int(d[0]) + 1)

### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra, shortest_path
from scipy.sparse import csr_matrix
K = int(input())

class Graph(object):

    def __init__(self, K):
        self.K = K
        self.weights = {}

    def add_edge(self, node1, node2, weight):
        if (node1, node2) in self.weights:
            self.weights[(node1, node2)] = min(self.weights[(node1, node2)], weight)
        else:
            self.weights[(node1, node2)] = weight

    def get_csr_matrix(self):
        n1, n2, w = [], [], []
        for (node1, node2), weight in self.weights.items():
            n1.append(node1)
            n2.append(node2)
            w.append(weight)
        return csr_matrix((w, (n1, n2)), shape=(self.K, self.K))

g = Graph(K)

for i in range(K - 1):
    g.add_edge(i, i + 1, 1)
    g.add_edge(i, (i * 10) % K, 10**(-16))

g.add_edge(K - 1, 0, 1)
g.add_edge(K - 1, ((K - 1) * 10) % K, 10**(-16))
d = dijkstra(g.get_csr_matrix(), directed=True, indices=1)
print(int(d[0]) + 1)
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline


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


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    B[i] = lcm // fractions.gcd(lcm, A[i])
    lcm = B[i] * A[i]

ans = 0
for i in range(N):
    ans += (lcm // A[i]) % mod
    ans %= mod

print(ans)


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    lcm = (lcm // fractions.gcd(lcm, A[i])) * A[i]

ans = 0

lcm %= mod
for i in range(N):
    ans += (lcm * inv_t[A[i]]) % mod
    ans %= mod

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

from itertools import product

N = int(input())
S = input()
S = [int(s) for s in S]


res = 0
for q in product(range(10), repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                res += 1
                break
            else:
                i+=1
print (res)

### FIXED CODE ###

from itertools import product

N = int(input())
S = input()
S = [int(s) for s in S]


res = 0
for q in product(range(10), repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                res += 1
                break
            else:
                i+=1
print (res)
### BUGGY CODE ###

import sys

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

ans = 1


for a in A:
    if a == 0:
        print(0)
        sys.exit()
    ans *= a

if 10**18 < ans:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys

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

ans = 1

for a in A:
    if a == 0:
        print(0)
        sys.exit()

for a in sorted(A, reverse=True):
    ans *= a
    if 10**18 < ans:
        print(-1)
        sys.exit()


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

N = int(input())
a = list(map(int,input().split()))
SUM = sum(a)
MIN = 10**10
for i in range(N-1):
    suma = 0
    for j in range(i+1):
        suma+=a[j]
    kari = abs(SUM-2*suma)
    MIN = min(MIN,kari)
print(MIN)

### FIXED CODE ###

def solve(N,a):
    suma = 0
    SUM = sum(a)
    MIN = 10**15
    for i in a[:(N-1)]:
        suma+=i
        MIN = min(MIN,abs(2*suma-SUM))
    return abs(MIN)

if __name__ == "__main__":
    N = int(input())
    a = list(map(int,input().split()))
    print(solve(N,a))
### BUGGY CODE ###

import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 2019

    S = input()[::-1]
    N = len(S)

    if N < 4:
        print(0)
        return

    R = [0] * 2019
    R[0] = 1 # '' の分
    t = 0
    b = 1
    for c in S:
        t += int(c) * b
        t %= 2019
        R[t] += 1
        b *= 10
    ans = 0
    for r in R:
        ans += r*(r-1)//2
    print(ans)
    




    

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 2019

    S = input()[::-1]
    N = len(S)

    if N < 4:
        print(0)
        return

    R = [0] * 2019
    R[0] = 1 # '' の分
    t = 0
    b = 1
    for c in S:
        t += int(c) * b
        t %= 2019
        R[t] += 1
        b *= 10
        b %= 2019
    ans = 0
    for r in R:
        ans += r*(r-1)//2
    print(ans)
    




    

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

import math
import collections


nc2_memo = {}
def nc2(n):
    if n <= 1:
        return 0
    if n in nc2_memo:
        return nc2_memo[n]
    r = math.factorial(n)//(2*math.factorial(n-2))
    nc2_memo[n] = r
    return r


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

cnt = collections.Counter(a)
ans = {}
for key1 in cnt.keys():
    ans[key1] = sum(nc2(value) if key1 != key2 else nc2(value-1) for key2, value in cnt.items())
for v in a:
    print(ans[v])


### FIXED CODE ###

import math
import collections


def nc2(n):
    if n <= 1:
        return 0
    return math.factorial(n)//(2*math.factorial(n-2))


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

cnt = collections.Counter(a)
each_ans = {}
for key, value in cnt.items():
    t = nc2(value)
    each_ans[key] = (t, t-value+1)
all_sum = sum(value[0] for _, value in each_ans.items())
ans = {}
for key in cnt.keys():
    ans[key] = all_sum - each_ans[key][0] + each_ans[key][1]
for i in a:
    print(ans[i])
### BUGGY CODE ###

n = int(input())
x = input()

val = 0
rui = 1
mod = 0
for i in range(n):
    val += int(x[n-1-i])*rui
    rui *= 2
    if int(x[n-1-i]) == 1:
        mod += 1

rui = 1
ans_li = []
    
for i in range(n):
    t_v = val
    t_m = mod
    if int(x[n-1-i]) == 1:
        t_v -= rui
        t_m -= 1
    else:
        t_v += rui
        t_m += 1
    rui *= 2
    ans = 0
    while t_v != 0:
        t_v %= t_m
        ans += 1
        t_m = bin(t_v).count("1")
    ans_li.append(ans)
    #print(ans_li)

#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])


### FIXED CODE ###

def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    
    t_v_p = val % (mod+1)
    if mod == 1:
        t_v_m = 0
    else:
        t_v_m = val % (mod-1)
        
    for i in range(n):
        ans = 0
        #t_v = val
        #t_m = mod
        if int(x[i]) == 1:
            if mod == 1:
                t_v = 0
            else:
                t_v = t_v_m
                t_v -= pow(2,(n-1-i),mod-1)
                #t_v -= rui % (mod-1)
                t_v %= (mod-1)
                ans += 1
                #t_m -= 1
        else:
            t_v = t_v_p
            t_v += pow(2,(n-1-i),mod+1)
            #print(t_v,rui)
            #t_v += rui % (mod+1)
            t_v %= (mod+1)
            ans += 1
            #t_m += 1
        rui //= 2
        #print(t_v,mod)
        #while t_v != 0:
        """
        if t_v != 0:
            if int(x[i]) == 1:
                if mod == 1:
                    t_v = 0
                else:
                    t_v %= mod-1
            else:
                t_v %= mod + 1
            #t_v %= t_m
            ans += 1
        """
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

def num_to_coo(p):
    h, w = divmod(p, W)
    h += 1
    w += 1
    return h, w

def bfs(s):
    cost = [-1] * (H * W)
    q = deque()
    q.append((s, 0))
    while q:
        p, c = q.popleft()
        cost[p] = c
        h, w = num_to_coo(p)
        if (field[h - 1][w] == '.') and p - W >= 0 and (cost[p - W] == -1):
            q.append((p - W, c + 1))
        if (field[h + 1][w] == '.') and p + W < H * W and (cost[p + W] == -1):
            q.append((p + W, c + 1))
        if (field[h][w - 1] == '.') and p - 1 >= 0 and (cost[p - 1] == -1):
            q.append((p - 1, c + 1))
        if (field[h][w + 1] == '.') and p + 1 < H * W and (cost[p + 1] == -1):
            q.append((p + 1, c + 1))
    return c

ans = -1
for s in range(H * W):
    h, w = num_to_coo(s)
    if field[h][w] == '.':
        ans = max(ans, bfs(s))
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
field = ''
for i in range(H):
    field += input()

def bfs(start):
    dist = [0] * (H * W)
    q = deque([start])
    while q:
        p = q.popleft()
        c = dist[p] + 1
        if p - W != start and p - W >= 0 and field[p - W] == '.' and dist[p - W] == 0:
            dist[p - W] = c
            q.append(p - W)
        if p + W != start and p + W < H * W and field[p + W] == '.' and dist[p + W] == 0:
            dist[p + W] = c
            q.append(p + W)
        if p - 1 != start and p - 1 >= 0 and field[p - 1] == '.' and dist[p - 1] == 0 and p % W != 0:
            dist[p - 1] = c
            q.append(p - 1)
        if p + 1 != start and p + 1 < H * W and field[p + 1] == '.' and dist[p + 1] == 0 and p % W != W - 1:
            dist[p + 1] = c
            q.append(p + 1)
    return dist[p]

ans = 0
for s in range(H * W):
    if field[s] == '.':
        ans = max(ans, bfs(s))
print(ans)
### BUGGY CODE ###

A=list(map(int,input().split()))
sum=2019
for i in range(int(A[1])):
    if i>=A[0]:
        for t in range (int(A[1])+1):
            if t>i:
                if i*t%2019<=sum:
                    sum=i*t%2019
print(sum)

### FIXED CODE ###

l,r=list(map(int,input().split()))
f=True
C=2019
if (r-l)<2019:
    for i in range(l,r+1):
        if C==0:
            break
        for t in range(i+1,r+1):
            if t*i%2019<C:
                C=t*i%2019
                if C==0:
                    break
else:
    C=0
print(C)
### BUGGY CODE ###

n,m = map(int,input().split())
li = [0]*m
for i in range(m):
  li[i] = list(map(int,input().split()))

ans = 0
for i in range(1,n+1):
  cnt = 0
  for j in range(m):
    if li[j][0] <= i <= li[j][1]:
      cnt += 1
      continue
    else:
      break
  if cnt == m:
    ans += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())

lans = 1
rans = n
for i in range(m):
  l,r = map(int,input().split())
  lans = max(lans,l)
  rans = min(rans,r)
if lans <= rans:
  print(len(list(range(lans,rans+1))))
else:
  print(0)
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
mod = 10**9 + 7

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

ans = 0
for i in range(n):
    a[i] = bin(a[i])[2:].zfill(60)

for i in range(60):
    count = 0
    for j in range(n):
        count += 1 if a[j][i] == '1' else 0

    ans += (pow(2, 59-i, mod) * count * (n-count)) % mod

print(ans % mod)

### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
mod = 10**9 + 7

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

ans = 0
for i in range(n):
    a[i] = bin(a[i])[2:].zfill(60)

for i in range(60):
    count = 0
    for j in range(n):
        count += 1 if a[j][i] == '1' else 0

    ans += (pow(2, 59-i, mod) * count * (n-count)) % mod

print(ans % mod)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lrs = [map(int, input().split()) for _ in range(Q)]

for l, r in lrs:
    s = S[l-1:r]
    length = len(s)
    count = 0
    for i in range(length - 1):
        if s[i] == 'A' and s[i+1] == 'C':
            count += 1
    print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
lrs = [list(map(int, input().split())) for _ in range(Q)]

cs = [0] * N
s = 0
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        s += 1
    cs[i+1] = s 

for l, r in lrs:
    print(cs[r-1] - cs[l-1])
### BUGGY CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
a2=a.copy()
a2=np.array(a2)
mod=10**9+7
def f(n,i):
  if i==n-1:
    return
  for j in range(i+1,n):
    c=eucrid(a[i],a[j])
    a[j]//=c
    
def eucrid(a,b):
  a,b=max(a,b),min(a,b)
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b

for i in range(n):
  f(n,i)
m=1
for i in a:
  m = m * i
b=m//a2
ans=b.sum()%mod
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

def eucrid(a,b):
  a,b=max(a,b),min(a,b)
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b
m=a[0]
for i in range(n):
  m=m//eucrid(m,a[i])*a[i]
b=0
m=m%mod
for i in a:
  b+=m*pow(i,mod-2,mod)%mod
print(b%mod)
### BUGGY CODE ###

def inpl(): return [int(i) for i in input().split()]

def solve(n,S):
    Ctr = set([])
    for i in range(n+1):
        Ctr = Ctr | set([S[i]])
    Ans = {}
    for i in range(n+1):
        Ans[S[i]] = 0
    for i in range(n+1):
        Ans[S[i]] += 1
    
    ans = 0
    for i in Ctr:
        ans += Ans[i] * (Ans[i] - 1) // 2
    return(ans)

N,M = inpl()
H = inpl()

SumH = [0]
for i in range(N):
    SumH.append((SumH[-1] + H[i]) % M)

print(solve(N,SumH))

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]

N,M = inpl()
H = {0: 1}
k = 0
ans = 0
for i in inpl():
    k += i
    t = k % M
    if t not in H:
        H[t] = 0
    H[t] += 1
    
for i in H.values():
   ans += i * (i - 1) // 2

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

import sys 

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
A.sort()
# print(A)

ans = 0 
exists = set()
for i in range(N):
    for e in exists:
        if A[i] % e == 0:
            break
    else:
        if i + 1 == N or A[i] != A[i+1]:
            ans += 1
    exists.add(A[i])

print(ans)

### FIXED CODE ###

import sys 

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
A.sort()

max_a = max(A)
counts = [0 for _ in range(max_a + 1)]
ans = 0

for a in A:
    counts[a] += 1

for a in A:
    if counts[a] == 1:
        ans += 1
    n = 1
    while n * a <= max_a:
        counts[n * a] += 2
        n += 1

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

N, K, Q = map(int, input().split())
P = [K]*N

for i in range(Q):
    w = int(input())
    P = list(map(lambda x: x-1, P))
    P[w-1] += 1

for j in P:
    if j > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
P = [K-Q]*N

for i in range(Q):
    w = int(input())
    P[w-1] += 1

for j in P:
    if j > 0:
        print("Yes")
    else:
        print("No")