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

import sys
input=sys.stdin.readline

n,w=map(int,input().split())
dp=[0]*(w+1)
c,p=map(int,input().split())
dp[c]=p

def ans(n,w):
  for _ in range(1,n):
    c,p=map(int,input().split())
    for j in range(w,c,-1):
      if dp[j-c] != 0 and dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
    if dp[c] < p:
      dp[c]=p
  return max(dp)
print(ans(n,w))

### FIXED CODE ###

import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))
### BUGGY CODE ###

from collections import deque

h,w=map(int, input().split())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append((i,j))
            visited[i][j] = 0

queue = deque(black)


while queue:
    y,x = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = y+j,x+k 
        if newy < 0 or newy >= h:continue 
        if newx < 0 or newx >= w:continue 
        if visited[newy][newx] == -1:
            visited[newy][newx] = visited[y][x] + 1
            queue.append((newy,newx))

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,visited[i][j])

print(ans)


### FIXED CODE ###

from collections import deque

h,w=map(int, input().split())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append((i,j))
            visited[i][j] = 0

queue = deque(black)


while queue:
    y,x = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = y+j,x+k 
        if newy < 0 or newy >= h:continue 
        if newx < 0 or newx >= w:continue 
        if visited[newy][newx] == -1:
            visited[newy][newx] = visited[y][x] + 1
            queue.append((newy,newx))

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,visited[i][j])

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

import itertools
import numpy as np

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

a = [1,5,10]
b = [i for i in list(itertools.combinations_with_replacement(a,N)) if sum(i) == Y/1000]
if b:
    print(b[0].count(10),b[0].count(5),b[0].count(1))
else:
    print(-1,-1,-1)

### FIXED CODE ###

N, Y = map(int, input().split())
ans = -1,-1,-1
for x in range(N+1):
    for y in range(N - x + 1):
        z = N - x - y
        if 0<=z<=2000 and 10000*x+5000*y+1000*z == Y:
            ans = x,y,z
            break
    else:
        continue
    break
print(*ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
S = input()
K = int(input())

lenS = len(S)
if lenS == 1:
    print(K//2)
    exit()

cnt_one = 0
i = 0
while i < lenS-1:
    if S[i] == S[i+1]:
        cnt_one += 1
        i += 2
    else:
        i += 1

if K == 1:
    print(cnt_one)
    exit()

SS = S*2
lenS = len(SS)

cnt_two = 0
i = 0
while i < lenS-1:
    if SS[i] == SS[i+1]:
        cnt_two += 1
        i += 2
    else:
        i += 1

lenS = len(S)
if len(set(S)) == 1:
    if lenS%2 == 1:
        ans = 0
        for j in range(1, K+1):
            if j%2 == 1:
                ans += cnt_one
            else:
                ans += cnt_two - cnt_one
        print(ans)
        exit()

print((cnt_two - cnt_one)*(K-1) + cnt_one)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
S = input()
K = int(input())

lenS = len(S)
if lenS == 1:
    print(K//2)
    exit()

cnt_one = 0
i = 0
while i < lenS-1:
    if S[i] == S[i+1]:
        cnt_one += 1
        i += 2
    else:
        i += 1

if K == 1:
    print(cnt_one)
    exit()

SS = S*2
lenSS = len(SS)

cnt_two = 0
i = 0
while i < lenSS-1:
    if SS[i] == SS[i+1]:
        cnt_two += 1
        i += 2
    else:
        i += 1

if len(set(S)) == 1:
    if lenS%2 == 1:
        if K%2 == 0:
            ans = (cnt_two) * (K//2)
        else:
            ans = (cnt_one * (K//2 + 1)) + ((cnt_two-cnt_one) * (K//2))
        print(ans)
        exit()

print((cnt_two - cnt_one)*(K-1) + cnt_one)
### BUGGY CODE ###

n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
i=0
num=0

while i<n-1:
        if a[i] + a[i+1] > x:
                a[i+1]=a[i+1]-1
                num=num+1
        else:
                i=i+1

print num

### FIXED CODE ###

n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
i=0
num=0

if a[0] > x:
        ans=a[0]-x
        a[0]=a[0]-ans
        num=num+ans
while i<n-1:
        if a[i] + a[i+1] > x:
                ans=a[i] + a[i+1] - x
                a[i+1]=a[i+1]-ans
                num=num+ans
        else:
                i=i+1

print num
### BUGGY CODE ###

import numpy as np
from functools import reduce
import fractions
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
n = int(input())

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

lcm = lcm_list(inp_list)

ans = 0

for i in inp_list:
    ans += lcm // i
    if ans > (10**9+7):
        ans -= (10**9+7)


print(ans % (10**9+7))


### FIXED CODE ###

from functools import reduce
import fractions
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
n = int(input())

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

lcm = lcm_list(inp_list)

ans = 0
mod = 10**9+7

for i in inp_list:
    ans += lcm // i



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

# coding: utf-8


def add_list(_n):
    _l = []
    for _ in range(_n):
        a, b = map(int, raw_input().split())
        for i in range(b):
            _l.append(a)
    return _l

n, k = map(int, raw_input().split())
l = add_list(n)
l.sort()

print l[k-1]


### FIXED CODE ###

# coding: utf-8

l = 10 ** 5
num = [0] * (l + 1)
n, k = map(int, raw_input().split())

for _ in xrange(n):
    a, b = map(int, raw_input().split())
    num[a] += b

for i in xrange(1, l+1):
    k -= num[i]
    if k <= 0:
        print i
        break
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 0
for i in range(N):
    for t in range(i):
        if P[i] > P[t]:
            count += 1   
            break
print(N - count)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
result = 1
mini = P[0]
for i in P:
    if mini > i:
        result += 1
        mini = i
print(result)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
lis = [0]*1000
#one = [0]*10
#two = [0]*10
#three=[0]*10
from itertools import combinations
for i,j,k in combinations(list(range(n)), 3):
  temp = int("".join([s[i], s[j], s[k]]))
  if lis[temp]==0:
    ans+=1
    lis[temp]=1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
lis = [0]*1000
one = [0]*10
two = [0]*100

for i in range(n):
  temp1 = int(s[i])
  if one[temp1]==1:
    continue
  else:
    one[temp1]=1
 
  for j in range(i+1, n):
    temp2 =  int("".join([s[i], s[j]]))
    if two[temp2]==1:
      continue
    else:
      two[temp2]=1
    
    for k in range(j+1, n):
      pin=int("".join([s[i], s[j], s[k]]))
      if lis[pin]==0:
        ans+=1
        lis[pin]=1
print(ans)
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
Y = sorted(list(set(X)))
Z = [X.count(y) for y in Y]
cnt = 0
for i in range(len(Y)):
    cnt += Z[i] 
    if cnt == N//2:
        cnt = len(list(range(Y[i],Y[i+1])))
        break
    elif cnt > N//2:
        cnt = 0
        break
print(cnt)

### FIXED CODE ###

N = int(input())
X = sorted(list(map(int,input().split())))
print(X[N//2]-X[N//2-1])
### BUGGY CODE ###

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

i_1 = a.index(1)

ans = 9999999999

# left = len(a[:i_1])
# right len(a[i_1+1:)

# if left < k or right <k:
#     c = math.ce

for i in range(1,k+1):
    count = 1
    left = i_1-(k-i)
    right = i_1+i

    if left < 0 or right < 0:
        continue


    l_l = len(a[:left])
    r_l = len(a[right:])

    count += math.ceil(l_l / (k-1)) + math.ceil(r_l / (k-1))
    ans = min(count,ans)

print(ans)

### FIXED CODE ###

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

i_1 = a.index(1)

ans = 9999999999

left = len(a[:i_1])
right = len(a[i_1:])

for i in range(k):
    x = left  - i
    y = right - (k-i)
    
    if x < 0 or y < 0:
        continue
    
    count = 1 + math.ceil(x/(k - 1)) + math.ceil(y/(k - 1))
    ans = min(ans,count)

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

import copy

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

for i in range(N):
    tmp = copy.copy(A)
    tmp.remove(A[i])
    print(max(tmp))

### FIXED CODE ###

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

maxNum = max(A)
index = -1
for i in range(N):
    if A[i] == maxNum:
        index = i

for i in range(N):
    if i != index:
        print(maxNum)
        continue
    else:
        A.remove(maxNum)
        print(max(A))
### BUGGY CODE ###

from collections import deque
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  row = list(input())
  blocks += row.count("#")
  matrix.append(row)

q = deque([(0,0,0)])
min_step = -1
# visited = []
visited = [ [False]*W for _ in range(H) ]
visited[0][0] = True

while q:
  r,c,step = q.popleft()
  # visited.append((r,c))
  # visited[r][c] = True

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc]: continue
    # if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    visited[r][c] = True
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )


### FIXED CODE ###

import sys
readline = sys.stdin.readline
from collections import deque
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  # row = list(input())
  row = readline().rstrip()
  blocks += row.count("#")
  matrix.append(row)

q = deque([(0,0,0)])
min_step = -1
# visited = []
visited = [ [False]*W for _ in range(H) ]
visited[0][0] = True

while q:
  r,c,step = q.popleft()
  # visited.append((r,c))
  # visited[r][c] = True

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc] or (nr,nc,step+1) in q: continue
    # if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    visited[r][c] = True
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )
### BUGGY CODE ###

x = int(input())
import math
a = -(-360//x)
b = math.gcd(a-(360%a),360)
info = []
while True:
    tem = math.gcd(b-(360%b),360)
    info.append(tem)
    if tem == 0:
        break
ans = a*(360//b)
for i in info:
    ans *= i

print(ans)

### FIXED CODE ###

x = int(input())
b = 1
while (360*b%x) != 0:
    b += 1

print(360*b//x)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    for j in range((n-r*i)//g+1):
        if n - r*i - g*j < 0:
            continue
        if (n - r*i - g*j)%b == 0:
            ans += 1
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    for j in range((n-r*i)//g+1):
        if (n - r*i - g*j)%b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
s = input()

dp = np.zeros([n+1, n+1])

for l1_r in range(1,n):
    for l2_r in range(l1_r+1, n+1):
        if(s[l1_r-1] == s[l2_r-1]):
            temp = dp[l1_r-1][l2_r-1]
            if( (l2_r - l1_r) > temp):
                  temp += 1
        else:
            temp = 0
        dp[l1_r][l2_r] = temp


print(int(dp.max()))


### FIXED CODE ###

# import numpy as np

n = int(input())
s = input()

# dp = np.zeros([n+1, n+1])
dp = [0] * (n+1)

for dif in range(1,n):
    count = 0
    t_max = 0
    for l1_r in range(0, n-dif):
        if(s[l1_r] == s[l1_r + dif]):
            count += 1
            t_max = max(count, t_max)
            if( count == dif):
                dp[dif] = count
                break
        else:
            count = 0
    dp[dif] = t_max

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

# 累積和と包除原理でいけるんですか？
# [(0, 8, 136), (0, 12, 323), (1, 10, 204), (2, 2, 34), (5, 7, 119), (6, 8, 85), (6, 12, 272), (10, 11, 187)]
# [(0, 8, 136), (0, 12, 323), (1, 2, 34), (4, 7, 119), (5, 8, 85), (5, 12, 272), (9, 9, 136), (9, 11, 187)]

n, m = map(int, input().split())
arr = list(map(int, input().split()))
ruiseki_arr = [0] * n
ruiseki_arr[0] = arr[0]
for i in range(1, n):
    ruiseki_arr[i] = ruiseki_arr[i - 1] + arr[i]
ans = 0
ans_arr = []
for i in range(n):
    for j in range(i, n):
        if i > 0:
            target = ruiseki_arr[j] - ruiseki_arr[i - 1]
        elif i == j:
            target = arr[i]
        else:
            target = ruiseki_arr[j]
        if target % m == 0:
            # print("----yay?----")
            # print("i, j = {}, {}, target ={}".format(i, j, target))
            # ans_arr.append((i, j, target))
            ans += 1
print(ans)

### FIXED CODE ###

# AGC023Aたらいう地獄みたいに難しいやつのさらに上を行く地獄

n, m = map(int, input().split())
arr = list(map(int, input().split()))
b = [0]
d = {0: 1}
for i in range(n):
    b.append(b[i] + arr[i])
    if b[i + 1] % m in d:
        d[b[i + 1] % m] += 1
    else:
        d[b[i + 1] % m] = 1
ans = 0
for _, v in d.items():
    ans += (v * (v - 1)) // 2
print(ans)
### BUGGY CODE ###

K = int(input())

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(i,j,k)

print(ans)


### FIXED CODE ###

K = int(input())

import math

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        a = math.gcd(i, j)
        for k in range(1, K+1):
            ans += math.gcd(a,k)

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

n=int(input())
s=input()
st=[str(i).zfill(3)for i in range(1000)]
dp=[0]*1000
for i in s:
  for j in range(1000):
    if dp[j]<3:
      if st[j][dp[j]]==i:dp[j]+=1
print(dp.count(3))

### FIXED CODE ###

n=int(input())
s=input()
st=[str(i).zfill(3)for i in range(1000)]
dp=[0]*1000
for i in s:
  for j in range(1000):
    if dp[j]<3:
      if st[j][dp[j]]==i:dp[j]+=1
print(dp.count(3))
### BUGGY CODE ###

H,W = map(int,input().split())
A = ['' for i in range(H)]
colors = [[-2 for j in range(W)] for i in range(H)]
q = []
for i in range(H):
    A[i] = list(input())
    for j,color in enumerate(A[i]):
        colors[i][j] = 0 if color == '#' else -1
        if '#' == color:
            q.append([i,j,0])
# for i in colors:
#     print(i)
mx = 0
direction = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    # print(q)
    tmp = [y,x,op] = q.pop(0)
    mx = max(mx,op)
    if colors[y][x] >= 0 and mx > 0: continue
    colors[y][x] = op
    for [dx,dy] in direction:
        ny,nx = y + dy , x + dx
        if  0 <= ny and ny < H and 0 <= nx and nx < W:
            if A[ny][nx] == '#' or colors[ny][nx] >= 0:
                continue
            q.append([ny,nx,op+1])
print(mx)

### FIXED CODE ###

from sys import stdin
from collections import deque
def main():
    readline = stdin.readline
    H,W = map(int,readline()[:-1].split())
    A = ['' for i in range(H)]
    visited = [[False] * W for i in range(H)]
    q = deque()
    for i in range(H):
        A[i] = readline()[:-1]
        # print(A[i])
        for j,color in enumerate(A[i]):
            if '#' == color:
                q.append([i,j,0])
                visited[i][j] = True
            # for i in visited:
            #     print(i)
    mx = 0
    direction = [[1,0],[0,1],[-1,0],[0,-1]]
    op = -1
    while len(q) > 0:
        # print(q)
        tmp = [y,x,op] = q.popleft()
        # print(tmp)
        mx = mx if mx > op else op
        for [dx,dy] in direction:
            ny,nx = y + dy , x + dx
            if  0 <= ny and ny < H and 0 <= nx and nx < W:
                if A[ny][nx] == '#' or visited[ny][nx] == True:
                    continue
                q.append([ny,nx,op+1])
                visited[ny][nx] = True
    print(op)

main()
### BUGGY CODE ###

L, R = [int(i) for i in input().split()]
num_list = []
for i in range(R-L):
  for j in range(R-L-i):
    x = (L + i)%2019
    y = (L + i + j + 1)%2019
    num = (x*y)%2019
    num_list.append(num)
print(min(num_list))

### FIXED CODE ###

L, R = [int(i) for i in input().split()]
num_list = []
if R-L > 2019:
  print(0)
else:
  for i in range(R-L):
    for j in range(R-L-i):
      x = (L + i)%2019
      y = (L + i + j + 1)%2019
      num = (x*y)%2019
      num_list.append(num)
  print(min(num_list))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(200000000)

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

l = [[] for i in range(n+1)]
for pi in ab:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])

def dfs(graph, start, oya):
    if start != 1:
        graph[start].remove(oya)
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs(graph, i, start)

dfs(l, 1, 1)

def dfs_2(graph, start, ans, x):
    ans[start] += x
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs_2(graph, i, ans, x)

ans = [0 for i in range(n+1)]
for p, x in px:
    dfs_2(l, p, ans, x)
        
for i in range(1, n+1):
    print(ans[i], end=' ')
print()

### FIXED CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]
 
l = [[] for i in range(n+1)]
for a, b in ab:  
    l[a].append(b)

value = [0 for i in range(n+1)]
for p, x in px:
    value[p] += x

stack = [1]
while stack:
    label = stack.pop()
    for i in l[label]:
        value[i] += value[label]
    stack += l[label]
        
print(*value[1:])
### BUGGY CODE ###

N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

import sys
sys.setrecursionlimit(10**8)
def dfs(v):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            ans[u] += ans[v]
            visited[u]=True
            dfs(u)
    return

visited = [False]*N
visited[0]= True
dfs(0)
print(*ans, sep=' ')

### FIXED CODE ###

N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

ans = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

from collections import deque

visited = [False]*N
d = deque([0])
while len(d)>0:
    v = d.popleft()
    visited[v]= True
    for u in edge[v]:
        if visited[u]==False:
            ans[u] += ans[v]
            visited[u]=True
            d.append(u)

print(*ans, sep=' ')
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
P = [set() for _ in range(N + 1)]
for a, b in AB:
    G[a].add(b)
    P[b].add(a)
for i in range(1, N):
    if len(P[i]) == 0:
        break


def bellman_ford(V, G, i):
    ans = [0] * V
    INF = float('inf')
    D = [INF] * V
    D[i] = 0
    for _ in range(1, V):
        update = False
        for p in range(1, V):
            for c in G[p]:
                if D[p] != INF and D[c] > D[p] - 1:
                    D[c] = D[p] - 1
                    ans[c] = p
                    update = True
        if not update:
            return ans
        if _ == V:
            return False


D = bellman_ford(N + 1, G, i)[1:]
[print(_) for _ in D]


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
count = [0] * (N + 1)
ans = [0] * (N + 1)
for a, b in AB:
    G[a].add(b)
    count[b] += 1
for i in range(1, N):
    if count[i] == 0:
        root = collections.deque([i])
        break
while root:
    p = root.popleft()
    for c in G[p]:
        count[c] -= 1
        if count[c] == 0:
            ans[c] = p
            root.append(c)
print(*ans[1:], sep='\n')
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

def mCn(m,n):
    return math.factorial(m)//math.factorial(n)//math.factorial(m-n)

ans = 0
for i in range(1,M):
    ans += (M-i)*N*N*i*(mCn(M*N-2,K-2))
    ans = ans % mod

for i in range(1,N):
    ans += (N-i)*M*M*i*(mCn(M*N-2,K-2))
    ans = ans % mod

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

def mCn(m,n):
    return math.factorial(m)//(math.factorial(n)*math.factorial(m-n)) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N1 = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N1 + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


ans = 0
for i in range(1,M):
    ans += (M-i)*N**2*i*(cmb(M*N-2,K-2,mod))
    if ans > mod:
        ans = ans % mod

for i in range(1,N):
    ans += (N-i)*M**2*i*(cmb(M*N-2,K-2,mod))
    if ans > mod:
        ans = ans % mod

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

def abc177_c():
    n = int(input())
    a = list(map(int, input().split(' ')))

    mod = 10 ** 9 + 7
    ans = 0

    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += ((a[i] % mod) * (a[j] % mod)) % mod

    ans = ans % mod
    print(ans)

if __name__ == '__main__':
    abc177_c()

### FIXED CODE ###

def abc177_c_2():
    n = int(input())
    a = list(map(int, input().split(' ')))

    mod = 10 ** 9 + 7
    ans = 0
    x = 0

    for i in range(n):
        ans = (ans + a[i] * x) % mod
        x = (x + a[i]) % mod

    print(ans)

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

def resolve():
    N = int(input())
    A = [int(i) for i in input().split()]
    if len(A) == 0:
        print(0)
        return
    As = set(A)
    ans = 0
    for a in As:
        cnt = A.count(a)
        if a <= cnt:
            ans += cnt - a
        else:
            ans += cnt
    print(ans)



resolve()


### FIXED CODE ###

def resolve():
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]
    dic = defaultdict(int)
    for a in A:
        dic[a] += 1
    ans = 0
    for k, v in dic.items():
        if k <= v:
            ans += v - k
        else:
            ans += v
    print(ans)


resolve()