Harryxun/stf_run huggingface dataset:
h, w = list(map(int, input().split()))
     
    s = []
    for i in range(h):
        line = input()
        s.append(line)
     
    ans = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                continue
            d = [[1<<10 for x in range(w)] for y in range(h)]
     
            stack = []
            stack.append((i, j))
            d[i][j] = 0
            while stack:
                y, x = stack.pop()
                if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                    d[y-1][x] = d[y][x] + 1
                    stack.append((y-1, x))
                if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                    d[y][x+1] = d[y][x] + 1
                    stack.append((y, x+1))
                if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                    d[y+1][x] = d[y][x] + 1
                    stack.append((y+1, x))
                if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                    d[y][x-1] = d[y][x] + 1
                    stack.append((y, x-1))
            ma = 0
            for y in range(h):
                for x in range(w):
                    if d[y][x] > ma:
                        ma = d[y][x]

            ans.append(ma)
    ans.sort()
    print(ans[-1])


### FIXED CODE ###

import collections
h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[False for x in range(w)] for y in range(h)]

        stack = collections.deque()
        stack.append((i, j, 0))
        d[i][j] = True
        while stack:
            y, x, score = stack.popleft()
            if y > 0 and s[y-1][x] == '.' and not d[y-1][x]:
                stack.append((y-1, x, score+1))
                d[y-1][x] = True
            if x < w-1 and s[y][x+1] == '.' and not d[y][x+1]:
                stack.append((y, x+1, score+1))
                d[y][x+1] = True
            if y < h-1 and s[y+1][x] == '.' and not d[y+1][x]:
                stack.append((y+1, x, score+1))
                d[y+1][x] = True
            if x > 0 and s[y][x-1] == '.' and not d[y][x-1]:
                stack.append((y, x-1, score+1))
                d[y][x-1] = True
            if score > ans:
                ans = score
print(ans)
n,k=map(int,input().split())
    l=[input().split() for _ in range(n)]
    w=[[0]*(k+1) for _ in range(k+1)]
    b=[[0]*(k+1) for _ in range(k+1)]
    for i in range(n):
        if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
            b[int(l[i][0])%k][int(l[i][1])%k]+=1
        else:
            w[int(l[i][0])%k][int(l[i][1])%k]+=1
     
    for i in range(1,k+1):
        b[0][i]+=b[0][i-1]
        b[i][0]+=b[i-1][0]
        w[0][i]+=w[0][i-1]
        w[i][0]+=w[i-1][0]
    for i in range(1,k+1):
        for j in range(1,k+1):
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
            w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]
     
    ans=0
    for i in range(k+1):
        for j in range(k+1):
            ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
            ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
    print(ans)

n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

for i in range(1,k+1):
    b[0][i]+=b[0][i-1]
    b[i][0]+=b[i-1][0]
    w[0][i]+=w[0][i-1]
    w[i][0]+=w[i-1][0]
for i in range(1,k+1):
    for j in range(1,k+1):
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]

ans=0
for i in range(k+1):
    for j in range(k+1):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

print(ans)
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

print(combinations_count(N, 2) + combinations_count(M, 2))

### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(abs(n - r)) * math.factorial(r))

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

print(combinations_count(N, 2) + combinations_count(M, 2))
#-*- coding: utf-8 -*-

n, m = map(int, raw_input().split())
mx = [] * n
for i in xrange(n):
	mx[i] = map(int, raw_input().split())

v = [0] * m
for i in xrange(m):
	v[i] = input()

for i in xrange(n):
	t = 0
	for j in xrange(m):
		t += mx[i][j] * v[j]
	print t

### FIXED CODE ###

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

n, m = map(int, raw_input().split())
t = [0] * m
mx = t * n
for i in xrange(n):
	mx[i] = map(int, raw_input().split())

v = [0] * m
for i in xrange(m):
	v[i] = input()

for i in xrange(n):
	t = 0
	for j in xrange(m):
		t += mx[i][j] * v[j]
	print t
w, h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
x = [x_i for x_i in range(w + 1)]
y = [y_i for y_i in range(h + 1)]
for l_e in l:
    if l_e[2] == 1:
        x = x[l_e[0]:]
    elif l_e[2] == 2:
        x = x[:l_e[0]]
    elif l_e[2] == 3:
        y = y[l_e[1]:]
    else:
        y = y[:l_e[1]]
print((x[-1] - x[0]) * (x[-1] - x[0]))

### FIXED CODE ###

w, h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
x = [x_i for x_i in range(w + 1)]
y = [y_i for y_i in range(h + 1)]
for l_e in l:
    if l_e[2] == 1:
        x = [i for i in x if i > l_e[0] - 1]
    elif l_e[2] == 2:
        x = [i for i in x if i < l_e[0] + 1]
    elif l_e[2] == 3:
        y = [i for i in y if i > l_e[1] - 1]
    else:
        y = [i for i in y if i < l_e[1] + 1]
print(0 if len(x) == 0 or len(y) == 0 else (x[-1] - x[0]) * (y[-1] - y[0]))
inp=list(map(int,input().split()))
S=inp[0]
B=inp[1]
R=inp[2]
ans=B+(S-B-A)
print(ans)

### FIXED CODE ###

inp=list(map(int,input().split()))
s=inp[0]
b=inp[1]
r=inp[2]
print(s//(b+r)*b+min(s%(b+r),b))
N = int(input())
x = [None for _ in range(N)]
y = [None for _ in range(N)]
h = [None for _ in range(N)]
hh = [0 for _ in range(N)]
flag = False
for i in range(N):
    x[i], y[i], h[i] = map(int, input().split())
for cx in range(0, 101):
    for cy in range(0, 101):
        for i in range(N):
            hh[i] = h[i] + abs(x[i] - cx) + abs(y[i] - cy)
            if hh[i] < 1:
                hh[i] = None
        if (min(hh) == max(hh)) and (min(hh) >= 1):
            print(cx, cy, hh[0])
            exit()

### FIXED CODE ###

N = int(input())
x = [None for _ in range(N)]
y = [None for _ in range(N)]
h = [None for _ in range(N)]
for i in range(N):
    x[i], y[i], h[i] = map(int, input().split())
    if h[i] > 0:
        a = [x[i], y[i], h[i]]
for cx in range(0, 101):
    for cy in range(0, 101):
        hh = a[2] + abs(a[0] - cx) + abs(a[1] - cy)
        flag = True
        for i in range(N):
            h_i = max(hh - abs(x[i] - cx) - abs(y[i] - cy), 0)
            if h_i != h[i]:
                flag = False
        if flag:
            print(cx, cy, hh)
            exit()
n = int(input())
a_list = list(map(int, input().split()))
q = int(input())

for i in range(q):
    b, c = map(int, input().split())
    newlist = a_list
    for j in range(n):
        if newlist[j] == b:
          newlist[j] = c
          ans = sum(newlist)
    print(ans)

### FIXED CODE ###

a = str(input())

if ord(a) < ord ("a"):
    print("A")
else:
    print("a")
N = int(input())
if N == 1:
    print('Hello World')
else if N == 2:
    a = input(input())
    b = input(input())
    print(a + b)

### FIXED CODE ###

N = int(input())
if N == 1:
    print('Hello World')
else :
    a = int(input())
    b = int(input())
    print(a + b)
# coding: utf-8
# Your code here!

N = int(input())

if N%2 != 0 : 
    print(0)
    
else : 
    n = 1
    while 2*(5**n) <= N : 
        n += 1
        
    global_cnt = 0
    
    for i in range(1, n) : 
        local_cnt = N // (2*(5**i))
        global_cnt += local_cnt
        
print(global_cnt)

### FIXED CODE ###

# coding: utf-8
# Your code here!

N = int(input())

if N%2 != 0 : 
    global_cnt = 0
else : 
    n = 1
    while 2*(5**n) <= N : 
        n += 1
        
    global_cnt = 0
    
    for i in range(1, n) : 
        local_cnt = N // (2*(5**i))
        global_cnt += local_cnt
        
print(global_cnt)
s = input()
find = False
for c in string.ascii_lowercase:
  if c not in s:
    print(c)
    find = True
    break
if not find:
  print('None')
  
    

### FIXED CODE ###

import string
s = input()
find = False
for c in string.ascii_lowercase:
  if c not in s:
    print(c)
    find = True
    break
if not find:
  print('None')
N=int(input())
ABC=[]
for i in range(N):
  l=list(map(int,input().split()))
  ABC=ABC+[l]
dp=[0,0,0]*N#dp[i][j]はi+1日目にアクティビティjを選んだ時の活動終了時の幸福量
for i in range(3):
  dp[0][i]=ABC[0][i]
for i in range(1,N):
  dp[i][1]=max(dp[i-1][2]+ABC[i][1],dp[i-1][0]+ABC[i][1])
  dp[i][0]=max(dp[i-1][1]+ABC[i][0],dp[i-1][2]+ABC[i][0])
  dp[i][2]=max(dp[i-1][1]+ABC[i][2],dp[i-1][0]+ABC[i][2])
ans=max(dp[N-1])
print(ans)

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
dplist=[0 for i in range(N)]
dplist[0]=0
dplist[1]=abs(H[1]-H[0])
for i in range(2,N):
  dplist[i]=min(dplist[i-1]+abs(H[i]-H[i-1]),dplist[i-2]+abs(H[i-2]-H[i]))
print(dplist[N-1])
X, Y = map(int, input().split())

if Y%2 == 1:
    print('No')
    exit()
else:
    if 2X <= Y <= 4*X:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

if Y%2 == 1:
    print('No')
    exit()
else:
    if 2*X <= Y <= 4*X:
        print('Yes')
    else:
        print('No')
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

MOD = 10**9 + 7

def mul(A):
    ret = 1
    for i in range(len(A)): ret = ret * A[i] % MOD
    return ret

if K==N:
    print(mul(A))
    exit()

POS, NEG = list(), list()
for i in range(len(A)):
    if A[i] < 0:
        NEG.append(A[i])
    else:
        POS.append(A[i])

POS.sort(reverse=True)
NEG.sort()

if len(POS)==0 and K%2==1: # must go negative
    print(mul(NEG[-K:]))
    exit()

ans = list()
while len(ans)<K:
    if len(NEG) <= 1:
        ans.append(POS.pop()) # no negative numbers to add
    elif len(POS) <= 1:
        if K-len(ans)>=2:
            ans.append(NEG[:K-len(ans)])
        else:
            ans.append(POS.pop())
    elif POS[0]*POS[1] > NEG[0]*NEG[1] or K-len(ans)==1:
        ans.append(POS.pop())
    else:
        ans.append(NEG.pop())
        ans.append(NEG.pop())

print(mul(ans))



### FIXED CODE ###

from collections import deque
rand = False
verbose = False

if rand:
    import random
    N, K = 200000, 10000
    A = random.choices(range(-10**9, 10**9), k=N)
else:
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

MOD = 10**9 + 7

def mul(A):
    ret = 1
    for i in range(len(A)):
        ret = (ret * A[i]) % MOD
#        print (ret)
    return ret

if K==N:
    print(mul(A))
    exit()

POS, NEG = list(), list()
for i in range(len(A)):
    if A[i] < 0:
        NEG.append(A[i])
    else:
        POS.append(A[i])

POS.sort(reverse=True)
NEG.sort()

if len(POS)==0 and K%2==1: # must go negative
    print(mul(NEG[-K:]))
    exit()

POS = deque(POS)
NEG = deque(NEG)

ans = list()
while len(ans)<K:
    if len(NEG) <= 1:
        if verbose: print('no more neg numbers')
        ans.append(POS.popleft()) # no negative numbers to add
    elif len(POS) <= 1:
        if verbose: print('no more pos numbers')
        if K-len(ans)>=2:
            ans.append(NEG.popleft())
            ans.append(NEG.popleft())
        else:
            ans.append(POS.popleft())
    elif POS[0]*POS[1] > NEG[0]*NEG[1] or K-len(ans)==1:
        if verbose: print('pos bigger')
        ans.append(POS.popleft())
    else:
        if verbose: print('neg biger')
        ans.append(NEG.popleft())
        ans.append(NEG.popleft())

print(mul(ans))
import copy
S=list(input())
S1 = "".join(S)
T=list(input())
T1 = "".join(T)
F = ["?"]*len(T)
F1 = "".join(F)
l =[]
M =[]
index =[]
B = copy.deepcopy(S)
while -1<S1.find(F1):
    a = S1.find(F1)
    index.append(a)
    B[a] ="a"
    S1="".join(B)
S1 ="".join(S)
for i in range(len(S)-len(T)+1):
    if S[i]==T[0]:
        l.append(i)
if 0<len(l):
    for i in l:
        c = S[i:len(T)+i]
        while "?" in c:
            c[c.index("?")] = T[c.index("?")]
        if c==T:
            A = copy.deepcopy(S)
            A[i:len(T)+i] = c
            while "?"in A:
                A[A.index("?")]="a"
            M.append(A)
else :
    for i in range(len(S)-len(T)+1):
        if S[i] =="?":
            c = S[i:len(T)+i]
        while "?" in c:
            c[c.index("?")] = T[c.index("?")]
        if c==T:
            A = copy.deepcopy(S)
            A[i:len(T)+i] = c
            while "?"in A:
                A[A.index("?")]="a"
            M.append(A)
if 0<len(index):
    for i in index:
        A = copy.deepcopy(S)
        A[i:len(T)+i] = T
        while "?"in A:
            A[A.index("?")]="a"
        M.append(A)
if 0<len(M):
    M.sort()
    print("".join(M[0]))
else:
    print("UNRESTORABLE")

### FIXED CODE ###

import copy
S=list(input())
S1 = "".join(S)
T=list(input())
T1 = "".join(T)
F = ["?"]*len(T)
F1 = "".join(F)
l =[]
M =[]
index =[]
B = copy.deepcopy(S)
for i in range(len(S)-len(T)+1):
    A = copy.deepcopy(S)
    c = A[i:len(T)+i]
    while "?" in c:
        c[c.index("?")] = T[c.index("?")]
    if c==T:
        A = copy.deepcopy(S)
        A[i:len(T)+i] = c
        while "?"in A:
            A[A.index("?")]="a"
        M.append(A)
if 0<len(M):
    M.sort()
    print("".join(M[0]))
else:
    print("UNRESTORABLE")
l = list(map(int, input().split))
l.sort()
l.reverse()
l.pop(0)
print(l[0]*l[1]/2)


### FIXED CODE ###

l = list(map(int, input().split()))
l.sort()
l.reverse()
l.pop(0)
print(l[0]*l[1]//2)
import numpy
a, b = map(int, input().split())
n = int(input())
l = sorted([list(map(int, input().split())) for _ in range(n)])
line = [0]*(max(l)[1]+2)
line[a] += 1
line[b] -= 1
for a, b in l:
    line[a] += 1
    line[b] -= 1
if list(numpy.cumsum(line)).count(2):
    print(1)
else:
    print(0)


### FIXED CODE ###

a, b = map(int, input().split())
n = int(input())
l = sorted([list(map(int, input().split())) for _ in range(n)])
line = [0]*1010
line[a] += 1
line[b] -= 1
for a, b in l:
    line[a] += 1
    line[b] -= 1
for i in range(1006):
    line[i+1] += line[i]
if line.count(2):
    print(1)
else:
    print(0)
import sys
from collections import defaultdict
readline = sys.stdin.readline
def solve(p, v, rs):
    als = G[v]
    cs = g[v]
    c = 0
    for u in als:
        if u in cs:
            c += solve(v, u, rs)
        elif u != p:
            if v < u:
                c += 1
            rs.add((min(u,v), max(u,v)))
    if p == None:
        return
    elif c%2 != 0:
        rs.add((v, p))
        return 0
    else:
        rs.add((p,v))
        return 1

N, M = map(int, readline().split())
if M %2 != 0:
    print(-1)
else:
    G = defaultdict(set)
    for v in range(M):
        a, b = map(int, readline().split())
        G[a].add(b)
        G[b].add(a)

    stack=[1]
    vs = set([1])
    g = defaultdict(set)
    counter = 1
    while True:
        v = stack.pop()
        for u in G[v]:
            if u in vs:
                continue
            vs.add(u)
            g[v].add(u)
            stack.append(u)
            counter += 1
        if counter == N:
            break
    rs = set()
    solve(None,1, rs)
    for r in rs:
        print(r[0], r[1])




### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
def solve(p, v, rs):
    als = G[v]
    cs = g[v]
    c = 0
    for u in als:
        if u in cs:
            c += solve(v, u, rs)
        elif u != p:
            if v < u:
                c += 1
            rs.add((min(u,v), max(u,v)))
    if p == None:
        return
    elif c%2 != 0:
        rs.add((v, p))
        return 0
    else:
        rs.add((p,v))
        return 1

N, M = map(int, readline().split())
if M %2 != 0:
    print(-1)
else:
    G = defaultdict(set)
    for v in range(M):
        a, b = map(int, readline().split())
        G[a].add(b)
        G[b].add(a)

    stack=[1]
    vs = set([1])
    g = defaultdict(set)
    counter = 1
    while True:
        v = stack.pop()
        for u in G[v]:
            if u in vs:
                continue
            vs.add(u)
            g[v].add(u)
            stack.append(u)
            counter += 1
        if counter == N:
            break
    rs = set()
    solve(None,1, rs)
    for r in rs:
        print(r[0], r[1])
from math import cos
A, B, H, M = map(int, input().split())
t = 30 * A - 6 * B
print((A**2 + B**2 - 2*a*b*cos(t) ** .5)


### FIXED CODE ###

from math import cos, radians
A, B, H, M = map(int, input().split())
t = 30 * (H + M / 60) - 6 * M
t = radians(t)
print((A**2 + B**2 - 2*A*B*cos(t)) ** .5)
def main():
    n, m = map(int, input().split())
    g = [[] for i in [0]*(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    def bfs(n, m, adj):
        visited = [0 for i in [0]*(n+1)]
        ans = 1
        for i in range(n+1):
            if visited[i]:
                continue
            Q = deque([i])
            temp = 1
            while Q:
                q = Q.popleft()
                visited[q] = 1
                link = adj[q]
                for j in link:
                    if visited[j]:
                        continue
                    visited[j] = 1
                    temp += 1
                    Q.append(j)
            ans = max(ans, temp)
        print(ans)  
    bfs(n, m, g)
 
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
 
    def find(target):
        if parent[target] < 0:
            return target
        else:
            parent[target] = find(parent[target])
            return parent[target]
 
    def is_same(x, y):
        return find(x) == find(y)
 
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return
        if parent[root_x] > parent[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_x] += parent[root_y]
        parent[root_y] = root_x

    def members(n, x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
 
    def get_size(x):
        return -parent[find(x)]
 
    def get_root():
        return [i for i, root in enumerate(parent) if root < 0]

    n, m = map(int, input().split())
    parent = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        union(a, b)
        # print(parent)
    ans = 0
    for i in range(n):
        ans = max(ans, get_size(i))
    print(ans)
    # 状況理解用
    # max_member = 0
    # for i in get_root():
    #     # print(i, members(n, i))
    #     max_member  = max(max_member, len(members(n, i)))
    # print(max_member)

if __name__ == '__main__':
    main()
n,s = (input().split())
n = int(n)
if n % 2 == 1:
    print("No")
else: 
    t = s[0 : n//2]
    if s[n//2: n] == t:
        print("Yes")
    else:
         print("No")

### FIXED CODE ###

n = input()
s = input()
n = int(n)
if n % 2 == 1:
    print("No")
else: 
    t = s[0 : n//2]
    if s[n//2: n] == t:
        print('Yes')
    else:
         print('No')
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)
n=int(input())
mat=[[] for i in range(n)]
group=[0]*n
group[0]=1
for i in range(n-1):
    u, v, w = map(int, input().split())
    mat[u-1].append((v-1, w))
    mat[v-1].append((u-1, w))
def C(kw, p, l):
    global group
    k, w = kw
    if w%2==1:
        p*=-1
    group[k]=p
    for kwi in mat[k]:
        if kwi[0]!=l:
            C(kwi, p, k)
for kwi in mat[0]:
    C(kwi, 1, 0)
for gi in group:
    if gi>0:
        print(1)
    else:
        print(0)
import math

x1,y1,x2,y2 = raw_input().split()

tei  = x2 - x1
taka = y2 - y1

if tei == taka:
    st = math.sqrt(2)
    answ = st * tei
    print answ
if tei != taka:
    answ = (tei*tei) + (taka*taka)
    print math.sqrt(answ)

### FIXED CODE ###

import math

x1,y1,x2,y2 = raw_input().split()

tei  = float(x2) - float(x1)
taka = float(y2) - float(y1)

if tei == taka:
    st = math.sqrt(2)
    answ = st * tei
    print answ
if tei != taka:
    answ = (tei*tei) + (taka*taka)
    print math.sqrt(answ)
A, op, B = (input()).split()
A = int(A)
B = int(B)
op = str("+", "-")
if op =="+":
    print(A + B)
elif op == "-":
    print(A - B)

### FIXED CODE ###

A, op, B = input().split()

if op =="+":
    print(int(A) + int(B))
elif op == "-":
    print(int(A) - int(B))
NN=str(input())
print("ABC"+N)

### FIXED CODE ###

N=str(input())
print("ABC"+N)
a, b = map(int, input().split())

if a > 13:
  return b
elif a < 6:
  return 0
else: 
  return b//2


### FIXED CODE ###

a, b = map(int, input().split())
 
if a < 6:
  print(0)
elif a <= 12:
  print(int(b/2))
else: 
  print(b)
N = int(input())
P = list(map(int, input().split()))
Q = P.copy()
cnt1 = 0
for i in range(N-1):
    if P[i] == i+1:
        tmp = P[i]
        P[i] = P[i+1]
        P[i+1] = tmp
        cnt1 += 1
if P[-1] == N:
    cnt1 += 1

cnt2 = 0
for i in range(N-1, 0, -1):
    if Q[i] == i+1:
        tmp = Q[i]
        Q[i] = Q[i-1]
        Q[i-1] = tmp
        cnt2 += 1
if Q[0] == 1:
    cnt2 += 1
print(min(cnt1, cnt2))


### FIXED CODE ###

x, t = map(int, input().split())
print(max(0, x-t))
n,m,k = map(int, input().split())
mod = 10**9+7
def cc(a,b):
  b = min(b,a-b)
  tot = 1
  for i in range(1,b+1):
    tot = (tot*(a-i+1)//i)%mod
    return tot
xans = 0
yans = 0
for i in range(1,n):
  xans+=i*(n-i)*m**2
  xans%=mod
for j in range(1,m):
  yans+=i*(m-i)*n**2
  yans%=mod
print((xans+yans)*cc(n*m-2,k-2)%mod)

### FIXED CODE ###

n,m,k = map(int, input().split())
n_ = n*m
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
  
x = sum(i*(n-i) for i in range(n))%mod
y = sum(i*(m-i) for i in range(m))%mod
ans = (x*m**2 + y*n**2)%mod*nCr(n*m-2,k-2)%mod
print(ans)