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

def main():
    import sys
    N = int(input())
    left = 0
    right = N - 1
    table = ["?"]*N
    print(left)
    sys.stdin.flush()
    le = input()
    if le == "Vacant":
        return
    table[left] = le
    print(right)
    sys.stdin.flush()
    ri = input()
    if ri == "Vacant":
        return
    table[right] = ri

    for i in range(20):
        c = (left + right) // 2
        print(c)
        sys.stdin.flush()
        s = input()
        if s == "Vacant":
            return
        table[c] = s
        if (c - le + 1) % 2 == 0 and table[left] != table[c]:
            right = c
        elif (ri - c + 1) % 2 == 0 and table[right] != table[c]:
            left = c
        elif (c - le + 1) % 2 == 1 and table[left] == table[c]:
            right = c
        elif (ri - c + 1) % 2 == 1 and table[right] == table[c]:
            left = c
        else:
            raise Exception


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    N = int(input())
    left = 0
    right = N
    table = ["?"]*N
    print(left)
    sys.stdin.flush()
    le = input()
    if le == "Vacant":
        return
    table[left] = le

    for i in range(20):
        c = (left + right) // 2
        print(c)
        sys.stdin.flush()
        s = input()
        if s == "Vacant":
            return
        table[c] = s
        if (c - left) % 2 == 0 and table[left] == table[c]:
            left = c
        elif (c - left) % 2 == 1 and table[left] != table[c]:
            left = c
        else:
            right = c


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


#import numpy as np
s = input()
n = int(input())
#qt = np.ones((n),dtype=np.int32)
#qf = np.zeros((n),dtype=np.int64)
#qc = [''] * n

mode = True
#mode = True : f1->s=c+s,f2->s=s+c
#mode = False : f1->s=s+c,f2->s=c+s

for i in range(n):
    qs = input()
    if len(qs) == 1:
        mode = not mode
        #s = s[::-1]
        #pass
    else:
        #qt[i] = 2
        #qf[i] = int(qs[1:-2])
        #qc[i] = qs[-1]
        if mode:
            if int(qs[2]) == 1:
                s = qs[4] + s
            else:
                s = s + qs[4]
        else:
            if int(qs[2]) == 1:
                s = s + qs[4]
            else:
                s = qs[4] + s
        
#print(mode)
if not mode:
    s = s[::-1]



#for i in range(n):
#    print(qt[i],qf[i],qc[i])

print(s)

### FIXED CODE ###


#import numpy as np
s = input()
n = int(input())
#qt = np.ones((n),dtype=np.int32)
#qf = np.zeros((n),dtype=np.int64)
#qc = [''] * n

mode = False
#mode = True : f1->s=c+s,f2->s=s+c
#mode = False : f1->s=s+c,f2->s=c+s

front = ''
back = ''
for i in range(n):
    qs = input()
    if len(qs) == 1:
        mode = not mode
        #s = s[::-1]
        #pass
    else:
        #qt[i] = 2
        #qf[i] = int(qs[1:-2])
        #qc[i] = qs[-1]
        if not mode:
            if int(qs[2]) == 1:
                front += qs[4]
                #s = qs[4] + s
            else:
                back += qs[4]
                #s = s + qs[4]
        else:
            if int(qs[2]) == 1:
                back += qs[4]
                #s = s + qs[4]
            else:
                front += qs[4]
                #s = qs[4] + s


#print(mode,front,back)
#hanten
if mode:
    print(back[::-1] + s[::-1] + front)
#no hanten
else:
    print(front[::-1] + s + back)
### BUGGY CODE ###

N = int(input())

lst = [list(map(int, input().split())) for i in range(N-1)]
ans = []
for i in range(N-1):
  t = lst[i][0] + lst[i][1]
  for j in range(i+1, N-1):
    if (t >= lst[j][1]):
      if (t % lst[j][2] == 0):
        t += lst[j][0]
      else:
        i = 1
        while (t >= lst[j][1] + (i * lst[j][2])):
          i += 1
        t = lst[j][1] + (i * lst[j][2]) + lst[j][0]
    else:
      t = lst[j][1] + lst[j][0]
  ans.append(t)
ans.append(0)

for i in ans:
  print(i)

### FIXED CODE ###

import math
N = int(input())
lst = [list(map(int, input().split())) for i in range(N-1)]
ans = []
for i in range(N-1):
  t = lst[i][0] + lst[i][1]
  for j in range(i+1, N-1):
    if (t >= lst[j][1]):
      if (t % lst[j][2] == 0):
        t += lst[j][0]
      else:
        n = math.ceil((t - lst[j][1]) / lst[j][2])
        t = lst[j][1] + lst[j][2] * n + lst[j][0]
    else:
      t = lst[j][1] + lst[j][0]
  ans.append(t)
ans.append(0)

for i in ans:
  print(i)
### BUGGY CODE ###

import bisect
from operator import itemgetter
n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1))
for i in range(m):
  b, c = BC[i]
  t = bisect.bisect_left(A, c)
  A[:min(b, t)] = [c]*min(b, t)
  A.sort()
print(sum(A))

### FIXED CODE ###

from operator import itemgetter
n, m = map(int, input().split())
A = [(1, i) for i in map(int, input().split())]
BC = [ tuple(map(int, input().split())) for _ in range(m) ]
XY = sorted(A + BC, reverse=True, key=itemgetter(1))
c = n
now = 0
ans = 0
while c > 0 and now < n+m:
  x, y = XY[now]
  t = min(c, x)
  ans += y*t
  c -= t
  now += 1
print(ans)
### BUGGY CODE ###


import math
from functools import reduce

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


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

### FIXED CODE ###

import math
from functools import reduce

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


K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            if i==j and j==k:
                ans=ans+gcd(i,j,k)
            elif i==j or j==k:
                ans=ans+3*gcd(i,j,k)
            else:
                ans=ans+6*gcd(i,j,k)
            
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb, tw
    return sum(dp(0)) % (10 ** 9 + 7)


print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb, tw
    return sum(dp(0)) % (10 ** 9 + 7)


print(main())
### BUGGY CODE ###

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


def to_ind(i, j):
    return i * w + j

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 9

graph = [[] for i in range(h * w)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "@":
            continue
        for dj in range(1, k + 1):
            if not(0 <= j + dj < w):
                break
            if s[i][j + dj] == "@":
                break
            graph[to_ind(i, j)].append(to_ind(i, j + dj))
            graph[to_ind(i, j + dj)].append(to_ind(i, j))
        for di in range(1, k + 1):
            if not(0 <= i + di < h):
                break
            if s[i + di][j] == "@":
                break
            graph[to_ind(i, j)].append(to_ind(i + di, j))
            graph[to_ind(i + di, j)].append(to_ind(i, j))   

visited = [INF] * (h * w)
visited[to_ind(x1 - 1, y1 - 1)] = 0
q = deque([to_ind(x1 - 1, y1 - 1)])
while q:
    v = q.pop()
    for nxt_v in graph[v]:
        if visited[nxt_v] <= visited[v] + 1:
            continue
        visited[nxt_v] = visited[v] + 1
        q.append(nxt_v)

if visited[to_ind(x2 - 1, y2 - 1)] == INF:
    print(-1)
else:
    print(visited[to_ind(x2 - 1, y2 - 1)])


### FIXED CODE ###

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


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(0, i1, j1)])
    while q:
        d, i, j = q.popleft()
        #if dist[i][j] < d:
        #    continue
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 > dist[nxt_i][nxt_j]:
                    break
                if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((dist[nxt_i][nxt_j], nxt_i, nxt_j))
    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(A, B + 1):
    if i < A + K or i > B - K:
        print(i)


### FIXED CODE ###

A, B, K = map(int, input().split())

for i in range(A, min(B + 1, A + K)):
    if i < A + K:
        print(i)

for i in range(max(B - K, A + K), B + 1):
    if i > B - K:
        print(i)
### BUGGY CODE ###

#!/usr/bin/python3

def main():
    N, W = map(int, input().split())

    dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

    for i in range(N):
        weight, value = map(int, input().split())

        for w in range(W + 1):
            if w < weight:
                dp[i+1][w] = dp[i][w]

            else:
                dp[i+1][w] = max(dp[i][w], dp[i][w-weight] + value)

    print(dp[-1][-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3

import numpy as np
def main():
    N, W = map(int, input().split())

    dp = np.zeros((N+1, W+1), dtype='uint64')

    for i in range(N):
        weight, value = map(int, input().split())

        dp[i+1][:weight] = dp[i][:weight]
        dp[i+1][weight:] = np.maximum(dp[i][weight:], dp[i][:-weight] + value)

    print(dp[-1][-1])

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

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
D_list = np.array([_i() for _ in range(N)])
idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = {}
for i, j in enumerate(idx):
    mapping[i] = j+1

# 解説を参考に実装
# Dのスコアが大きい方から小さい方へ伸びる有向エッジとみなす
# valueはノードから出ている有向エッジを切った場合の部分木の大きさ
nodes = {i: 1 for i in range(N)}
ans = []
cost = [[0, 1] for _ in range(N)]
# 葉っぱから見て，[エッジにたどり着くまでのコスト, 自分も含めた子ノードの数]
for i in range(N-1, 0, -1):
    d = sorted_D[i]
    sub = nodes[i]
    target = d + 2*sub - N
    # print(target, sorted_D[:i])
    cand = np.searchsorted(sorted_D[:i], target)
    if cand == i or sorted_D[cand] != target:
        print(-1)
        exit()
    else:
        ans.append((mapping[i], mapping[cand]))
        nodes[cand] += nodes[i]
        cost[cand][0] += (cost[i][0] + cost[i][1])
        cost[cand][1] += cost[i][1]

# 1番目のノードについてチェック
if cost[0][0] != sorted_D[0]:
    print(-1)
    exit()
else:
    for a in ans:
        print(a[0], a[1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
D_list = np.array([_i() for _ in range(N)])
idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = []
for j in idx:
    mapping.append(j+1)

# 解説を参考に実装
# Dのスコアが大きい方から小さい方へ伸びる有向エッジとみなす
# valueはノードから出ている有向エッジを切った場合の部分木の大きさ
nodes = [1] * N
ans = []
cost = [[0, 1] for _ in range(N)]
# 葉っぱから見て，[エッジにたどり着くまでのコスト, 自分も含めた子ノードの数]
for i in range(N-1, 0, -1):
    d = sorted_D[i]
    sub = nodes[i]
    target = d + 2*sub - N
    cand = np.searchsorted(sorted_D[:i], target)
    if (sorted_D[cand] != target) or (cand == i):
        print(-1)
        exit()
    else:
        ans.append((mapping[i], mapping[cand]))
        nodes[cand] += nodes[i]
        cost[cand][0] += (cost[i][0] + cost[i][1])
        cost[cand][1] += cost[i][1]

# 1番目のノードについてチェック
if cost[0][0] != sorted_D[0]:
    print(-1)
    exit()
else:
    for a in ans:
        print(a[0], a[1])
### BUGGY CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 5000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 50))
    if ans < t:
      ans = t

print(ans)


### FIXED CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 1000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 500))
    if ans < t:
      ans = t

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

n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
town=[0]
i=0
while True:
  idx=town[-1]
  if a[idx] in town:
    s=a[idx]
    i+=1
    break
  else:
    i+=1
    town.append(a[idx])
if i!=n:
  idp=town.index(s)
  chain=len(town[:idp])
  cycle=len(town[idp:])
  if k<=chain:
    print(town[k]+1)
  else:
    p=(k-chain)%cycle + chain
    print(town[p]+1)
else:
  print(town[k%n]+1)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
town=[0]
set={0}
i=0
while True:
  idx=town[-1]
  if a[idx] in set:
    s=a[idx]
    i+=1
    break
  else:
    i+=1
    town.append(a[idx])
    set.add(a[idx])
if i!=n:
  idp=town.index(s)
  chain=len(town[:idp])
  cycle=len(town[idp:])
  if k<=chain:
    print(town[k]+1)
  else:
    p=(k-chain)%cycle + chain
    print(town[p]+1)
else:
  print(town[k%n]+1)
### BUGGY CODE ###

from fractions import gcd
import sys

input = sys.stdin.readline

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

MOD = 10 ** 9 + 7


def lcm(a, b):
    return a * b // gcd(a, b)


l = A[0]
for i in range(1, N):
    l = lcm(l, A[i])

res = 0
for a in A:
    res = (res + l // a) % MOD

print(res)


### FIXED CODE ###

from fractions import gcd
import sys

input = sys.stdin.readline

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

MOD = 10 ** 9 + 7


def lcm(a, b):
    return a * b // gcd(a, b)


l = A[0]
for a in A:
    l = lcm(l, a)

res = 0
for a in A:
    res = (res + (l * pow(a, MOD - 2, MOD)) % MOD) % MOD
    # res = (res + l // a) % MOD

print(res)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
amax =max(A)
amin =min(A)
cntm = A.count(amin - 1)
cntz = A.count(amin)
cntp = A.count(amin + 1)
ans = cntm + cntz + cntp
for i in range(amin + 1 , amax):
    cntm = cntz
    cntz = cntp
    cntp = A.count(i + 1)
    ans = max(ans,cntm + cntz + cntp)
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
lst =[0] * (10 ** 5 +10)
for i in A:
    if i > 0:
        lst[i - 1] += 1
    lst[i] += 1
    lst[i + 1] += 1
print(max(lst))
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
al = map(int, input().split())
h = []

for a in al:
    heapq.heappush(h, a)

for i in range(m):
    b, c = map(int, input().split())
    if len(h) >= n and c <= heapq.nlargest(n, h)[-1]:
        continue

    for j in range(b):
        heapq.heappush(h, c)




ans = sum(heapq.nlargest(n,h))
print(ans)

### FIXED CODE ###

import heapq


n, m = map(int, input().split())
al = map(int, input().split())
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = map(int, input().split())
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

        if len(h) >= n:
            break


ans = sum( heapq.nlargest(n, h) )
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# abc121_c

"""
Energy Drink Collector
"""
test = False


def main():
    """
    とにかく安い方からM本になるまで買い続ける。
    """
    N, M = map(int, input().split())
    l = []

    for _ in range(N):
        # [値段, 在庫本数] の2xNリストをつくる。
        l.append(list(map(int, input().split())))

    # 安い順に並べる
    l.sort()
    l_price = []

    # 安い順に、値段だけのリストをつくる。[100, 100, 100, 110, 120, 120, ...]
    for v in l:
        l_price.extend([v[0]] * v[1])
        # for _ in range(v[1]):
            # l_price.append(v[0])

    if test:
        print(l_price)

    # 買う。
    cost = sum(l_price[0:M])

    # 合計金額を出力
    print(cost)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# abc121_c

"""
Energy Drink Collector
"""
test = False


def main():
    """
    とにかく安い方からM本になるまで買い続ける。
    """
    N, M = map(int, input().split())
    l = []
    bottle = 0
    cost = 0

    for _ in range(N):
        # [値段, 在庫本数] の2xNリストをつくる。
        l.append(list(map(int, input().split())))

    # 安い順に並べる
    l.sort()
    # 安い店の在庫を全部買って、M本を超えたら中断

    for i in range(N):
        bottle += l[i][1]
        cost += l[i][0] * l[i][1]
        # 買いすぎた分を返品
        if bottle >= M:
            cost -= (bottle - M) * l[i][0]
            break

    # 合計金額を出力
    print(cost)


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

N,X=map(int,input().split())
A=N

X,N = sorted((X,N-X))
while N != X:
    A += 2*X
    X,N=sorted((X,N-X))
print(A+X)

### FIXED CODE ###

N,X=map(int,input().split())
A=N

X,N = sorted((X,N-X))
while N != X and X != 0:
    if N%X == 0:
        A += 2*(N//X-1)*X
        X,N=X,X
    else:
        A += 2*(N//X)*X
        X,N=sorted((X,N%X))
print(A+X)
### BUGGY CODE ###

n = int(input())
s = input()
num = [0 for i in range(n)]
for i in range(n):
    for j in range(0, i):
        if s[j] == "W":
            num[i] += 1
    for j in range(i+1, n):
        if s[j] == "E":
            num[i] += 1
    # print(num[i])
print(min(num))


### FIXED CODE ###

n = int(input())
s = input()
num = [0 for i in range(n)]
w = [0 for i in range(n)]
if s[0] == 'W':
    w[0] = 1
for i in range(1, n):
    if s[i] == 'W':
        w[i] = (w[i-1] + 1)
    else:
        w[i] = w[i-1]
e = [0 for i in range(n)]
if s[n-1] == 'E':
    e[n-1] = 1
for i in range(2, n+1):
    if s[n-i] == 'E':
        e[n-i] = (e[n-i+1] + 1)
    else:
        e[n-i] = e[n-i+1]
sol = [0 for i in range(n)]
sol[0] = e[0]
sol[n-1] = w[n-2]
for i in range(1, n-1):
    sol[i] = w[i-1] + e[i+1]
print(min(sol))
### BUGGY CODE ###

N = int(input())
S = input()
L = []
for k in range(N):
  w = S[:k].count('W')
  e = S[k:].count('E')
  L.append(w+e)
print(min(L))

### FIXED CODE ###

N = int(input())
S = input()
L = [S[1:].count('E'),S[:N].count('W')]
k = 0
w = 0
e = S[1:].count('E')
while (k <= N-2):
  if (S[k] == 'W' and S[k+1] == 'W'):
    w += 1
  elif (S[k] == 'W' and S[k+1] == 'E'):
    w += 1
    e -= 1
  elif (S[k] == 'E' and S[k+1] == 'W'):
    w += 0
  else:
    e -= 1
  L.append(e+w)
  k += 1
  
print(min(L))
### BUGGY CODE ###

h, w = map(int, input().split())
a=[]
for i in range(h):
  a.append([it == '#' for it in input()])
q=[]
for i in range(h):
  for j in range(w):
    if a[i][j]: q.append((i, j))
cnt = -1
while q:
  cnt += 1
  r = []
  for i, j in q:
    if i > 0 and not a[i-1][j]:
      a[i-1][j]=True
      r += [(i-1, j)]
    if i < h-1 and not a[i+1][j]:
      a[i+1][j]=True
      r += [(i+1, j)]
    if j > 0 and not a[i][j-1]:
      a[i][j-1]=True
      r += [(i, j-1)]
    if j < w-1 and not a[i][j+1]:
      a[i][j+1]=True
      r += [(i, j+1)]
  q=r
print(cnt)



### FIXED CODE ###

def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)
 
 
h, w = map(int, input().split())
f(h, w)
### BUGGY CODE ###

import numpy as np

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

a = np.array(list(map(int,input().split())))

for j in range(k):
    if j > 41:
        break

    new_a = np.zeros(n, dtype=int)

    for i, x in enumerate(a):
        new_a[i-x if i-x >= 0 else 0:i+x + 1] += 1
   
    a = new_a

print(*a)

### FIXED CODE ###

from itertools import accumulate

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

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

for j in range(k):
    if j > 41:
        break

    b = [0] * n

    for i in range(n):
        b[max(0, i - a[i])] += 1
        
        if i + a[i] + 1 < n:
            b[i + a[i] + 1] -= 1

    a = list(accumulate(b))

print(*a)
### BUGGY CODE ###

from functools import reduce
from operator import mul

MOD = 1000000007


def combination(n, r):
  r = min(n - r, r)
  if r == 0:
    return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1, r + 1))

  return over // under


def main():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD
  NNC = N * N * c % MOD
  MMC = M * M * c % MOD

  total = 0
  MAX = max(M, N)
  for xy1 in range(MAX - 1):
    for xy2 in range(xy1 + 1, MAX):
      if xy2 < M:
        # diff * n_x1 * n_x2 * combination
        total = (total + (xy2 - xy1) * NNC) % MOD

      if xy2 < N:
        total = (total + (xy2 - xy1) * MMC) % MOD

  print(total)


main()

### FIXED CODE ###

def mfactorial(n: int, mod: int) -> int:
  cache = mfactorial.__cache if hasattr(mfactorial, '__cache') else [1, 1]
  n_len = len(cache)
  n_new = n - n_len + 1
  if n_new > 0:
    cache = cache + ([0] * n_new)
    for i in range(n_len, n + 1):
      cache[i] = cache[i - 1] * i % mod
    mfactorial.__cache = cache

  return mfactorial.__cache[n]


def cmb(n, r, mod):
  result = mfactorial(n, mod)
  result *= pow(mfactorial(r, mod), mod - 2, mod) % mod
  result %= mod
  result *= pow(mfactorial(n - r, mod), mod - 2, mod) % mod
  result %= mod

  return result


def main():
  MOD = 10 ** 9 + 7

  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = cmb(N * M - 2, K - 2, MOD)

  X = 0
  Y = 0
  for i in range(M):
    X += (M - i) * i
  for i in range(N):
    Y += (N - i) * i

  total = (X * (N ** 2) + Y * (M ** 2)) % MOD * c % MOD
  print(total)


main()