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

def main():
    s = list(map(int, list(input())))
    n = len(s)
    dp = [1]
    mod = 998244353
    for i, c in enumerate(s):
        dp2 = [0]*(i+2)
        for r in range(i+1):
            if r+c > 0:
                dp2[r+c-1] = (dp2[r+c-1]+dp[r]) % mod
            if i+2-r-c > 0:
                dp2[r+c] += (dp2[r+c]+dp[r]) % mod
        dp = dp2
    for i in range(n):
        dp2 = [0]*(n-i)
        for r in range(n-i+1):
            if r > 0:
                dp2[r-1] = (dp2[r-1]+dp[r]) % mod
            if n-i-r > 0:
                dp2[r] = (dp2[r]+dp[r]) % mod
        dp = dp2
    print(dp[0] % mod)


main()

### FIXED CODE ###


def main():
    s = list(map(int, list(input())))
    n = len(s)
    dp = [1]
    mod = 998244353
    for i, c in enumerate(s):
        dp2 = [0]*(i+2)
        for r in range(i+1):
            if r+c > 0:
                dp2[r+c-1] = (dp2[r+c-1]+dp[r]) % mod
            if i+2-r-c > 0:
                dp2[r+c] += (dp2[r+c]+dp[r]) % mod
        dp = dp2
    for i in range(n):
        dp2 = [0]*(n-i)
        for r in range(n-i+1):
            if r > 0:
                dp2[r-1] = (dp2[r-1]+dp[r]) % mod
            if n-i-r > 0:
                dp2[r] = (dp2[r]+dp[r]) % mod
        dp = dp2
    print(dp[0] % mod)


main()
### BUGGY CODE ###

a,b,c=map(int,input().split())
l=0
for i in range(100000000):
    l=a*i
    if l%b==c:
        print("YES")
        exit()
print("NO")


### FIXED CODE ###

a,b,c=map(int,input().split())
l=0
for i in range(b+1):
    l=a*i
    if l%b==c:
        print("YES")
        exit()
print("NO")
### BUGGY CODE ###

from bisect import bisect
n,m=[int(i) for i in input().split()]
a=sorted([int(i) for i in input().split()])
hoge=sorted([[int(j) for j in input().split()] for _ in range(m)],key=lambda x:x[1])
for b,c in hoge[::-1]:
    line=bisect(a,c)
    a[0:min(line,b)]=[c]*min(line,b)
    a=sorted(a)
print(sum(a))

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
a=sorted([int(i) for i in input().split()])
bc=sorted([[int(i) for i in input().split()] for _ in range(m)],key=lambda x:x[1])[::-1]
d=[]
ans=0
for b,c in bc:
    d+=[c]*b
    if len(d)>=n:
        break
for i in range(n):
    try:
        #元のカード列と置き換えるカード列で大きい方を選ぶ
        ans+=max(a[i],d[i])
    except:
        ans+=a[i]
print(ans)
### BUGGY CODE ###

def main():
    import bisect
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(py)] * 2):
        d[i].append(j)

    for i in d:
        i.sort()

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = bisect.bisect_right(d[i], j)
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import bisect
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(py)] * 2):
        d[i].append(j)

    for i in d:
        i.sort()

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = bisect.bisect_right(d[i], j)
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


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

n, p = map(int, input().split())
s = input()
r = set()
last = 0
d = {0: 0}
total = 0
rem = 0
if p == 2:
    for i in range(0, len(s)):
        if int(s[i]) % 2 == 0:
            total += i + 1
    print(total)
elif p == 5:
    for i in range(0, len(s)):
        if int(s[i]) % 5 == 0:
            total += i + 1
    print(total)



else:
    power = 1
    for i in range(len(s) - 1, -1, -1):  # handling of 0's as n and rem
        n = int(s[i]) * power + rem
        power *= 10
        power = power % p
        rem = n % p
        if rem in d.keys():
            d[rem] += 1
        else:
            d[rem] = 1
        total += d[rem] - 1
    print(total + d[0])


### FIXED CODE ###

n, p = map(int, input().split())
s = input()
r = set()
last = 0
d = {0: 0}
total = 0
rem = 0
if p == 2:
    for i in range(0, len(s)):
        if int(s[i]) % 2 == 0:
            total += i + 1
    print(total)
elif p == 5:
    for i in range(0, len(s)):
        if int(s[i]) % 5 == 0:
            total += i + 1
    print(total)



else:
    power = 1
    for i in range(len(s) - 1, -1, -1):  # handling of 0's as n and rem
        n = int(s[i]) * power + rem
        power *= 10
        power = power % p
        rem = n % p
        if rem in d.keys():
            d[rem] += 1
        else:
            d[rem] = 1
        total += d[rem] - 1
    print(total + d[0])
### BUGGY CODE ###

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

if B < N:
    Max = int(A*(B-1)/B)
    for x in range(B,1+N):
        fx = int(A*x/B) - A * int(x/B)
        Max = max(Max,fx)
elif B == N:
    Max = int(A*(B-1)/B)
else:
    Max = int(A*N/B)
print(Max)


### FIXED CODE ###

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


if B < N:
    Max = int(A*(B-1)/B)
    X = int(N/B)
    fx = int(A*(B*X-1)/B) - A * int((B*X-1)/B)
    # Max = max(fx,Max)
    # for x in range(1,X):
    #     fx = int(A*x/B) - A * int(x/B)
    #     Max = max(Max,fx)
elif B == N:
    Max = int(A*(B-1)/B)
else:
    Max = int(A*N/B)
print(Max)
### BUGGY CODE ###

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    colors[a*N + b] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
cnt = 0
while Q and cnt < N-1:
    cur, prev, NG = Q.pop()
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
        cnt += 1
print(col)
for a, b in ed:
    print(colors[a*N + b])


### FIXED CODE ###

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    ed.append([a, b])

col = max(len(v) for v in adj)

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
while Q:
    cur, prev, NG = Q.pop()
    c = 0
    for nex in adj[cur]:
        if nex == prev:
            continue
        else:
            c += 1
        if c == NG:
            c += 1
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in ed:
    print(colors[a*N + b])
### BUGGY CODE ###

import collections

N = int(input())
num_list = list(input().split())
memo = [0]*(N+1)
memo_flg = [False]*(N+1)
c = collections.Counter(num_list)

def calc(k):
    target = num_list[k]
    num = int(target)
    if(memo_flg[num] is True):
        return memo[num]
    ans = 0
    
    test = dict(c)
    test[target] -= 1

    for i in test.keys():
        ans += (test[i]*(test[i]-1))//2
    memo[num] = ans
    return ans

[print(calc(i)) for i in range(N)]


### FIXED CODE ###

import collections

N = int(input())
num_list = list(map(int,input().split()))
memo = [0]*(N+1)
memo_flg = [False]*(N+1)
counter = [0] * (N+1)
counter_ans = [0] * (N+1)

for i in num_list:
    counter[i] += 1
for i in range(N+1):
    counter_ans[i] = (counter[i]*(counter[i]-1))//2

all_sum = sum(counter_ans)
def calc(k):
    num = num_list[k]
    
    if(memo_flg[num] is True):
        return memo[num]
    ans = 0
    
    wrong = counter_ans[num]
    c = counter[num]-1
    right = (c*(c-1))//2
    
    ans = all_sum - wrong + right
    memo[num] = ans
    memo_flg[num] = True
    return ans

[print(calc(i)) for i in range(N)]
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for r in range(N//R + 1):
    ball1 = N - R * r
    if ball1 >= 0:
        for g in range(N//G + 1):
            ball2 = ball1 - G * g
            if ball2 >= 0:
                if ball2 % B == 0:
                    cnt += 1

print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0
 
for r in range(N//R + 1):
    ball1 = N - R * r
    if ball1 >= 0:
        for g in range(N//G + 1):
            ball2 = ball1 - G * g
            if ball2 >= 0:
                if ball2 % B == 0:
                    cnt += 1
 
print(cnt)
### BUGGY CODE ###

# D
from collections import deque

# create graph
G = dict()
N, M = map(int, input().split())
for n in range(1, N+1):
    G[n] = dict()

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c

# value
values = [-1000000000*2000]*(N+1)
values[1] = 0
# BFS
inc_cnt = 0
d = deque([1])
while len(d) > 0:
    a = d.popleft()
    for b in G[a].keys():
        if values[b] < values[a] + G[a][b]:
            values[b] = values[a] + G[a][b]
            if b == N:
                inc_cnt += 1
            d.append(b)
    if inc_cnt > 50:
        break
if inc_cnt > 50:
    print('inf')
else:
    print(values[N])

### FIXED CODE ###

# D
from collections import deque

# create graph
G = dict()
G_inv = dict()
N, M = map(int, input().split())
for n in range(1, N+1):
    G[n] = dict()
    G_inv[n] = dict()

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G_inv[b][a] = c

# value
values = [-1000000000*2000]*(N+1)
values[1] = 0

reachable = [0]*(N+1)
reachable[N] = 1
# find reachble points
dr = deque([N])
while len(dr) > 0:
    b = dr.popleft()
    for a in G_inv[b].keys():
        if reachable[a] == 0:
            reachable[a] = 1
            dr.append(a)

# BFS
inc_cnt = 0
d = deque([1])
while len(d) > 0:
    a = d.popleft()
    for b in G[a].keys():
        if values[b] < values[a] + G[a][b] and reachable[b] == 1:
            values[b] = values[a] + G[a][b]
            inc_cnt += 1
            d.append(b)
    if inc_cnt > 2000:
        break
if inc_cnt > 1000:
    print('inf')
else:
    print(values[N])
### BUGGY CODE ###

import numpy as np
from operator import add
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
N=listA[0]
lis_0=[0]*N[0]
lis=listA[1]
for idx1,i in enumerate(lis):
    arr=np.array(lis)
    arr_=arr/i
    lis_=arr_.tolist()
    
    for idx,num in enumerate(lis_):
        if idx!=idx1:
            if num.is_integer(): lis_[idx]=1
            else: lis_[idx]=0
        else:lis_[idx]=0
    lis_0 = list(map(add, lis_, lis_0))
        
print(lis_0.count(0))

### FIXED CODE ###

## 動画見てアルゴリズムを知った
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;

lis=listA[1]
m=max(lis)
lis0=[0]*(m+1)
for i in lis:
    if lis0[i]!=2: 
        j=1
        while i*j<=m:
            lis0[i*j]+=1
            j+=1
            
count=0
for i in lis:
    if lis0[i]==1: count+=1
print(count)
### BUGGY CODE ###

from collections import defaultdict
from itertools import product


INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for (i, j) in E[v]: dist[v][(i, j)] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    for v in V:
        if dist[v][v] < 0: return None
    return dist

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = defaultdict(list)
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.': E[(i, j)].append((x, y)); E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    ans = max(ans, max(D.values()))
print(ans)

### FIXED CODE ###

from collections import deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)
### BUGGY CODE ###

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

xy = []

while N >= 2:
    if A[-2] > 0:
        y = A.pop()
        x = A[0]

        xy.append([x,y])

        A[0] = x-y

    else:
        while N >= 2:
            x = A.pop()
            y = A.pop(0)

            xy.append([x,y])

            A.append(x-y)
            N -= 1
        break
    
    N -= 1

print(A[0])
for x, y in xy:
    print(x,y)

### FIXED CODE ###

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

xy = [0]*(N-1)
idx = 0

n = A.pop()

for i in range(N-1):
    a = A.pop()
    if a > 0:
        xy[idx] = [A[0], a]
        A[0] -= a
    else:
        xy[idx] = [n, a]
        n -= a
        idx += 1
        for j in A:
            xy[idx] = [n, j]
            n -= j
            idx += 1
        break

    idx += 1

print(n)
for x, y in xy:
    print(x,y)
### BUGGY CODE ###

import sys
n, k = map(int, input().split())
s = input()
sList = [] #連続する1の数、0の数、1の数...と格納するリスト
switch = int(s[0])
num = 1
if int(s[0]) == 0:
  sList.append(0)
if n > 1:
  for i in range(1, n):
    if int(s[i]) == switch:
      num += 1
    else:
      sList.append(num)
      num = 1
      switch = int(s[i])
sList.append(num)
if len(sList) // 2 < k: #全部ひっくり返せる
  print(n)
  sys.exit()
elif len(sList) % 2 == 0: #最後が0の数で終わっている場合、1の数で終わらせる
  sList.append(0)
  
sMax = 0
for i in range(0, (len(sList)-2*k) // 2 + 1): #リストの2k+1個の部分和のうち、最大のものが答え
  s = sum(sList[2*i:2*i+2*k+1])
  if sMax < s:
    sMax = s
    
print(sMax)

### FIXED CODE ###

import sys
n, k = map(int, input().split())
s = input()
sList = [] #連続する1の数、0の数、1の数...と格納するリスト
switch = int(s[0])
num = 1
if int(s[0]) == 0:
  sList.append(0)
if n > 1:
  for i in range(1, n):
    if int(s[i]) == switch:
      num += 1
    else:
      sList.append(num)
      num = 1
      switch = int(s[i])
sList.append(num)
if len(sList) // 2 < k: #全部ひっくり返せる
  print(n)
  sys.exit()
elif len(sList) % 2 == 0: #最後が0の数で終わっている場合、1の数で終わらせる
  sList.append(0)
  
s = sum(sList[0:2*k+1])
sMax = s

for i in range(1, (len(sList)-2*k) // 2 + 1): #リストの2k+1個の部分和のうち、最大のものが答え
  s += - sList[2*i-2] - sList[2*i-1] + sList[2*i+2*k] + sList[2*i+2*k-1]
  if sMax < s:
    sMax = s
    
print(sMax)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = int(input())

    for n in range(1, N + 1):
        res = 0
        for x in range(1, int(pow(n, 0.5)) + 1):
            for y in range(x, int(pow(n, 0.5)) + 1):
                for z in range(y, int(pow(n, 0.5)) + 1):
                    if pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x == n:
                        if x == y == z:
                            res += 1
                        elif x == y or y == z or z == z:
                            res += 3
                        elif x != y != z:
                            res += 6
        print(res)


if __name__ == '__main__':
    resolve()

# t = n - pow(x, 2) - pow(y, 2) - x * y
# if t >= 1:

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())

    res = [0] * (n + 10)
    for x in range(1, int(pow(n, 0.5)) + 1):
        for y in range(1, int(pow(n, 0.5)) + 1):
            for z in range(1, int(pow(n, 0.5)) + 1):
                t = pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x
                if t <= n:
                    res[t] += 1

    for x in range(1, n + 1):
        print(res[x])


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

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]
 
sys.setrecursionlimit(1000000)
mod = 1000000007
 
def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    k = I()
    ans = 0
    for a in range(1,k+1):
        for b in range(1,k+1):
            g = gcd(a,b)
            for c in range(1,k+1):
                ans += gcd(g,c)
    print(ans)
    return
 
#Solve
if __name__ == "__main__":
    solve()

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]
 
sys.setrecursionlimit(1000000)
mod = 1000000007
 
def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    k = I()
    ans = 0
    for a in range(1,k+1):
        for b in range(1,k+1):
            g = gcd(a,b)
            for c in range(1,k+1):
                ans += gcd(g,c)
    print(ans)
    return
 
#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

s=input()
k=int(input())

def decompose(s):
    l = []
    N = len(s)
    i = 0
    while i < N:
        j = i
        while j <= N:
            l.append(s[i:j])
            j += 1
        i += 1
    l = list(set(l))
    l.sort()
    return l
print(decompose(s)[k])

### FIXED CODE ###

s=input()
k=int(input())

def decompose(s):
    l = []
    N = len(s)
    i = 1
    while i <= N:
        l.append(s[:i])
        i += 1
    l = list(set(l))
    l.sort()
    return l

def answer(slist,smin,k):
    indices = [i for i, x in enumerate(slist) if x == smin]
    ans = []
    for ind in indices:
        ans.extend(decompose(s[ind:min(ind+k,len(s))]))
    ans = list(set(ans))
    ans.sort()
    if len(ans) >= k:
        return ans[k-1]
    else:
        s_temp = slist.copy()
        k -= len(ans)
        for r in range(len(indices)):
            s_temp.remove(min(slist))
        smin = min(s_temp)
        j = answer(slist,smin,k)
        return j

s=answer(list(s),min(list(s)),k)
print(s)
### BUGGY CODE ###

def main():
    k, s = map(int, input().split())
    
    c = 0
    for x in range(k + 1):
        for y in range(k + 1):
            for z in range(k + 1):
                if x + y + z == s:
                    c += 1
    print(c)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    k, s = map(int, input().split())
    
    c = 0
    for x in range(k + 1):
        for y in range(k + 1):
            if 0 <= s - (x + y) <= k:
                c += 1
    print(c)


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

K,S = map(int,input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            sumn = x + y + z
            if sumn == S:
                ans += 1
print(ans)


### FIXED CODE ###

K,S = map(int,input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        sumn = S - (x + y)
        if sumn >= 0 and sumn <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys

def solve():
    N = int(input())
    print("0" + "\n", flush = True)
    a = input()
    basis = -1
    if a == "Vacant": return 0
    elif a == "Male": basis = 0
    else: basis = 1
    low, high = 0, N
    while high - low > 1:
        mid = (low + high) // 2
        print(str(mid) + "\n", flush = True)
        a = input()
        if a == "Vacant": break
        else:
            b = (0 if a == "Male" else 1)
            if (mid - basis) % 2 != (a ^ b):
                high = mid
            else:
                low = mid
                basis = b
    else:
        print(str(low) + "\n", flush = True)

    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

N = int(input())

print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    reference_state = s
    opposite_state = ("Male" if s == "Female" else "Female") 
    low, high = 0, N
    count = 1
    while count < 20:
        mid = (low + high)//2
        expected_state = (reference_state if mid % 2 == 0 else opposite_state)
        print(mid, flush = True)
        s = input()
        if s == "Vacant":
            break
        else:
            if s == expected_state: low = mid
            else: high = mid
            count += 1
### BUGGY CODE ###

n,m,k = map(int,input().split())
ans = 0
MOD = 10**9+7
for i in range(1,n):
    ans += i*(n-i)*(m**2)
for i in range(1,m):
    ans += i*(m-i)*(n**2)
from scipy.misc import comb
print((ans*comb(m*n-2,k-2,exact=True))%MOD)

### FIXED CODE ###

n,m,k = map(int,input().split())
ans = 0
mod = 10**9+7
max = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % 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
C = cmb(m*n-2,k-2,mod)
for i in range(1,n):
    ans += (i*(n-i)*(m**2))*C
for i in range(1,m):
    ans += (i*(m-i)*(n**2))*C
print(ans%mod)