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

N, M, K = map(int, input().split())
inf = float('inf')
e = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a][b] = 1
    e[b][a] = 1


from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
G = csgraph_from_dense(e, null_value=inf)
D = floyd_warshall(G)

# b = [[-1] * N for _ in range(N)]
for _ in range(K):
    c, d = map(int,input().split())
    c -= 1
    d -= 1
    D[c][d] = inf
    D[d][c] = inf


# print(D)
ans = []
for i in range(N):
    a = 0
    for j in range(N):
        if D[i][j] != inf and D[i][j] > 1:
            a += 1
    ans.append(a)

print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 親の番号 根なら要素数(負の数)

    def find(self, x):
        """木の根を求める"""
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """xとyの属する集合を併合"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

uf = UnionFind(N)
ans = [0] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    ans[A] -= 1
    ans[B] -= 1

for i in range(N):
    ans[i] += uf.size(i) - 1

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        ans[C] -= 1
        ans[D] -= 1

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

import math

N = int(input())
ans = 0

for i in range(1,N+1):
  ans += int( i*( (N//i)+1 )*(N//i)/2 )
  
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
ans = 0

for i in range(1,N+1):
  ans += i*( (N//i)+1 )*(N//i)/2
  
print(int(ans))
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import Counter

def main():
    S = input()
    
    l = []
    base = 1
    for st in S[::-1]:
        l.append((int(st)*base)%2019)
        base *= 10
        
    cum = [0]
    
    for num in l:
        cum.append((cum[-1]+num)%2019)
    
    
    c = Counter(cum)
    
    ans = 0
    for it,num in c.items():
        ans += (num*(num-1))//2
    
    print(ans)    
    
    
    
    
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import Counter

def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = [0]

    for st in S[::-1]:
        num = int(st)
        MOD = (MOD_list[-1]+num*base)%P
        MOD_list.append(MOD)
        base *= 10
        base %= P

    c = Counter(MOD_list)
    for v in c.values():
        ans += (v*(v-1))//2
        
    print(ans)

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

MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

dp = [[0 for _ in range(13)] for __ in range(len(s))] 

if s[0] != "?":
    dp[0][int(s[0])] = 1
else:
    for j in range(10):
        dp[0][j] = 1

for i in range(1,len(s)):
    if s[i] != "?":
        for j in range(13):
            dp[i][(j * 10 + int(s[i])) % 13] = (dp[i][(j * 10 + int(s[i])) % 13] + dp[i-1][j]) % MOD
    else:
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] =  (dp[i][(j * 10 + k) % 13]+ dp[i-1][j]) % MOD

print(dp[len(s)-1][5] % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
 
s = str(input())
 
s = list(s)
 
cur = [0] * 13
 
if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1
 
for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD
 
print(cur[5] % MOD)
### BUGGY CODE ###

import numpy as np
N, M =map(int, input().split())
A = np.array(list(map(int, input().split())))
#print(A)
for i in range(M):
    maximum =  A.argmax()
    A[maximum] = A[maximum]/2
    #print(A)

A = np.trunc(A)
print(int(A.sum()))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
### BUGGY CODE ###

from itertools import combinations
import copy

h, w = map(int, input().split())

maze = [list("#"+input()+"#") for _ in range(h)]
res = [i for i in "#"*(w+2)]
maze.insert(0, res)
maze.append(res)




p = []
for y, l in enumerate(maze):
    for x, m in enumerate(l):
        if m == ".":
            p.append([y, x])


ans = []

for c in combinations(p, 2):
    sy, sx = c[0][0], c[0][1]
    gy, gx = c[1][0], c[1][1]

    temp_maze = copy.deepcopy(maze)
    temp_maze[sy][sx] = 0

    loc = [[sy, sx]]

    for k in range(1, (h+2)*(w+2)):
        next_loc = []
        for y, x in loc:
            for i, j in ([1,0], [-1,0], [0,1],[0,-1]):
                    if temp_maze[y+i][x+j] == '.':
                        temp_maze[y+i][x+j] = k
                        next_loc.append([y+i, x+j])
        loc = next_loc
        if [gy, gx] in loc:
            ans.append(k)
            

print(max(ans))

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
h += 2; w += 2
maze = "#" * w
for _ in range(h-2):
    maze += "#" + input() + "#"
maze += "#" * w

def bfs(start):
    INF = h*w+1
    dist = [INF] * (h*w)
    dist[start] = 0
    q = deque([start])
    while q:
        cur_loc = q.popleft()
        cur_val = dist[cur_loc]
        for move in (-1,1,w,-w):
            next_loc = cur_loc + move
            if maze[next_loc] == "#":
                continue
            next_val = cur_val + 1
            if next_val >= dist[next_loc]:
                continue
            dist[next_loc] = next_val
            q.append(next_loc)
    return max(x for x in dist if x < INF)

ans = max(bfs(start) for start in range(h*w) if maze[start] != "#")
print(ans)
### BUGGY CODE ###

n=input()
a=list(map(int,input().split()))
result=[]
i=0
while i<len(a):
  if len(a)%2!=0:
    if i%2==0:
      result=[a[i]]+result
    else:
      result=result+[a[i]]
  else:
    if i%2==0:
      result=result+[a[i]]
    else:
      result=[a[i]]+result
  i=i+1

print(*result)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=a[::-2]+a[N%2::2]
print(*b)
### BUGGY CODE ###

N = int(input())
f = 0
count = 0
for j in range(1,N+1):
    count = 0
    for i in range(1,int(j**0.5)+100):
        if j%i == 0:
            count +=1
    f = f + (j * count)
print(f)

### FIXED CODE ###

N = int(input())
count = 0
for i in range(1,N+1):
    t = N//i
    count += i * t*(t+1)/2
print(int(count))
### BUGGY CODE ###

s = input()
n = len(s)
t = ""

i = 0
while i < n-1:
    if s[i:i+2] == "BC":
        t += "D"
        i += 2
    else:
        t += s[i]
        i += 1

# print(t)

m = len(t)
i = 0
p = 0
ans = 0
while i < m:
    while i < m and (t[i] == "A" or t[i] == "D"):
        if t[i] == "A":
            p += 1
        else:
            ans += p
        i += 1
    p = 0
    i += 1

print(ans)

### FIXED CODE ###

s = input()
n = len(s)
A = []

i = 0
while i < n-1:
    if s[i:i+2] == "BC":
        A.append("D")
        i += 2
    else:
        A.append(s[i])
        i += 1

t = "".join(A)
# print(t)

m = len(t)
i = 0
p = 0
ans = 0
while i < m:
    while i < m and (t[i] == "A" or t[i] == "D"):
        if t[i] == "A":
            p += 1
        else:
            ans += p
        i += 1
    p = 0
    i += 1

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

X, Y, Z, K = input().split()
X = int(X)
Y = int(Y)
Z = int(Z)
K = int(K)
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
M = [len(A), len(B), len(C)]
if max(M) == len(A):
    if min(M) == len(B):
        P, Q, R = A, C, B
    else:
        P, Q, R = A, B, C
elif max(M) == len(B):
    if min(M) == len(C):
        P, Q, R = B, A, C
    else:
        P, Q, R = B, C, A
else:
    if min(M) == len(A):
        P, Q, R = C, B, A
    else:
        P, Q, R = C, A, B
PQ = []
for p in range(len(P)):
    for q in range(len(Q)):
        PQ.append(P[p] + Q[q])
PQ = sorted(PQ, reverse=True)
PQR = []
for pq in range(min(K, len(PQ))):
    for r in range(len(R)):
        PQR.append(PQ[pq] + R[r])
PQR = sorted(PQR, reverse=True)
for i in range(K):
    print(PQR[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

S = input()
ans = 0
def check_left(n, S):
    count = 0
    for i in reversed(range(0, n)):
        if S[i] == "<":
            count += 1
        else:
            break
    return count

def check_right(n, S):
    count = 0
    for i in range(n, len(S)):
        if S[i] == ">":
            count += 1
        else:
            break
    return count

for i in range(len(S)+1):
    ans += max(check_left(i, S), check_right(i, S))
    
print(ans)

### FIXED CODE ###

S = input()
N = len(S) + 1
 
A = [0] * N
 
if S[0] == '<':
    A[0] = 0

if S[-1] == '>':
    A[-1] = 0

for i in range(1, N-1):
    if S[i-1] == '>' and S[i] == '<':
        A[i] = 0

for i in range(N-1):
    if S[i] == '<':
        A[i+1] = A[i] + 1

for i in range(N-1)[::-1]:
    if S[i] == '>':
        A[i] = max(A[i], A[i+1] + 1)

print(sum(A))
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
s1=set()
s2=set()
uf=UnionFind(n+1)
for i in range(m):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a
  s1.add((a,b))
  uf.unite(a,b)
for j in range(k):
  c,d=map(int,input().split())
  if c>d:
    c,d=d,c
  s2.add((c,d))
ans=[]
for i in range(1,n+1):
  cnt=0
  for j in uf.members(i):
    x,y=i,j
    if x>y:
      x,y=y,x
    if not((x,y) in s1 or (x,y) in s2):
      cnt+=1
  ans.append(cnt-1)
print(*ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
uf=UnionFind(n+1)
cnt=[0]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  uf.unite(a,b)
  cnt[a]+=1
  cnt[b]+=1
for i in range(k):
  c,d=map(int,input().split())
  if uf.same(c,d):
    cnt[c]+=1
    cnt[d]+=1
ans=[]
for i in range(1,n+1):
  ans.append(uf.size(i)-cnt[i]-1)
print(*ans)
### BUGGY CODE ###

#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x)
#print(y)
F=0
S=0
for i in range(n):
    if x[i]<=y[i]:
        F+=1
    else:
        S+=1
if F<=S:
    print("Snuke")
else:
    print("Fennec")

### FIXED CODE ###

#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def DIJKSTRA(point,d):
    cost      = [float("inf")]*(n+1)
    Q         = []
    cost[point]=0
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append([b,1])
    else:
        d[a]=[[b,1]]
    if b in d.keys():
        d[b].append([a,1])
    else:
        d[b]=[[a,1]]
        
x=DIJKSTRA(1,d)[1:]
y=DIJKSTRA(n,d)[1:]
#print(x)
#print(y)
F=0
S=0
for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1
if F<=S:
    print("Snuke")
else:
    print("Fennec")
### BUGGY CODE ###

while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        C=[[9999 for x in range(m+1)] for y in range (m+1)]
        T=[[9999 for x in range(m+1)] for y in range (m+1)]
        for i in range(n):
            [a,b,c,t]=[int(x) for x in raw_input().split()]
            C[a][b]=c
            C[b][a]=c
            T[a][b]=t
            T[b][a]=t
        for i in range(1,m+1):
            C[i][i]=0
            T[i][i]=0
        for k in range(1,m+1):
            for i in range(1,m+1):
                for j in range(1,m+1):
                    if C[i][j]>C[i][k]+C[k][j]:
                        C[i][j]=C[i][k]+C[k][j]
                    if T[i][j]>T[i][k]+T[k][j]:
                        T[i][j]=T[i][k]+T[k][j]
        Q=int(raw_input())
        for i in range(Q):
            [p,q,r]=[int(x) for x in raw_input().split()]
            if r:
                print T[p][q]
            else:
                print C[p][q]

### FIXED CODE ###

while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        C=[[9999 for x in range(m+1)] for y in range (m+1)]
        T=[[9999 for x in range(m+1)] for y in range (m+1)]
        for i in range(n):
            [a,b,c,t]=[int(x) for x in raw_input().split()]
            C[a][b]=c
            C[b][a]=c
            T[a][b]=t
            T[b][a]=t
        for i in range(1,m+1):
            C[i][i]=0
            T[i][i]=0
        for k in range(1,m+1):
            for i in range(1,m+1):
                for j in range(i,m+1):
                    if C[i][j]>C[i][k]+C[k][j]:
                        C[i][j]=C[i][k]+C[k][j]
                        C[j][i]=C[i][k]+C[k][j]
                    if T[i][j]>T[i][k]+T[k][j]:
                        T[i][j]=T[i][k]+T[k][j]
                        T[j][i]=T[i][k]+T[k][j]
        Q=int(raw_input())
        for i in range(Q):
            [p,q,r]=[int(x) for x in raw_input().split()]
            if r:
                print T[p][q]
            else:
                print C[p][q]
### BUGGY CODE ###

from collections import Counter
 
n, k = map(int,input().split())
a = list(map(int,input().split()))
 
c = Counter(a)
l = len(c)
cnt = 0
if k < l:
    i = -1
    for _ in range(l-k):
        cnt += c.most_common()[i][1]
        i -= 1
print(cnt)

### FIXED CODE ###

from collections import Counter
import heapq
n, k = map(int,input().split())
a = list(map(int,input().split()))
c = Counter(a)
heapc = list(c.values())
heapq.heapify(heapc)
l = len(c)
cnt = 0
if k < l:
    for _ in range(l-k):
        cnt += heapq.heappop(heapc)
print(cnt)
### BUGGY CODE ###

n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
DP=[[0 for i in range(w_max+1)] for j in range(n)]
for i in range(w_max+1):
  if i>=W[0]:
    DP[0][i]=V[0]
for i in range(1,n):
  for j in range(w_max+1):
    if j>W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    elif j==W[i]:
      DP[i][j]=max(DP[i-1][j],V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(DP[n-1][w_max])

### FIXED CODE ###

n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
DP=[[0 for i in range(w_max+1)] for j in range(n)]
for i in range(w_max+1):
  if i>=W[0]:
    DP[0][i]=V[0]
for i in range(1,n):
  for j in range(w_max+1):
    if j>W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    elif j==W[i]:
      DP[i][j]=max(DP[i-1][j],V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(DP[n-1][w_max])
### BUGGY CODE ###


def main():
  from collections import defaultdict
  from collections import Counter
  
  n = int(input())
  a = list(map(int, input().split()))
  
  d = Counter(a)
  e = defaultdict(int)
  
  
  
  func = lambda x: x*(x-1)//2 if x>=2 else 0
  
  ppp = ''
  
  for x in a:
    get = e.get(x)
    if get == None:
      g = d[x] - 1
      tmp = d.copy()
      tmp.pop(x)
      h = list(tmp.values())
      h.append(g)
      i = list(map(func, h))
      ans = sum(i)
      e[x] = ans
      ppp += str(ans) + '\n'
    else:
      ppp += str(get) + '\n'
    
   
  print(ppp)
      
 
if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
  from collections import defaultdict
  from collections import Counter
  
  n = int(input())
  a = list(map(int, input().split()))
  
  d = Counter(a)
  e = defaultdict(int)
  
  func = lambda x: x*(x-1)//2 if x>=2 else 0
  v = list(d.values())
  base = sum(list(map(func, v)))
  
  for k,v in d.items():
    if v<=1:
      e[k] = base - 0
    else:
      e[k] = base - ( v*(v-1)//2 - (v-1)*(v-2)//2 )
    
  p = [str(e[x])+'\n' for x in a]
  q = ''.join(p)
  print(q)
      
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

from itertools import combinations
import numpy as np
n, k = map(int, input().split())
hs = []
for i in range(n):
    hs.append(int(input()))
def get_diff(x):
    return max(x) - min(x)
print(min(np.apply_along_axis(get_diff, 1, list((combinations(hs, k))))))

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
hs = []
for i in range(n):
    hs.append(int(input()))

if list(np.diff(hs)) == list(np.zeros(n-1, dtype=int)):
    print('0')
else:
    sorted_hs = np.sort(hs)
    try:
        print(min([min(np.diff(sorted_hs[i::k-1])) for i in range(k) if not len(sorted_hs[i::k-1]) == 1]))
    except:
        print('0')
### BUGGY CODE ###

from scipy.misc import comb

MAX = 10**9 + 7

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * comb(M*N-2, K-2, exact=True)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()


### FIXED CODE ###

MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = (M*N* ((M*(N+1)*(N-1))%MAX + (N*(M+1)*(M-1)) % MAX)) % MAX
    disSum *= mod_inv(6, MAX) % MAX
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

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

N=int(input())
lst=set()
for i in range(1,N+1):
    lst.add(i)
    if sum(lst)>=N:
        if sum(lst)==N:
            break
        else:
            lst.remove(sum(lst)-N)
for s in lst:
    print(s)


### FIXED CODE ###

N=int(input())
lst=set()
num=0
for i in range(1,N+1):
    lst.add(i)
    num+=i
    if num>=N:
        if num==N:
            break
        else:
            lst.remove(num-N)
            break
for s in lst:
    print(s)
### BUGGY CODE ###

def main():
    N = int(input())
    c = [0] * 4
    for num in map(int, input().split()):
        c[num] += 1
    dp = [[[0] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
    for i3 in range(c[3]+1):
        for i2 in range(c[2]+c[3]-i3+1):
            for i1 in range(c[1]+c[2]+c[3]-i2-i3+1):
                if i1 == i2 == i3 == 0:
                    continue
                tmp = N / (i1+i2+i3)
                if i1 > 0:
                    tmp += i1 * dp[i1-1][i2][i3] / (i1+i2+i3)
                if i2 > 0:
                    tmp += i2 * dp[i1+1][i2-1][i3] / (i1+i2+i3)
                if i3 > 0:
                    tmp += i3 * dp[i1][i2+1][i3-1] / (i1+i2+i3)
                dp[i1][i2][i3] = tmp

    print(dp[c[1]][c[2]][c[3]])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    c = [0] * 4
    for num in map(int, input().split()):
        c[num] += 1
    dp = [[[0] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
    for i3 in range(c[3]+1):
        for i2 in range(c[2]+c[3]-i3+1):
            for i1 in range(c[1]+c[2]+c[3]-i2-i3+1):
                try:
                    dp[i1][i2][i3] = (i1 * dp[i1-1][i2][i3] +
                                      i2 * dp[i1+1][i2-1][i3] +
                                      i3 * dp[i1][i2+1][i3-1] +
                                      N) / (i1+i2+i3)
                except IndexError:
                    continue
                except ZeroDivisionError:
                    continue

    print(dp[c[1]][c[2]][c[3]])


if __name__ == "__main__":
    main()