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

import math
N,M,k = map(int,input().split())
p = N*M
PP = 1
for i in range(p-k+1,p-1):
    PP *= i
P = PP//math.factorial(k-2)
    
Q = N*(N-1)*(N+1)*M*M//6
R = M*(M-1)*(M+1)*N*N//6
print((P*(Q+R))%(10**9+7))

### FIXED CODE ###

import math
N,M,k = map(int,input().split())
p = N*M
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

P = cmb(p-2,k-2)
Q = N*(N-1)*(N+1)*M*M//6
R = M*(M-1)*(M+1)*N*N//6
print((P*(Q+R))%(10**9+7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

N = int(input())
MOD = 10 ** 9 + 7

to = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)

visited = [False] * N
def dfs(n):
    visited[n] = True
    w = 1
    b = 1
    for i in to[n]:
        if visited[i] == False:
            rw, rb = dfs(i)
            w *= (rw + rb) % MOD
            b *= rw % MOD
    return (w,b)

ans = dfs(0)
print((ans[0] + ans[1]) % MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

N = int(input())
MOD = 10 ** 9 + 7

to = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)

def dfs(n,p):
    w = 1
    b = 1
    for i in to[n]:
        if i != p:
            rw, rb = dfs(i, n)
            w *= (rw + rb)
            w %= MOD
            b *= rw
            b %= MOD
    return (w,b)

ans = dfs(0, -1)
print((ans[0] + ans[1]) % MOD)
### BUGGY CODE ###

import bisect

N = int(input())
A = [int(input()) for _ in range(N)]

x = []
for a in A:
    i = bisect.bisect_left(x,a)
    if i==0: x = [a] + x
    else: x[i-1]=a

print(len(x))

### FIXED CODE ###

import bisect

N = int(input())
A = [-int(input()) for _ in range(N)]

x = [A[0]]

for a in A[1:]:
    i = bisect.bisect(x,a)
    if i==len(x): x.append(a)
    else: x[i]=a

print(len(x))
### BUGGY CODE ###

n=int(input())
a=[]
ans=0
for i in range(n):
    s=list(input())
    s.sort()
    ans+=a.count(s)
    a.append(s)
print(ans)


### FIXED CODE ###

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

from collections import deque
n=int(input())
numList=deque([])
for i in range(n):
    a=input()
    if a in numList:
        numList.remove(a)
    else:
        numList.append(a)
print(len(numList))

### FIXED CODE ###

from collections import Counter
n=int(input())
a=[int(input()) for i in range(n)]
cnt=Counter(a)
print(len(tuple(i for i in cnt.values() if i%2==1)))
### BUGGY CODE ###

import numpy as np

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

list_seikaisha =[]

for i in range(Q):
    list_seikaisha.append(int(input())-1)

list_pt=[K for i in range(N)]
arr_pt=np.array(list_pt)

for seikaisha in list_seikaisha:
    arr_pt=arr_pt-1
    arr_pt[seikaisha]=arr_pt[seikaisha]+1

list_YN=[]
f=lambda pt:"Yes" if pt>=1 else "No"
for pt in arr_pt:
    print(f(pt))


### FIXED CODE ###

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

list_seikaisha =[]

for i in range(Q):
    list_seikaisha.append(int(input())-1)

list_pt=[K for i in range(N)]

for seikaisha in list_seikaisha:
    list_pt[seikaisha]=list_pt[seikaisha]+1
list_pt=[x-Q for x in list_pt]

list_YN=[]
f=lambda pt:"Yes" if pt>=1 else "No"
for pt in list_pt:
    print(f(pt))
### BUGGY CODE ###

import sys
from collections import Counter

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


N = I()
A = LI()

for i in range(0, N):
    A_part = A[:i] + A[i+1:]
    counter_a = Counter(A_part)
    choice_total = sum([(count*(count-1)//2) for count in counter_a.values() if count > 1])
    print(choice_total)

### FIXED CODE ###

import sys
from collections import Counter

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
counter_a = Counter(A)
choice_total = sum([(count*(count-1)//2) for count in counter_a.values() if count > 1])

for i in range(0, N):
    sub_num = A[i]
    count_sub_num = counter_a[sub_num]
    print(choice_total - ((count_sub_num*(count_sub_num-1) - (count_sub_num-1)*(count_sub_num-2)) // 2))
### BUGGY CODE ###

import math
from functools import reduce


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def lcm(l):
    return reduce(lcm_base, l, 1)


N = int(input())
A = list(map(int, input().split()))
P = int(1e9+7)

lcm_a = lcm(A)
ans = 0
for a in A:
    ans = (ans + lcm_a//a) %P
print(ans)


### FIXED CODE ###

import math
from functools import reduce


N = int(input())
A = list(map(int, input().split()))
P = int(1e9+7)

def lcm_base(x, y):
    ret = (x * y) // math.gcd(x, y)
    return ret


def lcm(iter):
    return reduce(lcm_base, iter, 1)


lcm_a = lcm(A) % P
ans = 0
for a in A:
    a_inv = pow(a, P-2, P)
    ans = (ans + lcm_a*a_inv) %P
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
res = 0
for i in range(0, n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            for k in range(j+1,n):
                if j-i!=k-j:
                    if(s[i] != s[k] and s[j] != s[k]):
                        res += 1

print(res)

### FIXED CODE ###

import collections

n = int(input())
s = input()
res = 0
# for i in range(0, n):
#     for j in range(i+1,n):
#         if s[i] != s[j]:
#             for k in range(j+1,n):
#                 if j-i!=k-j and s[i] != s[k] and s[j] != s[k]:
#                     res += 1
#
# print(res)
num = collections.Counter(s)
# print(num)
num_r = num["R"]
num_g = num["G"]
num_b = n - num_r - num_g
count_2 = 0
for x in range(1,int(n/2)+1):
    for i in range(n-2*x):
        # print(x)
        # print(i)
        # print()
        if (i + 2 * x < n and s[i] != s[i + x] and s[i + x] != s[i + 2 * x] and s[i] != s[i + 2 * x] ):
            count_2 += 1
            # print(x)
            # print(i)
            # print()

res = num_r * num_g * num_b - count_2
# print(num_r)
# print(num_g)
# print(num_b)
print(res)
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
A.append(0)
D=[abs(A[0])]
for i in range(n-1):
  D+=[abs(A[i]-A[i+1])]
D.append(abs(A[n-1]))
for i in range(n):
  print(sum(D[:i])+abs(A[i-1]-A[i+1])+sum(D[i+2:]))

### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
A.append(0)
D=[abs(A[0])]
for i in range(n-1):
  D+=[abs(A[i]-A[i+1])]
D.append(abs(A[n-1]))
d=sum(D)
for i in range(n):
  print(d+abs(A[i-1]-A[i+1])-D[i]-D[i+1])
### BUGGY CODE ###

X, K, D = map(int, input().split())

poss = True

if X > 0:
    poss = True
else:
    poss = False

old = X

for i in range(K):
    if X > 0:
        if poss == False:
##            if abs(old) >= abs(X):
##                break
##            else:
##                print("false", i)
            if (K-i)%2 == 0:
                break
            else:
                X = abs(X-D)
                break
            
            
        old = X
        X -= D
    elif X < 0:

        if poss == True:
##            if abs(old) >= abs(X):
##                break
##            else:
##                
##                print("true", i, X, old)

            if (K-i)%2 == 0:
                break
            else:
                X = abs(X+D)
                break
        
        old = X
        X += D
    else:
        if (K-i)%2 == 0:
            break
        else:
            X = X+D
            break


print(abs(X))


### FIXED CODE ###

X, K, D = map(int, input().split())

X = abs(X)

cuts = X//D

if cuts>=K:
    print(X-(K*D))
else:
    remainingcuts = K-cuts
    r = X-cuts*D

    if remainingcuts%2 == 1:
        print(abs(r-D))
    else:
        print(r)
### BUGGY CODE ###

x, k, d = map(int, input().split())

if abs(x)//d >= k:
  print(abs(abs(x) - k*d))

else:
  a = 1
  while abs(x) - d*a >=0:
    a += 1
  if (k-(a-1)) % 2 ==0:
    print(abs(abs(x) - (a-1)*d))
  else:
    print(abs(abs(x) - a*d))


### FIXED CODE ###

x, k, d = map(int, input().split())

if abs(x)//d >= k:
  print(abs(abs(x) - k*d))

else:
#  a = 1
  y = abs(x)//d
  a = y + 1
#  while abs(x) - d*a >=0:
#    a += 1
  if (k-(a-1)) % 2 ==0:
    print(abs(abs(x) - (a-1)*d))
  else:
    print(abs(abs(x) - a*d))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
evisited = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

def dfs(p, v):
    if visited[v]:
        return
    visited[v] = True
    for i in edges[v]:
        if i != p and i not in evisited[v]:
            dfs(v, i)
    count = 0
    for i in edges[v]:
        if i != p and i not in evisited[v]:
            print(v + 1, i + 1)
            evisited[i].add(v)
            count += 1
    if count % 2 == 1:
        print(v + 1, p + 1)
        evisited[p].add(v)

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)
    for v in range(n):
        for (i, r) in edges[v]:
            if r >= 0:
                print(v + 1, i + 1)
### BUGGY CODE ###

from itertools import permutations
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=[int(i)-1 for i in input().split()]
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j], d[i][k]+d[k][j])
#print(d)
ans=10**12
for v in permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

import itertools
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=list(map(int,input().split()))
for i in range(r):
  l[i]-=1
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j], d[i][k]+d[k][j])
#print(d)
ans=10**12
for v in itertools.permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if prev[a] == 0:
      a_color=[]
    else:
      a_color=[G[a][prev[a]][1]]
    for b in G[a]:
      if seen[b] == 0:
        seen[b] = 1
        todo.append(b)
        prev[b] = a
        for c in range(1,N+1):
          if c not in a_color:
            a_color.append(c)
            colors.append((G[a][b][0],c))
            G[a][b][1]=G[b][a][1]=c
            if c > cmax: cmax = c
            break
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

print(cmax)
for i in range(N-1):
  print(colors[i][1])

### FIXED CODE ###

from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if len(G[a])<50:
      if prev[a] == 0:
        a_color=set([])
      else:
        a_color=set([G[a][prev[a]][1]])
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          for c in range(1,N+1):
            if c not in a_color:
              a_color.add(c)
              colors.append((G[a][b][0],c))
              G[a][b][1]=G[b][a][1]=c
              if c > cmax: cmax = c
              break
    else:
      temp = list(range(1,N))
      if prev[a] != 0:
        del temp[G[a][prev[a]][1]-1]
      temp = deque(temp)
      for i,b in enumerate(G[a]):
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          c = temp.popleft()
          colors.append((G[a][b][0],c))
          G[a][b][1]=G[b][a][1]=c
          if c > cmax: cmax = c
            
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

print(cmax)
for i in range(N-1):
  print(colors[i][1])
### BUGGY CODE ###

N=int(input())

i=0
while(True):
  i+=1
  if (i % N == 0 and i % 2==0):
    print(i)
    break



### FIXED CODE ###

def main():
    a, b = 2, int(input())
    ta, tb = a, b
    if b == 0: print(0)
    while a%b != 0:
       a, b = b, a%b
    print(int((ta*tb)/b))
main()
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
import copy
a = copy.deepcopy(p)
for i in range(n):
    a[i] = [-a[i],0,i]
import heapq as hp
hp.heapify(a)
for i in range(k):
    s = hp.heappop(a)
    u = [s[0]/2,s[1]+1,s[2]]
    hp.heappush(a, u)
ans = 0
for i in range(n):
    ans = max(-(-p[a[i][2]]//(a[i][1]+1)),ans)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
def test(d,m,u):
    global ans
    p = 0
    for i in range(n):
        if m < a[i]:
            p += a[i]//m
    if u-d <= 1:
        ans = max(ans,m)
        pass
    elif p > k:
        ans = max(ans,m)
        d = m
        m = -(-(m+u)//2)
        test(d,m,u)
    else:
        u = m
        m = -(-(m+d)//2)
        test(d,m,u)
d = 0
m = 1
u = 10**9+7
test(d,m,u)
print(ans)
### BUGGY CODE ###

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)
ab = abs
n = k = ar = dp = 0

def solve(x):
	global n,k,ar,dp
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,min(n,x+k+1)):
		t = ab(ar[x]-ar[i])+solve(i)
		m = t if t<m else m
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	global n,ar,k,dp
	(n,k), ar = [[*map(int,s.split())] for s in [*open(0)]]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

N = int(input())

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

ans = []
for i in range(1,N+1):
    ans.append(A.index(i)+1)

print(*ans)

### FIXED CODE ###

N = int(input())

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

student = list(range(0,N))

student.sort(key = lambda x:A[x])

for s in student:
    print(s+1,end= " ")
### BUGGY CODE ###

S = input()
B = []
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    C = []
    A = list(map(str, input().split()))
    if len(A) == 3:
        C.append(A[2])
    if int(A[0]) == 1:
        B.reverse()
    else:
        if int(A[1]) == 1:
            B = C + B
        else:
            B.append(A[2])
print(''.join(B))

### FIXED CODE ###

from collections import deque

S = input()
B = deque()
res = 0
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    A = list(map(str, input().split()))
    if int(A[0]) == 1:
        if res == 0:
            res = 1
        else:
            res = 0
    else:
        if int(A[1]) == 1:
            if res == 0:
                B.appendleft(A[2])
            else:
                B.append(A[2])
        else:
            if res == 0:
                B.append(A[2])
            else:
                B.appendleft(A[2])
if res == 0:
    print(''.join(B))
else:
    B.reverse()
    print(''.join(B))
### BUGGY CODE ###

n = int(input())
a = [int(i)for i in input().split()]
for i in range(1, n + 1):
    print(a.count(i))


### FIXED CODE ###

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

import math
k=int(input())
a=1
s=0
while a<=k:
  b=1
  while b<=k:
    c=1
    while c<=k:
      g=math.gcd(a,b)
      s+=math.gcd(g,c)
      c+=1
    b+=1
  a+=1
print(s)

### FIXED CODE ###

from fractions import gcd
n=int(input())
ans=0
for i in range(1,n+1):
  for k in range(i,n+1):
    gc=gcd(i,k)
    for _ in range(k,n+1):
      g=gcd(gc,_)
      if i==_:
        ans+=g
      elif i==k or k==_:
        ans+=g*3
      else:
        ans+=g*6
print(ans)
### BUGGY CODE ###

import math
ans = 0
n = int(input())
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      num = math.gcd(i,j)
      num = math.gcd(num,k)
      ans += num
print(ans)

### FIXED CODE ###

import math
n = int(input())
lis = [[0] * n for i in range(n)]
for i in range(n):
  for j in range(n):
    lis[i][j] = math.gcd(i+1,j+1)
ans = 0
for i in range(n):
  for j in range(n):
    for k in range(n):
      ans += lis[i][lis[k][j]-1]
print(ans)
### BUGGY CODE ###

# D
N = int(input())
L = list(map(int,input().split()))
count = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if abs(L[i]-L[j]) < L[k] and L[k] < L[i] + L[j]:
                count += 1
print(count)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int,input().split()))
count = 0
L.sort() # 昇順
for i in range(N):
    for j in range(i+1,N):
        ind = bisect.bisect_left(L,L[i]+L[j])
        count += ind-j-1

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

import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP=[[] for i in range(N+1)]
for _ in range(M):
    i, j = LI()
    MP[i].append(j)
# print(MP)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

len_1 = len(MP[1])

# print("len_1: {}".format(len_1))
# print(RES)

result = RES[1]
RESN = [0]*(N+1)
for i in range(1, N-1):
    skip = False
    max_j = max((RES[w],w) for w in MP[i])[1]

    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        if div == 0:
            skip = True
            break
        else:
            RESN[k] = next_E / div
    if not skip:
        result = min(result, RESN[1])

print(result)


### FIXED CODE ###

def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()
### BUGGY CODE ###

from collections import defaultdict
s = input()
n = len(s)

d = defaultdict(int)
d[0] = 1
for i in range(n):
    x = int(s[i:])
    d[x%2019] += 1

res = 0
for k in d:
    c = d[k]
    res += c*(c-1)//2
print(res)


### FIXED CODE ###

P = 2019
S = input()
N = len(S)
 
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()
 
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1
 
print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
  if i-a<k or b-i<k:
    print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
l=min((a+b+1)//2,a+k)
r=max((a+b+1)//2,b-k+1)
for i in range(a,l):
  print(i)
for i in range(r,b+1):
  print(i)
### BUGGY CODE ###

from collections import Counter
from itertools import accumulate
import bisect

n = int(input())
a = tuple(map(int, input().split()))
b = sorted(Counter(a).values())
b = tuple([0]*(n-len(b))+b)
c = tuple([0]+list(accumulate(b)))

ans = []
for k in range(1,n+1):
    l = 0
    r = n+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    ans.append(l)

print('\n'.join(map(str,ans)))




### FIXED CODE ###

from collections import Counter
from itertools import accumulate
import bisect

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

print(n)
for k in range(2,n//2+1):
    l = 0
    r = n+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    print(l)

for k in range(max(n//2+1,2),n+1):
    if exist>=k:
        print(1)
    else:
        print(0)