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

h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

gh = {i:[] for i in range(h+1)}
gw = {i:[] for i in range(w+1)}

for _h, _w in hw:
    gh[_h].append(_w)
    gw[_w].append(_h)
    
ansh = 0
posh = -1
answ = 0
posw = -1
for k,v in gh.items():
    if len(v) > ansh:
        ansh = len(v)
        posh = k
for k,v in gw.items():
    if [posh,k] in hw:
        if len(v)-1 > answ:
            answ = len(v)-1
            posw = k
    else:
        if len(v) > answ:
            answ = len(v)
            posw = k
            
print(ansh+answ)

### FIXED CODE ###

h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

hc = [0]*h
wc = [0]*w
d={}
for _h, _w in hw:
    hc[_h-1]+=1
    wc[_w-1]+=1
    d[(_h-1,_w-1)]=1
    
maxh = max(hc)
maxw = max(wc)
    
        
hoge = True
wi = [i for i in range(w) if wc[i]==maxw]
for h in [i for i in range(h) if hc[i]==maxh]:
    for w in wi:
        if (h,w) not in d:
            hoge=False
            break
            
if hoge:
    print(maxh+maxw-1)
else:
    print(maxh+maxw)
### BUGGY CODE ###

from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N-1):#距離、点
    graph.append([abs(A[k][0]-A[k-1][0]),A[k][2],A[k-1][2]])
    graph.append([abs(A[k][0]-A[k+1][0]),A[k][2],A[k+1][2]])
graph.append([abs(A[N-1][0]-A[N-2][0]),A[N-1][2],A[N-2][2]])
for k in range(N-1):
    graph.append([abs(B[k][1]-B[k-1][1]),B[k][2],B[k-1][2]])
    graph.append([abs(B[k][1]-B[k+1][1]),B[k][2],B[k+1][2]])
graph.append([abs(B[N-1][1]-B[N-2][1]),B[N-1][2],B[N-2][2]])

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
#クラスカル法
kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

### FIXED CODE ###

from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):#距離、点
    graph.append([min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]])
for k in range(N):
    graph.append([min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]])

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
#クラスカル法
kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)
### BUGGY CODE ###

R, G, B, n = list(map(int, input().split()))

cnt = []
for r in range(n//R + 1):
  nn = n - r*R
  for g in range(nn//G + 1):
    nnn = nn - g*G
    if nnn % B == 0:
      cnt.append([r, g, nnn // B])
print(len(cnt))
    

### FIXED CODE ###

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

cnt = 0
for i in range(n//a+1):
  an = n - a * i
  for j in range(an//b+1):
    num = an - b * j
    if num >= 0 and num % c == 0:
      cnt+=1
        
print(cnt)
### BUGGY CODE ###

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range(n):
            tmp += Train[i][j]
            P_Train[i][j] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        if  p - 1 < 0:
            ans += P_Train[i][q]
        else:
            ans += P_Train[i][q] - P_Train[i][p - 1]
    return ans


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range(n):
            tmp += Train[i][j]
            P_Train[i][j] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        if  p - 1 < 0:
            ans += P_Train[i][q]
        else:
            ans += P_Train[i][q] - P_Train[i][p - 1]
    return ans


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

n, w = map(int, input().split())
items = []

append = items.append
for i in range(n):
    append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0] * (w + 1) for _ in range(n + 1)]
    g = [[0] * (w + 1) for _ in range(n + 1)]

    for i in range(w + 1):
        g[0][i] = 1

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)


### FIXED CODE ###

n, w = map(int, input().split())
items = []
 
for i in range(n):
    items.append(list(map(int, input().split())))
 
 
def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
 
    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1
 
    for i in range(n + 1):
        c[i][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1
 
    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes
 
 
result, _ = knapsack(n, w, items)
print(result)
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return colors

def solve():
  n,m  =(int(i) for i in input().split())
  graph = [[] for _ in range(n)]
  for i in range(m):
    a,b = (int(i) for i in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  colors = isbipart(n,graph)
  if colors:
    b = colors.count(1)
    w = colors.count(-1)
    print(b*w-m)
  else:
    print(n*(n-1)//2-m)
solve()

### FIXED CODE ###


from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return colors

def solve():
  n,m  =(int(i) for i in input().split())
  graph = [[] for _ in range(n)]
  for i in range(m):
    a,b = (int(i) for i in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  colors = isbipart(n,graph)
  if colors:
    b = colors.count(1)
    w = n-b
    print(b*w-m)
  else:
    print(n*(n-1)//2-m)
solve()
### BUGGY CODE ###

k = int(input())
from fractions import gcd

# when input is list type
def list_gcd(a):
    x=a[0]
    for i in range(1,len(a)):
        x=gcd(x,a[i])
    return x

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        ans+=3*list_gcd([i+1,j+1])
        ans+=3*list_gcd([i+1,j+1])
        for l in range(j+1, k):
            ans+=6*list_gcd([i+1,j+1,l+1])
print(ans)

### FIXED CODE ###

k = int(input())
from fractions import gcd

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        x=gcd(i+1,j+1)
        ans+=6*gcd(i+1,j+1)
        for l in range(j+1, k):
            ans+=6*gcd(x,l+1)
print(ans)
### BUGGY CODE ###

import sys
from heapq import heapify, heapreplace

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = map(int, read().split())
    a = [int(i) for i in read().split()]
    heapify(a)
    for _ in range(m):
        b, c = map(int, read().split())
        for _ in range(b):
            if a[0] < c:
                heapreplace(a, c)
            else:
                break
    print(sum(a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from operator import itemgetter
from heapq import heapify, heapreplace

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = map(int, read().split())
    a = [int(i) for i in read().split()]
    bc = sorted([[int(i) for i in read().split()] for _ in range(m)], key=itemgetter(1), reverse=True)
    heapify(a)
    for b, c in bc:
        for _ in range(b):
            if a[0] < c:
                heapreplace(a, c)
            else:
                break
    print(sum(a))

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

from collections import deque
N = int(input())
A = list(map(int, input().split()))
#N=3
#A=[1,2,3]
q=deque(A)
#print(q)
ans=0
for i in range(N-1):
    ans+=q.popleft() *sum(q)
print(ans%(10**9+7))

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
#N=3
#A=[1,2,3]
q=deque(A)
#print(q)
ans=0
sums=sum(q)
#print(sums)
for i in range(N-1):
    qwe=q.popleft()
    ans+=qwe *(sums-qwe)
    sums-=qwe
print(ans%(10**9+7))
### BUGGY CODE ###

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

A.sort()

for i in range(M):
    A[-1] = A[-1]//2
    A.sort()
print(sum(A))

### FIXED CODE ###

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

n, m = list(map(int, input().split()))
a = list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(a)
for i in range(m):
    value = heapq.heappop(a)
    value = (value+1)//2
    heapq.heappush(a, value)

# print(a)
print(-sum(a))
### BUGGY CODE ###

while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	ref = [0]
	for i in a:
		ref += [i+j for j in ref]
	print min(abs(sum(a)-2*i) for i in ref)

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###


if __name__ == "__main__":
    n,c  = map(int, input().split())

    timeline = {}
    for i in range(n):
        s, t, c = list(map(int, input().split()))
        for i in range(s-1, t):
            xs = timeline.get(i, None)
            if xs is None:
                xs = set()
            xs.add(c)
            timeline[i] = xs
    print(max([len(v) for k, v in timeline.items()]))


### FIXED CODE ###

def getter(starts, ends):
    while starts:
        if starts[-1][0] < ends[-1][1]:
            yield (starts.pop(), True)
        else:
            yield (ends.pop(), False)


def foo(C, targets):
    starts = sorted(targets, key=lambda x:x[0], reverse=True)
    ends = sorted(targets, key=lambda x: x[1], reverse=True)

    result = 0
    active = [0]*(C+1)
    for x, p in getter(starts, ends):
        if p:
            active[x[2]] += 1
        else:
            active[x[2]] -= 1
        result = max(result, sum(map(lambda x: 1 if x > 0 else 0 ,active)))
    return result


if __name__ == "__main__":
    n, C  = map(int, input().split())

    targets = []
    for i in range(n):
        s, t, c = list(map(int, input().split()))
        targets.append((s-1, t, c))
    print(foo(C, targets))
### BUGGY CODE ###

from numpy import*
a,b=loadtxt(open(0),'i',skiprows=1)
c=0
l=1<<29
while l:u=l;l>>=1;c+=sum(diff(searchsorted(sort(r_[b%u-u,b%u]),([u],[l])-a%u).T))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)
### BUGGY CODE ###

N, P = map(int,input().split())
 
output=1
 
for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

### FIXED CODE ###

N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)
### BUGGY CODE ###

n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    if i+1 in fl:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            break
            

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


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M,K = map(int,input().split())
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

A,B,K=map(int,input().split())
X=range(A,B+1)
i=0
while i<=len(X)-1:
    if i<=K-1 or i>=len(X)-K:
        print(X[i])
        i+=1
    else:
        i+=1


### FIXED CODE ###

A,B,K=map(int,input().split())
l=[int(i) for i in range(A,min(B+1,A+K))]
s=[int(i) for i in range(max(B-K+1,A+K-1),B+1)]
l=l+s
L=list(set(l))
L.sort()
for i in L:
    print(i)
### BUGGY CODE ###

from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    flip = 0
    while not (a > 0 and b > 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)


### FIXED CODE ###

from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    if a < 0 or a == 0 and b < 0:
        a, b = -a, -b
    if b <= 0:
        a, b = -b, a
        flip = 1
    else:
        flip = 0

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)
### BUGGY CODE ###

def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

def f(b, n):
    re = 0
    while n:
        re += n % b
        n //= b
    return re

N = int(input())
S = int(input())

for b in divisors(abs(N-S)):
    b += 1
    if f(b, N) == S:
        print(b)
        break
else:
    print(-1)


### FIXED CODE ###

def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

def f(b, n):
    re = 0
    while n:
        re += n % b
        n //= b
    return re

N = int(input())
S = int(input())
if N < S:
    print(-1)
elif N == S:
    print(N+1)
else:
    for b in divisors(N-S):
        b += 1
        if f(b, N) == S:
            print(b)
            break
    else:
        print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

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

# 木構造をリストで表現する
G = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    P[p] += x

# 各頂点のカウンター
Count = [0] * (N+1)


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    Count[v] = point + P[v]

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, Count[v])


dfs(1, 0, 0)

res = ' '.join(map(str, Count[1:]))
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

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

a.sort()

result = 0
mod = 10**9+7

def solve(x, y):
    if x == 0:
        return 1
    else:
        x = min(x, y-x)
        r = 1
        for i in range(y-x+1, y+1):
            r *= i
            r %= mod
        for i in range(1, x+1):
            r *= pow(i, mod-2, mod)
            r %= mod
        return r



for i in range(n-k+1):
    for j in range(i+k-1, n):
        result = (result+(a[j]-a[i])*solve(k-2, j-i-1))%mod
print(result)

### FIXED CODE ###

N, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

result = 0
mod = 10**9+7

 
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
n = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, n+1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if k==1:
    print(0)
else:
    result = 0
    for i in range(N-k+1):
        result += (a[N-i-1]-a[i])*cmb(N-1-i, k-1)
        result %= mod

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

n=int(input())
s=[sorted(input()) for _ in range(n)]
cnt=0
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    if s[i]==s[j]:
      cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=[''.join(sorted(input())) for _ in range(n)]
ans=0
cnt={}
for i in range(n):
  if s[i] in cnt:
    cnt[s[i]]+=1
  else:
    cnt[s[i]]=1
print(sum(cnt[key]*(cnt[key]-1)//2 for key in cnt))