Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)

Fixed submission:
n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))

index = [-1, -1, pi[n - 1][1], n, n]
ret = 0
for pos in range(n - 2, -1, -1):
    p, i = pi[pos]
    ii = bisect.bisect_left(index, i)
    ret += p * (index[ii - 1] - index[ii - 2]) * (index[ii] - i)
    ret += p * (i - index[ii - 1]) * (index[ii + 1] - index[ii])
    bisect.insort_left(index, i)
print(ret)

Fixed submission:
n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))
left  = {i: i - 1 for i in range(n)}
right = {i: i + 1 for i in range(n)}
left[-1] = -1
right[n] = n

ret = 0
for p, i in pi:
    ret += p * (left[i] - left[left[i]]) * (right[i] - i)
    ret += p * (i - left[i]) * (right[right[i]] - right[i])
    l, r = left[i], right[i]
    right[l] = r
    left[r] = l
print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))

index = [-1, -1, pi[n - 1][1], n, n]
ret = 0
for pos in range(n - 2, -1, -1):
    p, i = pi[pos]
    ii = bisect.bisect_left(index, i)
    ret += p * (index[ii - 1] - index[ii - 2]) * (index[ii] - i)
    ret += p * (i - index[ii - 1]) * (index[ii + 1] - index[ii])
    bisect.insort_left(index, i)
print(ret)

Fixed submission:
n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))
left  = {i: i - 1 for i in range(n)}
right = {i: i + 1 for i in range(n)}
left[-1] = -1
right[n] = n

ret = 0
for p, i in pi:
    ret += p * (left[i] - left[left[i]]) * (right[i] - i)
    ret += p * (i - left[i]) * (right[right[i]] - right[i])
    l, r = left[i], right[i]
    right[l] = r
    left[r] = l
print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))

index = [-1, -1, pi[n - 1][1], n, n]
ret = 0
for pos in range(n - 2, -1, -1):
    p, i = pi[pos]
    ii = bisect.bisect_left(index, i)
    ret += p * (index[ii - 1] - index[ii - 2]) * (index[ii] - i)
    ret += p * (i - index[ii - 1]) * (index[ii + 1] - index[ii])
    index.insert(ii, i)
print(ret)


Fixed submission:
n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))
left  = {i: i - 1 for i in range(n)}
right = {i: i + 1 for i in range(n)}
left[-1] = -1
right[n] = n

ret = 0
for p, i in pi:
    ret += p * (left[i] - left[left[i]]) * (right[i] - i)
    ret += p * (i - left[i]) * (right[right[i]] - right[i])
    l, r = left[i], right[i]
    right[l] = r
    left[r] = l
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(200000)

n, q = map(int, input().split())
edges = [[] for _ in range(n)]
counter = [0] * n
for a, b in [list(map(int, input().split())) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for p, x in [list(map(int, input().split())) for _ in range(q)]:
    counter[p - 1] += x

def dfs(p, i, v):
    counter[i] += v
    for j in edges[i]:
        if j != p:
            dfs(i, j, counter[i])

dfs(-1, 0, 0)

print(' '.join(str(c) for c in counter))

Fixed submission:
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
counter = [0] * n
for a, b in [list(map(int, input().split())) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for p, x in [list(map(int, input().split())) for _ in range(q)]:
    counter[p - 1] += x

ret = [-1] * n
ret[0] = counter[0]
q = [0]
index = 0
while index < len(q):
    i = q[index]
    index += 1
    for j in edges[i]:
        if ret[j] < 0:
            q.append(j)
            ret[j] = counter[j] + ret[i]

print(' '.join(str(c) for c in ret))
Buggy python submission (verdict: Runtime Error):
, m, p = map(int, input().split())
abcs = [list(map(int, input().split())) for _ in range(m)]
distance = [-100000 * n] * (n + 1)

distance[1] = 0
for _ in range(n + 1):
    for a, b, c in abcs:
        if distance[b] < distance[a] + c - p:
            distance[b] = distance[a] + c - p

ret = distance[n]
for _ in range(n + 1):
    for a, b, c in abcs:
        if distance[b] < distance[a] + c - p:
            distance[b] = distance[a] + c - p

print(-1 if ret != distance[n] else max(ret, 0))

Fixed submission:
n, m, p = map(int, input().split())
abcs = [list(map(int, input().split())) for _ in range(m)]
distance = [-1000000 * n] * (n + 1)

distance[1] = 0
reachable1 = set([1])
reachableN = set([n])
for _ in range(n + 1):
    for a, b, c in abcs:
        if distance[b] < distance[a] + c - p:
            distance[b] = distance[a] + c - p
        # 枝刈りが必要                                                                                                                                                                                                                
        if a in reachable1:
            reachable1.add(b)
        if b in reachableN:
            reachableN.add(a)

for a, b, c in abcs:
    if (distance[b] < distance[a] + c - p) and (a in reachable1) and (b in reachableN):
        print(-1)
        exit(0)

print(max(distance[n], 0))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[frommap[d][m]] for d in range(10)) % 1000000007 for m in range(13)]
    else:
        f = frommap[int(c)]
        dp = [dp[f[m]] for m in range(13)]

print(dp[5])

Fixed submission:
s = input()
dp = [1] + [0] * 12
for c in s:
    newdp = [0] * 13
    for d in range(10) if c == '?' else [int(c)]:
        for m in range(13):
            m2 = (m * 10 + d) % 13
            newdp[m2] = (newdp[m2] + dp[m]) % 1000000007
    dp = newdp
print(dp[5])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
dp = [1] + [0] * 12
for c in s:
    newdp = [0] * 13
    for d in range(10) if c == '?' else [int(c)]:
        for m in range(13):
            m2 = (m * 10 + d) % 13
            newdp[m2] = (newdp[m2] + dp[m]) % 1000000007
    dp = newdp
print(dp[5])

Fixed submission:
s = input()
dp = [1] + [0] * 12
for c in s:
    newdp = [0] * 13
    for d in range(10) if c == '?' else [int(c)]:
        for m in range(13):
            m2 = (m * 10 + d) % 13
            newdp[m2] = (newdp[m2] + dp[m]) % 1000000007
    dp = newdp
print(dp[5])
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)
    for v in range(n):
        for (i, r) in edges[v]:
            if r >= 0:
                print(v + 1, i + 1)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
def doit(a):
    c = {}
    for ai in a:
        c[ai] = c.get(ai, 0) + 1
    if len(c) > 3:
        return "No"
    k = list(sorted(c.keys()))
    if len(k) == 1:
        if k[0] == 0:
            return "Yes"
    if len(k) == 2:
        if k[0] == 0 and c[k[0]] * 2 == c[k[1]]:
            return "Yes"
    if len(k) == 3:
        if c[k[0]] == c[k[1]] == c[k[2]] and k[0] ^ k[1] == k[2]:
            return "Yes"
    return "No"

print(doit(sorted(a)))

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
def doit(a):
    c = {}
    for ai in a:
        c[ai] = c.get(ai, 0) + 1
    if len(c) > 3:
	return "No"
    k = list(sorted(c.keys()))
    if len(k) == 1:
	if k[0] == 0:
            return "Yes"
    if len(k) == 2:
	if k[0] == 0 and c[k[0]] * 2 == c[k[1]]:
            return "Yes"
    if len(k) == 3:
	if c[k[0]] == c[k[1]] == c[k[2]] and k[0] ^ k[1] == k[2]:
            return "Yes"
    return "No"

print(doit(sorted(a)))


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
def doit(a):
    c = {}
    for ai in a:
        c[ai] = c.get(ai, 0) + 1
    if len(c) > 3:
        return "No"
    k = list(sorted(c.keys()))
    if len(k) == 1:
        if k[0] == 0:
            return "Yes"
    if len(k) == 2:
        if k[0] == 0 and c[k[0]] * 2 == c[k[1]]:
            return "Yes"
    if len(k) == 3:
        if c[k[0]] == c[k[1]] == c[k[2]] and k[0] ^ k[1] == k[2]:
            return "Yes"
    return "No"

print(doit(sorted(a)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
total = sum(a)
ret = []
for i in range(n):
    s = 0
    for j in range(n // 2):
        s += a[(i + j * 2 + 1) % n] * 2
    ret.append(total - s)
print(" ".join(map(str, ret)))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
s = 0
for j in range(n // 2):
    s += a[(j * 2 + 1) % n] * 2
ret = []
ret.append(sum(a) - s)
for i in range(0, n - 1):
    ret.append((a[i] - ret[-1] // 2) * 2)
print(" ".join(map(str, ret)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(100000)

n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for a, b in [map(int, input().split()) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

mod = 1000000007
def dfs(v, p, c):
    ret = max(k - c, 0)
    used = 1 + (1 if p >= 0 else 0)
    for w in edges[v]:
        if w != p:
            ret = (ret * dfs(w, v, used)) % mod
            used += 1
    return ret
print(dfs(0, -1, 0))

Fixed submission:
import sys

sys.setrecursionlimit(100000)

n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for a, b in [map(int, input().split()) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

mod = 1000000007
def dfs(v, p, c):
    ret = max(k - c, 0)
    used = 1 + (1 if p >= 0 else 0)
    for w in edges[v]:
        if w != p:
            ret = (ret * dfs(w, v, used)) % mod
            used += 1
    return ret
print(dfs(0, -1, 0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(100000)

n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for a, b in [map(int, input().split()) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

mod = 1000000007
def dfs(v, p, c):
    children = len(edges[v]) - (1 if p >= 0 else 0)
    ret = max(k - c, 0)
    used = 1 + (1 if p >= 0 else 0)
    for w in edges[v]:
        if w != p:
            ret = (ret * dfs(w, v, used)) % mod
            used += 1
    return ret
print(dfs(0, -1, 0))


Fixed submission:
import sys

sys.setrecursionlimit(100000)

n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for a, b in [map(int, input().split()) for _ in range(n - 1)]:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

mod = 1000000007
def dfs(v, p, c):
    ret = max(k - c, 0)
    used = 1 + (1 if p >= 0 else 0)
    for w in edges[v]:
        if w != p:
            ret = (ret * dfs(w, v, used)) % mod
            used += 1
    return ret
print(dfs(0, -1, 0))
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 1000000007
cmb = [[1]]
for i in range(n + 1):
    cmb.append([1])
    for j in range(i):
        cmb[-1].append((cmb[-2][j] + cmb[-2][j + 1]) % mod)
    cmb[-1].append(1)
for i in range(1, k + 1):
    print((cmb[n - k + 1][i] * cmb[k - 1][i - 1]) % mod)

Fixed submission:
n, k = map(int, input().split())
mod = 1000000007
cmb = [[1]]
for i in range(n + 1):
    cmb.append([1])
    for j in range(i):
        cmb[-1].append((cmb[-2][j] + cmb[-2][j + 1]) % mod)
    cmb[-1].append(1)
for i in range(1, k + 1):
    if i > n - k + 1:
        print(0)
    else:
        print((cmb[n - k + 1][i] * cmb[k - 1][i - 1]) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    visited = set(q)
    while len(q) > 0:
        x, step = q.pop(0)
        if step == 3:
            v.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return v

v = set([s])
ret = 0
while True:
    olen = len(v)
    v = bfs(v)
    ret += 1
    if t in v:
        break
    if len(v) == olen:
        ret = -1
        break

print(ret)

Fixed submission:
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    index = 0
    ret = set()
    while len(q) > index:
        x, step = q[index]
        index += 1
        if step == 3:
            ret.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return ret

v = set([s])
visited = set([(s, 0)])
ret = 0
while True:
    v2 = bfs(v)
    if len(v2) == 0:
        ret = -1
        break
    ret += 1
    if t in v2:
        break
    v = v2

print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    visited = set(q)
    while len(q) > 0:
        x, step = q.pop(0)
        if step == 3:
            v.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return v

v = set([s])
ret = 0
while True:
    olen = len(v)
    v = bfs(v)
    ret += 1
    if t in v:
        break
    if len(v) == olen:
        ret = -1
        break

print(ret)

Fixed submission:
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    index = 0
    ret = set()
    while len(q) > index:
        x, step = q[index]
        index += 1
        if step == 3:
            ret.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return ret

v = set([s])
visited = set([(s, 0)])
ret = 0
while True:
    v2 = bfs(v)
    if len(v2) == 0:
        ret = -1
        break
    ret += 1
    if t in v2:
        break
    v = v2

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xtoy = {}
ytox = {}
for x, y in xy:
    if x not in xtoy:
        xtoy[x] = []
    xtoy[x].append(y)
    if y not in ytox:
        ytox[y] = []
    ytox[y].append(x)
ret = 0
while len(xtoy) > 0:
    q = [(next(iter(xtoy)), None)]
    xs = set()
    ys = set()
    while len(q) > 0:
        (x, y) = q.pop(0)
        if x is not None and x not in xs:
            xs.add(x)
            for y in xtoy.pop(x):
                q.append((None, y))
        if y is not None and y not in ys:
            ys.add(y)
            for x in ytox.pop(y):
                q.append((x, None))
    ret += len(xs) * len(ys)
print(ret - n)


Fixed submission:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xtoy = {}
ytox = {}
for x, y in xy:
    if x not in xtoy:
        xtoy[x] = []
    xtoy[x].append(y)
    if y not in ytox:
        ytox[y] = []
    ytox[y].append(x)
ret = 0
while len(xtoy) > 0:
    x = next(iter(xtoy))
    xs = set()
    ys = set()
    xs.add(x)
    q = [(x, None)]
    while len(q) > 0:
        (xx, yy) = q.pop(0)
        if xx is not None:
            for y in xtoy.pop(xx):
                if y not in ys:
                    ys.add(y)
                    q.append((None, y))
        if yy is not None:
            for x in ytox.pop(yy):
                if x not in xs:
                    xs.add(x)
                    q.append((x, None))
    ret += len(xs) * len(ys)
print(ret - n)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 1000000007
dp = [1] + [1] * m
for i in range(n):
    newdp = [1] + [0] * m
    for j in range(m):
        if s[i] == t[j]:
            newdp[j + 1] = (newdp[j] + dp[j + 1]) % mod
        else:
            newdp[j + 1] = (newdp[j] + dp[j + 1] - dp[j] + mod) % mod
    dp = newdp
print(dp[-1])

Fixed submission:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 1000000007
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(0, len(s) + 1):
    for j in range(0, len(t) + 1):
        ret = 0
        if i == 0:
            ret = 1
        elif j == 0:
            ret = 1
        else:
            ret = (dp[i][j - 1] + dp[i - 1][j]) % mod
            if s[i - 1] != t[j - 1]:
                ret = (ret + mod - dp[i - 1][j - 1]) % mod
        dp[i][j] = ret
print(dp[len(s)][len(t)])
Buggy python submission (verdict: Runtime Error):
n = int(input())
c = [tuple(map(int, input().split())) for _ in range(n)]
s = {}
for i in range(n):
    for j in range(i + 1, n):
        (p, q) = [b - a for a, b in zip(c[i], c[j])]
        s[(p, q)] = s.get((p, q), 0) + 1
print(n - max(s.values()))

Fixed submission:
n = int(input())
c = [tuple(map(int, input().split())) for _ in range(n)]
s = {(0, 0): 0}
for i in range(n):
    for j in range(n):
        if i != j:
            (p, q) = [b - a for a, b in zip(c[i], c[j])]
            s[(p, q)] = s.get((p, q), 0) + 1
print(n - max(s.values()))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

def trade(n, rate):
    dp = [0]
    for i in range(n):
        v = dp[i] + 1
        for ra, rb in rate:
            if i + 1 >= ra:
                v = max(v, dp[i + 1 - ra] + rb)
        dp.append(v)
    return dp[-1]

n = trade(n, [(ga, gb), (sa, sb), (ba, bb)])
n = trade(n, [(gb, ga), (sb, sa), (bb, ba)])
print(n)


Fixed submission:
n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

def trade(n, rate):
    dp = [0]
    r = sorted(rate, key=lambda r: float(r[0]) / float(r[1]))[0]
    p = n - 10000000
    if p // r[0] > 0:
        d = p // r[0]
        n -= d * r[0]
        dp = [d * r[1]]
    for i in range(n):
        v = dp[i] + 1
        for ra, rb in rate:
            if i + 1 >= ra:
                v = max(v, dp[i + 1 - ra] + rb)
        dp.append(v)
    return dp[-1]

n = trade(n, [(ga, gb), (sa, sb), (ba, bb)])
n = trade(n, [(gb, ga), (sb, sa), (bb, ba)])
print(n)
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
s = [input() for _ in range(h)]
sy = [0] * w
ret = 0
for y in range(h):
    seqx = 0
    seqy = 0
    for x in range(w):
        if s[y][x] == '.':
            if sy[x] == 0:
                yy = y
                while yy < h and s[yy][x] != '#':
                    yy += 1
                sy[x] = yy - y
            seqx += 1
            seqy = max(seqy, sy[x])
            ret = max(ret, seqx + seqy - 1)
        else:
            seqx = 0
            seqy = 0
            sy[x] = 0
print(ret)

Fixed submission:
h, w = map(int, input().split())
s = [input() for _ in range(h)]
sy = [0] * w
ret = 0
for y in range(h):
    seqx = 0
    seqy = 0
    for x in range(w):
        if s[y][x] == '.':
            if sy[x] == 0:
                yy = y
                while yy < h and s[yy][x] != '#':
                    yy += 1
                sy[x] = yy - y
            seqx += 1
            seqy = max(seqy, sy[x])
            ret = max(ret, seqx + seqy - 1)
        else:
            seqx = 0
            seqy = 0
            sy[x] = 0
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d)) % mod
    return (ret * n * n * cmb(n * m - 2, k - 2)) % mod

print((doit(n, m, k) + doit(m, n, k)) % mod)

Fixed submission:
n, m, k = map(int, input().split())

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d) * n * n * cmb(n * m - 2, k - 2)) % mod
    return ret

print((doit(n, m, k) + doit(m, n, k)) % mod)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d) * n * n * cmb(n * m - 2, k - 2)) % mod
    return ret

print((doit(n, m, k) + doit(m, n, k)) % mod)

Fixed submission:
n, m, k = map(int, input().split())

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d) * n * n * cmb(n * m - 2, k - 2)) % mod
    return ret

print((doit(n, m, k) + doit(m, n, k)) % mod)