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

def dw_heap(A,i,length):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if l < length and A[l] > A[largest]: largest = l
        if r < length and A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest


def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2


def extract(A,last):
    max_item = A[1]
    A[1],A[last] = A[last],A[1]
    dw_heap(A,1,last)
    return max_item


def build_heap(A,length):
    for i in range(length//2,0,-1): dw_heap(A,i,length)


if __name__=='__main__':
    hp = [None]*(2*10**6)
    hp[0] = 2*10**9 + 1
    i = 1
    j = -1 
    while True:
        op = input() 
        if   op[0] != 'i': break
        hp[i] = int(op[7:])
        i += 1
    if op[2] != 'd': build_heap(hp,i)
    while True:
        if   op[2] == 'd': break
        if   op[0] == 'i':
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        else:
            hp[j] = extract(hp,i-1)
            i -= 1
            j -= 1
        op = input() 
    print(*hp[:j:-1],sep='\n')

### FIXED CODE ###

from sys import stdin

def dw_heap(A,i):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if A[l] > A[largest]: largest = l
        if A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest

def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2

if __name__=='__main__':
    hp = [-1]*(4000000)
    hp[0] = 2000000001
    i = 1
    j = -1 
    for op in stdin:
        if op[0] == 'i':# insert
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        elif op[1] == 'x':# extract
            hp[j],hp[1],hp[i-1] = hp[1],hp[i-1],-1
            dw_heap(hp,1)
            i -= 1
            j -= 1
        else:# end
            break
    print(*hp[:j:-1],sep='\n')
### BUGGY CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)%M*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

### FIXED CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)
### BUGGY CODE ###

s=input()
counter=0
while "BW" in s:
    s.replace("BW","WB")
    counter+=1
print(counter)
  

### FIXED CODE ###

S = input()
ans = 0
count = 0
for i in range(len(S)-1, -1, -1):
    if S[i] == "B":
        ans += len(S)-i-1-count
        count += 1
 
print(ans)
### BUGGY CODE ###

N=int(input())
P=list(map(int, input().split()))
a=1
b=0
for i in P:
	M=min(P[:a])
	if M==i:
		b+=1
	a+=1
print(b)

### FIXED CODE ###

_ = input()
p = list(map(int, input().split()))
m = float("inf")
c = 0
for i in p:
  c += i <= m
  m = min(m, i)
print(c)
### BUGGY CODE ###

import heapq
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
f.sort()
f.reverse()
l=[]
for i in range(n):
  l.append([-a[i]*f[i],-f[i],a[i]])
heapq.heapify(l)
for i in range(k):
  x=heapq.heappop(l)
  heapq.heappush(l,[-(max(x[2]-1,0))*(-x[1]),x[1],max(x[2]-1,0)])
l=list(l)
L=[]
for i in range(n):
  L.append(l[i][0])
print(-min(L))

### FIXED CODE ###

import heapq
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
f.sort()
f.reverse()
l=0;r=max(a)*max(f)
sum=sum(a)
while abs(l-r)>1:
  x=(l+r)//2
  ct=0
  for i in range(n):
    ct+=max(a[i]-(x//f[i]),0)
  if ct<=k:
    r=x
  else:
    l=x+1
x=l
ct=0
for i in range(n):
  ct+=max(a[i]-(x//f[i]),0)
if ct<=k:
  print(l)
else:
  print(r)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
maze = []
def mazecal(hs,ws):
    calmaze = [[-1 for _ in range(w)] for _ in range(h)]
    step = 0
    que = deque([[hs,ws,step]])
    while len(que)!=0:
        cur = que.popleft()
        #print('cur',cur)
        calmaze[cur[0]][cur[1]] = cur[2]
        if cur[0]>0   and maze[cur[0]-1][cur[1]]==0:
            if calmaze[cur[0]-1][cur[1]] ==-1 or calmaze[cur[0]-1][cur[1]] > cur[2]+1:
                 que.append([cur[0]-1,cur[1],  cur[2]+1])
        if cur[0]<h-1 and maze[cur[0]+1][cur[1]]==0:
            if calmaze[cur[0]+1][cur[1]] ==-1 or calmaze[cur[0]+1][cur[1]] > cur[2]+1:
                que.append([cur[0]+1,cur[1],  cur[2]+1])
        if cur[1]>0   and maze[cur[0]][cur[1]-1]==0:
            if calmaze[cur[0]][cur[1]-1] ==-1 or calmaze[cur[0]][cur[1]-1] > cur[2]+1:
                que.append([cur[0]  ,cur[1]-1,cur[2]+1])
        if cur[1]<w-1 and maze[cur[0]][cur[1]+1]==0:
            if calmaze[cur[0]][cur[1]+1] ==-1 or calmaze[cur[0]][cur[1]+1] > cur[2]+1:
                que.append([cur[0]  ,cur[1]+1,cur[2]+1])        
    smax = 0
    for i in range(h):smax = max(smax,max(calmaze[i]))
    return smax

for i in range(h):maze.append([0 if c=='.' else 1 for c in input()])
gmax = 0
for i in range(h):
    for j in range(w):
        if maze[i][j]==0:gmax = max(gmax,mazecal(i,j))
print(gmax)

### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
maze = []
def mazecal(hs,ws):
    calmaze = [[-1 for _ in range(w)] for _ in range(h)]
    que = deque([[hs,ws,0]])
    smax = 0
    while len(que)!=0:
        cur = que.popleft()
        calmaze[cur[0]][cur[1]] = cur[2]
        smax = max(smax,cur[2])
        if cur[0]>0   and maze[cur[0]-1][cur[1]]==0:
            if calmaze[cur[0]-1][cur[1]] ==-1 or calmaze[cur[0]-1][cur[1]] > cur[2]+1:
                calmaze[cur[0]-1][cur[1]] = cur[2]+1
                que.append([cur[0]-1,cur[1],  cur[2]+1])
        if cur[0]<h-1 and maze[cur[0]+1][cur[1]]==0:
            if calmaze[cur[0]+1][cur[1]] ==-1 or calmaze[cur[0]+1][cur[1]] > cur[2]+1:
                calmaze[cur[0]+1][cur[1]] = cur[2]+1
                que.append([cur[0]+1,cur[1],  cur[2]+1])
        if cur[1]>0   and maze[cur[0]][cur[1]-1]==0:
            if calmaze[cur[0]][cur[1]-1] ==-1 or calmaze[cur[0]][cur[1]-1] > cur[2]+1:
                calmaze[cur[0]][cur[1]-1] = cur[2]+1
                que.append([cur[0]  ,cur[1]-1,cur[2]+1])
        if cur[1]<w-1 and maze[cur[0]][cur[1]+1]==0:
            if calmaze[cur[0]][cur[1]+1] ==-1 or calmaze[cur[0]][cur[1]+1] > cur[2]+1:
                calmaze[cur[0]][cur[1]+1] = cur[2]+1
                que.append([cur[0]  ,cur[1]+1,cur[2]+1])
    return smax

for i in range(h):maze.append([0 if c=='.' else 1 for c in input()])
gmax = 0
for i in range(h):
    for j in range(w):
        if maze[i][j]==0:gmax = max(gmax,mazecal(i,j))
print(gmax)
### BUGGY CODE ###

from itertools import permutations
n, l = map(int, input().split(' '))
lst = []
for _ in range(n):
  lst.append(input())
all_str = list(permutations(lst))
all_str = [''.join(x) for x in all_str]
print(min(all_str))

### FIXED CODE ###

n, l = map(int, input().split(' '))
lst = []
for _ in range(n):
    lst.append(input())
all_str = sorted(lst)
print(''.join(all_str))
### BUGGY CODE ###

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

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = dict()
for x, s, t in roadworks:
    for i in range(s, t+1):
        i = max(0, i-x)
        stops[i] = x
#print(stops)
for d in D:
    if d+1 in stops:
        print(stops[d+1])
    else:
        print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)
### BUGGY CODE ###

# ARC081c
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    from collections import Counter

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

    mg = 0
    for i in a:
        if a.count(i) > 3 and mg != i:
            if mg == 0:
                print(i**2)
                exit(0)
            print(mg*i)
            exit(0)
        if a.count(i) > 1 and mg != i:
            if mg == 0:
                mg = i
                continue
            print(mg*i)
            exit(0)
    print(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# ARC081c
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    from collections import Counter
    import heapq

    n = int(input())

    def fun(i):
        return -int(i)

    a = list(map(fun, input().split()))
    heapq.heapify(a)

    b = []
    heapq.heapify(b)
    ln = 0
    cou = 0
    mn = 0
    while(len(a) > 0):
        i = -heapq.heappop(a)
        # print(i)
        if ln != i:
            ln = i
            cou = 0
        cou += 1
        if cou > 1:
            heapq.heappush(b, -i)
            cou = 0
    try:
        print(heapq.heappop(b)*heapq.heappop(b))
    except:
        print(0)


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

#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, L: "List[int]"):
    combi = itertools.combinations(L,3)
    answer = 0
    for c in combi:
        if c[0]<c[1]+c[2] and c[1]<c[0]+c[2] and c[2]<c[1]+c[0]:
            answer += 1
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

def solve(N: int, L: "List[int]"):
    L.sort()
    answer = 0
    for i in range(N):
        for j in range(i+1,N):
            max_k = bisect.bisect_left(L,L[i]+L[j])
            answer += max_k-(j+1)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

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

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right
import numpy as np

n, d, a = map(int, input().split())
xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()
xh = np.array(xh)
xh = xh.T
x = xh[0][:]
h = xh[1][:]
l = 0
ret = 0
while l < n:
    xl = x[l]
    hl = h[l]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(x, xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    h[l:r] -= k * a
print(ret)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh = dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
ai = [0] * (n+1)
anow = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    anow += ai[l]
    hl -= a * anow
    if hl > 0:
        r = bisect_right(x, xl+2*d)
        k = (hl+(a-1))//a
        ret += k
        anow += k
        ai[r] -= k
    l += 1
print(ret)
### BUGGY CODE ###

# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(input().strip())
getl = lambda: input().strip()
gets = lambda: list(map(int, input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in range(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[H:]))


### FIXED CODE ###

# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur / a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in xrange(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print min(dp[H:])
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int,input().split())))
bit = []
ans = 0
mod = 10**9+7
# for i in a:
#     cnt = 1
#     while i:
#         bit[-cnt] += i%2
#         i //= 2
#         cnt += 1
for i in range(60):
    bit.append(sum(a&1))
    a >>= 1
# print(bit)
for i in range(60):
    ans += ((n-bit[i])*bit[i]) % mod * pow(2,i,mod)
    ans %= mod
print(ans%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
bit = [0]*60
ans = 0
mod = 10**9+7
for i in a:
    cnt = 1
    while i:
        bit[-cnt] += i%2
        i //= 2
        cnt += 1
for i in range(60):
    ans += (n-bit[-1-i])*bit[-1-i] * (2**i) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

import bisect

def bs(x, key_func, arr):

	if len(arr) == 0 or arr == None:
		return -1

	n = len(arr)
	ini = 0
	fin = n - 1

	while ini < fin:
		m = (ini + fin) // 2
		if key_func(arr[m]) < x:
			ini = m + 1
		else:
			fin = m
	if fin == n - 1 and key_func(arr[fin]) < x:
		return n
	if key_func(arr[fin]) >= x:
		return max(0, fin - 1)
	return fin	

def main():
	N = int(input())	
	S = input()

	tb_i = {'BG': [], 'BR': [], 'GR': []}
	for i in range(N):
		for j in range(i + 1, N):
			if S[i] == S[j]:
				continue
			word = ''.join(list(sorted([S[i], S[j]])))
			tb_i[word].append((j, j - i))
	
	for key in tb_i:
		tb_i[key].sort(key=lambda x: x[0])
	
	rs = 0	
	for i in range(2, N):	
		word = None
		if S[i] == 'R':
			word = 'BG'
		if S[i] == 'G':
			word = 'BR'
		if S[i] == 'B':
			word = 'GR'

		idx = bs(i, lambda x: x[0], tb_i[word])
		if idx == len(tb_i[word]):
			idx -= 1	
		if idx == 0 and tb_i[word][0][0] >= i:
			idx -= 1
		for j in range(idx, -1, -1):
			if tb_i[word][j][1] == i - tb_i[word][j][0]:
				continue
			rs += 1
	print(rs)
	return 0 

main()


### FIXED CODE ###

import bisect

def main():
	N = int(input())	
	S = input()

	tb_pos = {'BG': None, 'BR': None, 'GR': None}
	for k in tb_pos:
		tb_pos[k] = [0] * (N + 1)
	
	rs = 0
	for i in range(N):
		for j in range(i + 1, N):
			if S[i] == S[j]:
				continue
			d = j - i
			c1, c2 = S[i], S[j]
			if c1 > c2:
				c1, c2 = c2, c1
			word = c1 + c2
			if j + d < N and S[j + d] not in word:
				rs -= 1
			tb_pos[word][j + 1] += 1 

	for i in range(1, N + 1):
		for k in tb_pos:
			tb_pos[k][i] += tb_pos[k][i - 1]
				
	for j in range(2, N):
		word = None
		if S[j] == 'B':
			word = 'GR'
		elif S[j] == 'G':
			word = 'BR'
		else:
			word = 'BG'
		
		rs += tb_pos[word][j + 1]

	print(rs)
	return 0 

main()
### BUGGY CODE ###

import functools
import operator
n = int(input())
a = list(map(int, input().split()))
ans = functools.reduce(operator.mul, a)
print(ans if ans <= 10**18 else '-1')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [i for i in a if i != 1]
ans = 1
if len(b) < 100:
    for i in range(len(b)):
        ans *= b[i]
else:
    ans = 10**18+1
if 0 in b:
    ans = 0
print(ans if ans <= 10**18 else '-1')
### BUGGY CODE ###

def main():
    import sys
    import heapq
    input=sys.stdin.readline
    N,M=map(int,input().split())
    A=list(map(lambda x:-1*int(x),input().split()))
    for i in range(M):
        heapq.heapify(A)
        if i==0:
            temp = -(heapq.heappop(A))//2
        else:
            heapq.heappush(A,-temp)
            temp = -(heapq.heappop(A))//2
    print(-sum(A)+temp)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import heapq
    input=sys.stdin.readline
    N,M=map(int,input().split())
    A=list(map(lambda x:-1*int(x),input().split()))
    heapq.heapify(A)
    for i in range(M):
        if i==0:
            temp = -(heapq.heappop(A))//2
        else:
            heapq.heappush(A,-temp)
            temp = -(heapq.heappop(A))//2
    print(-sum(A)+temp)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        #print(i,j)
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    #print(DPLIST)
    #print()
            

print(DPLIST[0][N-1][0])

### FIXED CODE ###

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

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        #print(i,j)
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    #print(DPLIST)
    #print()
            

print(DPLIST[0][N-1][0])
### BUGGY CODE ###

n, q = map(int, input().split())
arr = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    arr[a-1][b-1] += 1
    
ans = [0 for _ in range(n)] 

for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
    
for i, c in enumerate(ans):
    for j, x in enumerate(arr[i]):
        if arr[i][j]==1:
            ans[j] += c
            
print(*ans)
            
        

### FIXED CODE ###

n, q = map(int, input().split())
arr = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    arr[a-1].append(b)
    
ans = [0 for _ in range(n)] 

for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
    
for i, c in enumerate(ans):
    for j in arr[i]:
        ans[j-1] += c
            
print(*ans)
### BUGGY CODE ###

import math
import collections
import numpy as np
n, m = map(int, input().split())

factor = []
tmp = int(np.sqrt(m)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
c = collections.Counter(factor)
num = list(c.values())

ans = 1
for i in range(len(num)):
    ans *= math.factorial(num[i] + n - 1) // (math.factorial(n - 1) * math.factorial(num[i]))
    ans %= 1000000007
print(ans)

### FIXED CODE ###

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

factor = []
tmp = int(m ** (1/2)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
num = list(collections.Counter(factor).most_common())

def comb(n, r):
    tmp = 1
    for i in range(r):
        tmp *= n - i
    for i in range(r):
        tmp //= r - i
    return tmp

ans = 1
for x in num:
    ans *= (comb(x[1] + n - 1, x[1]) % 1000000007)
    ans %= 1000000007
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
ans = 0
 
for i in range(N-1):
  ans += A[i]*sum(A[i+1:N])
  
mod = 10**9 + 7
print(ans%mod)

### FIXED CODE ###

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

ans = 0
res = [0] * N
res[0] = A[0]
for i in range(len(A)-1):
    res[i+1] = res[i] + A[i+1]

sum_A = sum(A)

for i in range(N-1):
  ans += A[i]*(sum_A-res[i])
  
mod = 10**9 + 7
print(ans%mod)
### BUGGY CODE ###

S = input()
Q = int(input())
inversion_flg = False
# L = [input().split() for _ in range(Q)]

for i in range(Q):
    L = input().split()
    if L[0] == '1':
        if inversion_flg:
            inversion_flg = False
        else:
            inversion_flg = True
    if L[0] == '2':
        if not inversion_flg:
            if L[1] == '1':
                S = L[2] + S
            else:
                S = S + L[2]
        else:
            if L[1] == '2':
                S = L[2] + S
            else:
                S = S + L[2]



# print(L)
if not inversion_flg: 
    print(S)
else:
    # S.reverse()
    S = S[::-1]
    print(S)

### FIXED CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)
### BUGGY CODE ###

import numpy as np

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

asum = sum(Alist)
cut = []
length = []
for n in range(N):
    tmp = K * Alist[n] / asum
    cut.append(int(tmp) + 1)
    length.append(Alist[n] / (int(tmp)+1))

amari = K - sum(cut) + N
length = np.array(length)

for _ in range(amari):
    max_idx = np.argmax(length)
    cut[max_idx] += 1
    length[max_idx] = Alist[max_idx] / cut[max_idx]

ans = max(length)

if ans%1>0:
    print(int(ans)+1)
else:
    print(int(ans))

### FIXED CODE ###

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

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

left = 0
right = max(Alist)

while right - left > 1:
    mid = (left + right) // 2
    
    cnt = 0
    for A in Alist:
        if A % mid == 0:
            cnt += (A // mid) - 1
        else:
            cnt += (A // mid)
    
    if cnt <= K:
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

n = int(input())
ns = list(map(int, input().split()))
ans = 0
from collections import Counter
c = Counter(ns)
dubbles = set([key for key, value in c.items() if value >= 2])
ns = sorted([i for i in ns if i not in dubbles])
n = len(ns)

def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

for i in range(n):
    flag = True
    for j in make_divisors(ns[i]):
        if j in dubbles:
            flag = False
            break
    if flag:
        ans += 1
        dubbles.add(ns[i])
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
c = Counter(ns)
ans = 0

l = [True] * (max(ns)+1)
for i in sorted(set(ns)):
    if l[i]:
        j = i*2
        while j < len(l):
            l[j] = False
            j += i

a = set([key for key, value in c.items() if value == 1])
for i in a:
    if l[i]:
        ans += 1
print(ans)