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

import sys; readline = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(1000000)

N, U, V = map(int, readline().split())
AB = [list(map(int, readline().split())) for i in range(N - 1)]

A = [a - 1 for a, b in AB]
B = [b - 1 for a, b in AB]

U, V = U - 1, V - 1

conn = {}
for a, b in zip(A, B):
    if not a in conn:
        conn[a] = []
    conn[a].append(b)

    if not b in conn:
        conn[b] = []
    conn[b].append(a)

t = [0 for i in range(N)]

def dfsU(u, parent, depth):
    t[u] = depth

    for _u in conn[u]:
        if _u != parent:
            dfsU(_u, u, depth + 1)

dfsU(V, -1, 0)

maxv = 0
maxu = U
def dfsV(v, parent, depth):
    global maxv
    global maxu
    if depth < t[v]:
        if t[v] > maxv:
            maxv = t[v]
            maxu = depth
        for _v in conn[v]:
            if _v != parent:
                dfsV(_v, v, depth + 1)

dfsV(U, -1, 0)
if (maxv - maxu) % 2 == 1:
    print(maxv - 1)
else:
    print(maxv - 1)

### FIXED CODE ###

import sys; readline = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(1000000)

N, U, V = map(int, readline().split())
AB = [list(map(int, readline().split())) for i in range(N - 1)]

A = [a - 1 for a, b in AB]
B = [b - 1 for a, b in AB]

U, V = U - 1, V - 1

conn = {}
for a, b in zip(A, B):
    if not a in conn:
        conn[a] = []
    conn[a].append(b)

    if not b in conn:
        conn[b] = []
    conn[b].append(a)

t = [0 for i in range(N)]

def dfsU(u, parent, depth):
    t[u] = depth

    for _u in conn[u]:
        if _u != parent:
            dfsU(_u, u, depth + 1)

dfsU(V, -1, 0)

maxv = 0
maxu = U
def dfsV(v, parent, depth):
    global maxv
    global maxu
    if depth < t[v]:
        if t[v] > maxv:
            maxv = t[v]
            maxu = depth
        for _v in conn[v]:
            if _v != parent:
                dfsV(_v, v, depth + 1)

dfsV(U, -1, 0)
if (maxv - maxu) % 2 == 1:
    print(maxv - 1)
else:
    print(maxv - 1)
### BUGGY CODE ###

n = int(input())
a = input().split()
a = [int(i) for i in a]

total = sum(a)
mid = int((total + 1) / 2)

over_idx = len(a) - 1
for i in range(1,len(a)):
    if sum(a[:i]) >= mid:
        over_idx = i - 1
        break

diff1 = abs(sum(a[:over_idx]) - sum(a[over_idx:]))
diff2 = abs(sum(a[:over_idx+1]) - sum(a[over_idx+1:]))

ans = min(diff1, diff2)

print(ans)


### FIXED CODE ###

n = int(input())
a = input().split()
a = [int(i) for i in a]

total = sum(a)
mid = int((total + 1) / 2)

temp_sum = 0
for i in range(len(a)):
    temp_sum += a[i]
    if temp_sum >= mid:
        over_idx = i
        break

diff1 = abs(sum(a[:over_idx]) - sum(a[over_idx:]))
diff2 = abs(sum(a[:over_idx+1]) - sum(a[over_idx+1:]))

ans = min(diff1, diff2)

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

#!/usr/bin/env python3
MOD = 998244353
n = int(input())
s = input()
cnt = [0] * 3
ans = 1
for i in range(3 * n):
    for j in range(3):
        if 'RGB'[j] == s[i]:
            cnt[j] += 1
            a = 0
            for i, x in enumerate(cnt):
                if x < cnt[a]:
                    a = i
            c = 0 + (a == 0)
            for i, x in enumerate(cnt):
                if x > cnt[c]:
                    c = i
            b = 3 - a - c
            if cnt[a] == 1:
                ans *= cnt[b]
                cnt = [x - 1 for x in cnt]
            elif b == j:
                ans *= cnt[c] - cnt[b] + 1
            ans %= MOD
f = [1] * (n + 1)
for i in range(1, n):
    f[i + 1] = (i + 1) * f[i]
print(ans * f[n])


### FIXED CODE ###

#!/usr/bin/env python3
MOD = 998244353
n = int(input())
s = input()
ans = 1
for i in range(n):
    ans *= i + 1
    ans %= MOD
cnt = [0] * 3
dic = {'R': 0, 'G': 1, 'B': 2}
for c in s:
    p = dic[c]
    m = min(cnt[p - 1], cnt[p - 2])
    if m > 0:
        ans *= m
        cnt[p - 1] -= 1
        cnt[p - 2] -= 1
    else:
        ans *= max(1, cnt[p - 1] + cnt[p - 2] - cnt[p])
        cnt[p] += 1
    ans %= MOD
print(ans)
### BUGGY CODE ###

N, K = (int(x) for x in input().split())
l = []
while 1:
    if not N % K:
        l.append(0)
        break
    N = abs(N - K)
    if N < K:
        if N in l:
            break
        l.append(N)
print(min(l))

### FIXED CODE ###

N,K = (int(x) for x in input().split())
a = N % K
print(min((a, K-a)))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
import collections 
for i in range(1,n+1):
    print(collections.Counter(a)[i])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
import collections 
c = collections.Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

import queue
import copy

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]

def movable(S,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S[px][py] == ".":
            return True
        else:
            return False
    else:
        return False

def bfs(S,sx,sy,gx,gy):
    S_dist = [[0 for _ in range(W)] for _ in range(H)]
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    while not q.empty():
        p = q.get()
        S[p[0]][p[1]] = "#"
        if p == (gx,gy):
            return S_dist[gx][gy]
        for vx,vy in vec:
            if movable(S,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if S[i//W][i%W] == "." and S[j//W][j%W] == ".":
            S_ = copy.deepcopy(S)
            ans = max(ans,bfs(S_,i//W,i%W,j//W,j%W))
print(ans)


### FIXED CODE ###

import queue
import copy

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
INF = H*W+1

def movable(S,S_dist,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S_dist[px][py] == INF and S[px][py] == ".":
            return True
    return False

def bfs(S,sx,sy):
    S_dist = [[INF for _ in range(W)] for _ in range(H)]
    #Sを直接いじれば訪問済みかどうか管理できるがそれだと毎回Sをリセットする必要がある
    #S_distのみ書き込みにすればS_distはローカルだからリセットが不要
    S_dist[sx][sy] = 0
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    ret = 0
    while not q.empty():
        p = q.get()
        ret = S_dist[p[0]][p[1]]
        for vx,vy in vec:
            if movable(S,S_dist,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        ans = max(ans,bfs(S,i//W,i%W))
print(ans)
### BUGGY CODE ###

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

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

d = {(W, 0)}

for w, v in items:
    tmp = set()
    for rw, rv in d:
        tmp.add((rw, rv))
        if rw >= w:
            tmp.add((rw-w, rv+v))
    d = tmp

d = {elm[1] for elm in d}

print(max(d))

### FIXED CODE ###

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

from collections import defaultdict

dp = defaultdict(int)

dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for k, val in list(dp.items()):
        if k+w <= W:
            dp[k+w] = max(dp[k+w], val+v)



print(max(dp.values()))
### BUGGY CODE ###

def str_to_map(str):
    Map = dict()
    for i in range(len(str)):
        c = str[i]
        if(c in Map):
            Map[c].add(i)
        else:
            Map[c] = {i}
    return Map


str1 = input()
str2 = input()

I1 = str_to_map(str1)
I2 = str_to_map(str2)

flag = True

for i in range(len(str1)):
    if(I1[str1[i]] != I2[str2[i]]):
        flag = False

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


### FIXED CODE ###

str1 = input()
str2 = input()

dict1 = dict()
ans = "Yes"

for i in range(len(str1)):
    if(str1[i] in dict1.keys()):
        if(dict1[str1[i]] != str2[i]):
            ans = "No"
    else:
        if(str2[i] in dict1.values()):
            ans = "No"
        dict1[str1[i]] = str2[i]

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

A, B, K = map(int, input().split())
list_num = [i for i in range(A, B+1, 1)]
list_num2 = []

for i in range(K):
    if len(list_num) == 0:
        break
    print(list_num[0])
    list_num.pop(0)

for i in range(K):
    if len(list_num) == 0:
        break
    list_num2.append(list_num[-1])
    list_num.pop(-1)
list_num2.sort()
for i in list_num2:
    print(i)


### FIXED CODE ###

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

list_num = []
a_max = -1
for i in range(K):
    if A+i <= B:
        a_max = A+i
        print(a_max)

tmp = K
for i in range(K):
    if B - tmp + 1 > a_max:
        print(B - tmp + 1)
    tmp -= 1
### BUGGY CODE ###

N = int(input())
S = (input())
from operator import itemgetter
from itertools import combinations
L = [int(i) for i in range(N)]
memo = []
for i in list(combinations(L,3)):
    memo.append(itemgetter(*i)(S))
print(len(set(memo)))

### FIXED CODE ###

N = int(input())
S = list((input()))
L = [str(i) for i in range(0,10)]
ALL =[]
for i in L:
    for j in L:
        for k in L:
            ALL.append(i+j+k)
cnt=0    
for a in ALL:
    try:
        
        I1 = S.index(a[0])
        I2 = S[I1+1:].index(a[1])+len(S[:I1+1])
        I3 = S[I2+1:].index(a[2])+len(S[:I2+1])

        if I1<I2 and I2<I3:
            cnt+=1
    except:
        continue
print(cnt)
### BUGGY CODE ###

[H,N]=[int(i) for i in input().split()]
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for n in range(N):
  [A[n],B[n]]=[int(i) for i in input().split()]
k=H+max(A)+1
DP=[100000000 for i in range(k)]
DP[0]=0
for n in range(N):
  for h in range(k):
    if h-A[n]>-1:
    	if DP[h-A[n]]+B[n]<DP[h]:DP[h]=DP[h-A[n]]+B[n]
print(min(DP[H:]))

### FIXED CODE ###

[H,N]=[int(i) for i in input().split()]
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for n in range(N):
  [A[n],B[n]]=[int(i) for i in input().split()]
k=H+max(A)+1
DP=[100000000 for i in range(k)]
DP[0]=0
for n in range(N):
  for h in range(k):
    if h-A[n]>-1:
    	if DP[h-A[n]]+B[n]<DP[h]:DP[h]=DP[h-A[n]]+B[n]
print(min(DP[H:]))
### BUGGY CODE ###

N = int(input())
A = [0] * N
for i in range(N):
	A[i] = int(input())

for j in range(1, N):
	if A[j] in A[: j]:
		A[A[: j].index(A[j])] = -1
		A[j] = -1


print(len([k for k in A if k != -1]))


### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(input()) for _ in range(N)]
c = Counter(A).values()

print(len([i for i in c if i % 2 == 1]))
### BUGGY CODE ###

L,R = map(int,input().split())
if (L-R >= 2019):
  print(0)
else:
  res = 2018
  for i in range(L,R):
    for j in range(i+1,R+1):
      res = min(res,(i*j)%2019)
print(res)


### FIXED CODE ###

L,R = map(int,input().split())
if (R-L >= 2019):
  print(0)
else:
  res = 2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      res = min(res,(i*j)%2019)
  print(res)
### BUGGY CODE ###

n, q = map(int, raw_input().split())
s = [0 for i in range(n)]
a = [map(int, raw_input().split()) for i in range(q)]
for r in a:
	s[r[0]-1] += r[1]
	mx = max(s)
	print s.index(mx)+1, mx

### FIXED CODE ###

n, q = map(int, raw_input().split())
s = [0]*n
mx,mxa = 0, 0
for i in range(q):
	a,v = map(int, raw_input().split())
	s[a-1] += v
	if v > 0:
		if s[a-1] > mx:
			mx = s[a-1]
			mxa = a-1
		elif s[a-1] == mx:
			if a-1 < mxa:
				mxa = a-1
	elif v < 0:
		if a-1 == mxa:
			mx = max(s)
			mxa = s.index(mx)
	print mxa+1,mx
### BUGGY CODE ###

s=(input())
n=len(s)

ans=0

s_ans=[int(s[i:j+1]) for i in range(n) for j in range(i+3,n)]

print(sum(map(lambda x:x%2019==0,s_ans)))

### FIXED CODE ###

S=input()[::-1]
l=[0]*2019
a=1
d=0

for s in S:
  d=d+int(s)*a
  l[d%2019]+=1
  a*=10
  a%=2019
  
ans=l[0]
for i in l:
  if i>=2:
    ans+=i*(i-1)//2
    
print(ans)
### BUGGY CODE ###

# ABC053B - A to Z String
s = list(input())
while s[0] != 'A':
    s.pop(0)
while s[-1] != 'Z':
    s.pop()
print(len(s))

### FIXED CODE ###

# ABC053B - A to Z String
s = list(input())
i = 0
while s[i] != "A":
    i += 1
j = 1
while s[-j] != "Z":
    j += 1
print(len(s) - i - j + 1)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
 
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x
z=lcm(A)
 
MOD=10**9+7
import numpy as np
A=np.array(A)
B=z//A
B%=MOD
print(np.sum(B)%MOD)

### FIXED CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))

cnt=0
for i in range(n):
  B=b[i]
  AA=np.searchsorted(a, B-0.1, side='right')
  CC=n-np.searchsorted(c, B+0.1)
  cnt+=AA*CC
print(cnt)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
#cnt=0
#for i in range(n):
 # B=b[i]
  #A=[a[i] for i in range(n) if a[i]<B]
  #C=[c[i] for i in range(n) if c[i]>B]
  #cnt+=len(A)*len(C)
#print(cnt)
cnt=0
#真ん中のパーツをまず考える
for i in range(n):
  B=b[i]
  if B<=a[0] or B>=c[-1]:
    continue
  #Bより小さいAの最大値のインデックスを探す
  i_small=0
  i_large=n-1
  while i_large-i_small>1:
    if a[(i_small+i_large)//2] <B:
      i_small=(i_small+i_large)//2
    else:
      i_large=(i_small+i_large)//2
 
  A=i_large
  if a[-1]<B:
    A+=1

  #Bより大きいCの最小値のインデックスを探す
  i_small=0
  i_large=n-1
  while i_large-i_small>1:
    if c[(i_small+i_large)//2] >B:
      i_large=(i_small+i_large)//2
    else:
      i_small=(i_small+i_large)//2
  C=n-i_large
  if c[0]>B:
    C+=1

  cnt+=A*C
if n>1:
  print(cnt)
else:
  if a[0]<b[0]<c[0]:
    print(1)
  else:
    print(0)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

M_NUM = 10**18

ans = 1
for item in a:
    ans *= item

if ans > M_NUM:
    print('-1')
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

M_NUM = 10**18

ans = 1
for item in a:
    if ans > M_NUM:
        break
    ans *= item

if 0 in a:
    print('0')
elif ans > M_NUM:
    print('-1')
else:
    print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())

list_cake_1 = []
list_cake_2 = []
list_cake_3 = []

while len(list_cake_1) < X:
	element = list(map(int, input().split()))
	list_cake_1.extend(element)

while len(list_cake_2) < Y:
	element = list(map(int, input().split()))
	list_cake_2.extend(element)
	
while len(list_cake_3) < Z:
	element = list(map(int, input().split()))
	list_cake_3.extend(element)

list_cake_12 = []

for i in list_cake_1:
	for j in list_cake_2:
		list_cake_12.append(i+j)

list_cake_12.sort()
list_cake_3.sort()

list_cake_123 = []

min_number = min([X*Y, K])

for i in range(1, min_number+1):
	for j in range(Z):
		list_cake_123.append(list_cake_12[-i]+list_cake_3[j])

list_cake_123.sort()

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

### FIXED CODE ###

import sys

input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())

list_cake_1 = list(map(int, input().split()))
list_cake_2 = list(map(int, input().split()))
list_cake_3 = list(map(int, input().split()))

list_cake_1 = sorted(list_cake_1, reverse=True)
list_cake_2 = sorted(list_cake_2, reverse=True)
list_cake_3 = sorted(list_cake_3, reverse=True)

list_total_sum = []

for i, cake_1 in enumerate(list_cake_1, 1):
	for j, cake_2 in enumerate(list_cake_2, 1):
		for k, cake_3 in enumerate(list_cake_3, 1):
			if i*j*k > K:
				break
			list_total_sum.append(cake_1 + cake_2 + cake_3)

for element in sorted(list_total_sum, reverse=True)[:K]:
	print(element)
### BUGGY CODE ###


import copy

class MyClass():

    maxSum = 0

    def do(self, baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if nokoriSousaCount < 0:
            return

        sum = 0
        for each in _temochi:
            sum += each

        if self.maxSum < sum:
            self.maxSum = sum

        if leftIndex <= rightIndex:
            temochi = copy.copy(_temochi)
            temochi.append(baseList[leftIndex])
            self.do(baseList, temochi, leftIndex + 1, rightIndex, nokoriSousaCount - 1)

            temochi = copy.copy(_temochi)
            temochi.append(baseList[rightIndex])
            self.do(baseList, temochi, leftIndex, rightIndex - 1, nokoriSousaCount - 1)
            
        self.removeMin(_temochi, leftIndex, rightIndex, nokoriSousaCount - 1)

    def removeMin(self, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if len(_temochi) > 0 and nokoriSousaCount > 0:
            minNum = min(_temochi)
            if minNum < 0:
                #temochi = copy.copy(_temochi)
                _temochi.remove(minNum)
                self.do(baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount)


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

doClass = MyClass()
doClass.do(baseList, [], 0, count - 1, opeCount)

print(doClass.maxSum)




### FIXED CODE ###

class MyClass():
    maxNumber = 0

    def roop(self, baseList, opeCount):
        listCount = len(baseList)
        roopMax = listCount if listCount < opeCount else opeCount
        for leftCount in range(0, roopMax):
            self.getMax(baseList[0: leftCount + 1], opeCount - leftCount - 1)

            for rightCount in range(1, roopMax - leftCount + 1):
                leftList = baseList[0: leftCount]
                rightList = baseList[listCount - rightCount : listCount]
                handList = leftList + rightList

                self.getMax(handList, opeCount - leftCount - rightCount)

                

    def getMax(self, handList, remainOpeCount):
        if len(handList) < 1:
            return

        maxVal = 0
        removeCount = 0

        if remainOpeCount > 0:
            handList.sort()
            for each in handList:
                if each < 0:
                    removeCount += 1
                    remainOpeCount -= 1
                    if remainOpeCount < 1:
                        break
        
        maxVal = sum(handList[removeCount:])
        self.maxNumber = max([maxVal, self.maxNumber])


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

my = MyClass()
my.roop(baseList, opeCount)
print(my.maxNumber)
### BUGGY CODE ###

N,M = map(int,input().split())
a = [list(map(int,input().split())) for i in range(M)]
b = []
c = []
for i in a:
    if i[0]==1:
        b.append(i)
    elif i[1]==N:
        c.append(i)
for i in b:
  for j in c:
    if i[1]==j[0]:
    	print('POSSIBLE')
    	exit()
print('IMPOSSIBLE')

### FIXED CODE ###

N,M = map(int,input().split())
a = [list(map(int,input().split())) for i in range(M)]
b = set()
for i in a:
    if i[0]==1 or i[1]==N:
        b.add((i[0],i[1]))
for i in range(2,N):
    if (1,i) in b and (i,N) in b:
    	print('POSSIBLE')
    	exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

class Cmb:
    def __init__(self, N, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,k = map(int,input().split())
mod = 10**9+7
c = Cmb(N=n)
ans = 0
for l in range(k+1):
    tmp = c(n,l)*c(n-1, n-l-1)
    ans += tmp%mod
print(ans%mod)

### FIXED CODE ###

class Cmb:
    def __init__(self, N, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,k = map(int,input().split())
mod = 10**9+7
c = Cmb(N=n)
ans = 0
for l in range(min(k+1, n)):
    tmp = c(n,l)*c(n-1, n-l-1)
    ans += tmp%mod
print(ans%mod)
### BUGGY CODE ###

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

for i in range(1,1+N):
    D.append(A.count(i))
    # print(A.count(i))

print(*D, sep='\n')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
D = [0 for i in range(N)]

for i in A:
    D[i-1] += 1

for i in range(len(D)):
    print(D[i])
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab=sorted(ab)
cost=[]
for i in range(n):
  cost+=[ab[i][0]]*ab[i][1]
print(sum(cost[0:m]))

### FIXED CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab=sorted(ab)
ans=0
d=0
for i in range(n):
  s=min(m-d,ab[i][1])
  ans+=ab[i][0]*s
  d+=s
  if d==m:
    break
print(ans)
### BUGGY CODE ###

S = input()

N = len(S)
japp = 0
ans = 0
for i in range(N,4,-1):
  for j in range(5,i+1):
    if i-j-japp < 0:
      japp = 0
      break
    Si = S[i-j-japp:i]
    if int(Si) % 2019 == 0:
      ans += 1
      japp = 4
      #print(Si)
    else:
      japp = 0 

print(ans)

### FIXED CODE ###

S = input()
counts =[0] * 2019
counts[0] = 1
num, d = 0,1

for s in S[::-1]:
  num += int(s) *d
  d *= 10
  num %= 2019
  d %= 2019
  counts[num] += 1

ans = 0
for count in counts:
  ans += count * (count - 1) //2
print(ans)
### BUGGY CODE ###

k=int(input())
a,b='','7'
count=1
if k%2==0:
  print(-1)
else:
  while True:
    a=a+b
    if int(a)%k==0:
      print(count)
      break
    else:
      count+=1


### FIXED CODE ###

k=int(input())
a=0
for i in range(k):
  a=(a*10+7)%k
  if a==0:
    print(i+1)
    exit()
    
print(-1)
### BUGGY CODE ###

from collections import defaultdict

n, k = map(int, input().split())
ans = 0
sushi = [list(map(int, input().split())) for _ in range(n)]

sushi.sort(key=lambda x: -x[1])

neta = set()
first = []
second = []
for s in sushi:
    t, d = s
    if t not in neta:
        first.append(d)
        neta.add(t)
    else:
        second.append(d)

first.sort(reverse=True)
second.sort(reverse=True)

kinds = min(k, len(first))
ans = 0

for i in range(1, kinds + 1):
    point = sum(first[:i])
    point += sum(second[:k - i])
    point += i ** 2
    ans = max(ans, point)

print(ans)


### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
top = [0] * n
sub = []

for i in range(n):
    t, d = map(int, input().split())
    t -= 1
    if top[t] == 0:
        top[t] = d
    else:
        if d > top[t]:
            sub.append(top[t])
            top[t] = d
        else:
            sub.append(d)

top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]

for p in top:
    if p == 0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1] + p)

for p in sub:
    sub_sum.append(sub_sum[-1] + p)

ans = 0

for i in range(1, k + 1):
    if (len(sub_sum) - 1) >= (k - i) and top_sum[i] != -1:
        ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)

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

import math
a,b,n = map(int,input().split())
ans = 0
start =  b // a
for i in range(start,n+1):
    dum1 = (a * i / b) // 1
    dum2 = a * ((i / b)//1)
    dum3 = dum1 - dum2
    #print(dum1,dum2)
    ans = max(ans,dum3)
print(math.ceil(ans))

### FIXED CODE ###

import math
a,b,n = map(int,input().split())
if b-1 <= n:
    print(math.floor((a*(b-1))/b)-(a*math.floor((b-1)/b)))
else:
    print(math.floor((a * (n)) / b) - (a * math.floor((n) / b)))