Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
al = list(map(int,input().split()))
al = sorted(al)
ans = 0
while True:
   if m - 2*n + 1 >= 0:
      ans += sum(al) * 2 + 2*al[-1]*(n-1)
      al.pop()
      m = m - 2*n +1
      n -= 1
   else:
      l = []
      for a in al:
         l.append(a+al[-1])
         l.append(a+al[-1])
      l.pop()
      l = l[-m:]
      ans += sum(l)
      break

print(ans)



Fixed submission:
import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*3
lb = -1
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target

target = lb
rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)


if tmp > m:
    ans -= (tmp-m)*target
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

import math
import sys

n,k = map(int,input().split())
al = list(map(int,input().split()))
fl = list(map(int,input().split()))

al.sort()
fl.sort(reverse=True)

ub = max([a*f for a,f in zip(al, fl)])
lb = 0

while True:
    if ub == lb:
        print(lb)
        sys.exit()
    p = 0
    t = (ub + lb) // 2
    for a, f in zip(al, fl):
        p += max(a - t // f, 0)
    if p <= k:
        ub = t
    else:
        lb = t + 1

Fixed submission:
# coding: utf-8
# Your code here!

import math
import sys

n,k = map(int,input().split())
al = list(map(int,input().split()))
fl = list(map(int,input().split()))

al.sort()
fl.sort(reverse=True)

ub = max([a*f for a,f in zip(al, fl)])
lb = 0

while True:
    if ub == lb:
        print(lb)
        sys.exit()
    p = 0
    t = (ub + lb) // 2
    for a, f in zip(al, fl):
        p += max(a - t // f, 0)
    if p <= k:
        ub = t
    else:
        lb = t + 1

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

import math
import sys

n,k = map(int,input().split())
al = list(map(int,input().split()))
fl = list(map(int,input().split()))

al.sort()
fl.sort(reverse=True)

ub = max([a*f for a,f in zip(al, fl)])
lb = 0

while True:
    if ub == lb:
        print(lb)
        sys.exit()
    p = 0
    t = int((ub + lb) / 2)
    for a, f in zip(al, fl):
        p += max(math.ceil(a - t / f), 0)
    if p <= k:
        ub = t
    else:
        lb = t + 1

Fixed submission:
# coding: utf-8
# Your code here!

import math
import sys

n,k = map(int,input().split())
al = list(map(int,input().split()))
fl = list(map(int,input().split()))

al.sort()
fl.sort(reverse=True)

ub = max([a*f for a,f in zip(al, fl)])
lb = 0

while True:
    if ub == lb:
        print(lb)
        sys.exit()
    p = 0
    t = (ub + lb) // 2
    for a, f in zip(al, fl):
        p += max(a - t // f, 0)
    if p <= k:
        ub = t
    else:
        lb = t + 1

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

import numpy as np

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))

a.sort()
f.sort(reverse=True)

for i in range(k):
    ans = [i*j for i, j in zip(a, f)]
    a[np.argmax(ans)] -= 1
    
ans = [i*j for i, j in zip(a, f)]
print(max(ans))

Fixed submission:
# coding: utf-8
# Your code here!

import math
import sys

n,k = map(int,input().split())
al = list(map(int,input().split()))
fl = list(map(int,input().split()))

al.sort()
fl.sort(reverse=True)

ub = max([a*f for a,f in zip(al, fl)])
lb = 0

while True:
    if ub == lb:
        print(lb)
        sys.exit()
    p = 0
    t = (ub + lb) // 2
    for a, f in zip(al, fl):
        p += max(a - t // f, 0)
    if p <= k:
        ub = t
    else:
        lb = t + 1
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import math

n,m,l = map(int,input().split())
adj = [[float('inf') for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    if c <= l:
        adj[a-1][b-1] = c
        adj[b-1][a-1] = c
    
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start):
        num = len(adj)          # グラフのノード数
        dist = [[float('inf'), float('inf')] for i in range(num)] # 始点から各頂点までの最短距離を格納する
        
        dist[start] = (0, 0)
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, 0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, prov_fuel, src = heapq.heappop(q) # pop
            
            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf'):
                    if prov_fuel + cost <= l:
                        new_cost = prov_cost
                        new_fuel = prov_fuel + cost
                    else:
                        new_cost = prov_cost + 1
                        new_fuel = cost
                    if dist[dest][0] > new_cost or (dist[dest][0] == new_cost and dist[dest][1] > new_fuel):
                        dist[dest] = (new_cost, new_fuel)
                        heapq.heappush(q, (new_cost, new_fuel, dest))
                        
        return dist



ans = []
for i in range(n):
    ans.append(Dijkstra().dijkstra(adj, i))
q = int(input())
for _ in range(q):
    s,t = map(int,input().split())
    if ans[s-1][t-1][0] == float('inf'):
        print(-1)
    else:
        print(ans[s-1][t-1][0])

Fixed submission:
# coding: utf-8
# Your code here!

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

c = a - 2 * b
if c > 0:
    print(c)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

n = int(input())
ll = list(map(int,input().split()))

ll.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if ll[k] < ll[i] + ll[j]:
                ans += 1
print(ans)

Fixed submission:
# coding: utf-8
# Your code here!

n = int(input())
ll = list(map(int,input().split()))

ll.sort()
ans = 0
for i in range(n - 2):
    for j in range(i+1, n - 1):
        lb = j + 1
        ub = n - 1
        b = ll[i] + ll[j]
        if ll[lb] >= b:
            continue
        if ll[ub] < b:
            ans += ub - lb + 1
            continue
        while True:
            if ub == lb:
                ans += ub - j
                break
            t = (lb + ub) // 2 + 1
            if ll[t] < b:
                lb = t
            else:
                ub = t - 1
print(ans)

Buggy python submission (verdict: Runtime Error):
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> ll; 
    int n;
	cin >> n;
    for(int i=0; i<n; i++) {
    	int x;
    	cin >> x;
    	ll.push_back(x);
    }
    long long ans = 0;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            for(int k=j+1; k<n; k++) {
                if(ll[i] < ll[j] + ll[k] && ll[j] < ll[i] + ll[k] && ll[k] < ll[i] + ll[j]) {
                    ans += 1;
                }
            }
        }
    }
    cout << ans << '\n';
    
}

Fixed submission:
# coding: utf-8
# Your code here!

n = int(input())
ll = list(map(int,input().split()))

ll.sort()
ans = 0
for i in range(n - 2):
    for j in range(i+1, n - 1):
        lb = j + 1
        ub = n - 1
        b = ll[i] + ll[j]
        if ll[lb] >= b:
            continue
        if ll[ub] < b:
            ans += ub - lb + 1
            continue
        while True:
            if ub == lb:
                ans += ub - j
                break
            t = (lb + ub) // 2 + 1
            if ll[t] < b:
                lb = t
            else:
                ub = t - 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

n = int(input())
ll = list(map(int,input().split()))

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if ll[i] < ll[j] + ll[k] and ll[j] < ll[k] + ll[i] and ll[k] < ll[i] + ll[j]:
                ans += 1

print(ans)

Fixed submission:
# coding: utf-8
# Your code here!

n = int(input())
ll = list(map(int,input().split()))

ll.sort()
ans = 0
for i in range(n - 2):
    for j in range(i+1, n - 1):
        lb = j + 1
        ub = n - 1
        b = ll[i] + ll[j]
        if ll[lb] >= b:
            continue
        if ll[ub] < b:
            ans += ub - lb + 1
            continue
        while True:
            if ub == lb:
                ans += ub - j
                break
            t = (lb + ub) // 2 + 1
            if ll[t] < b:
                lb = t
            else:
                ub = t - 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))

bitdp = [[float('inf') for i in range(1<<n)] for i in range(m+1)]
   
bitdp[0][0] = 0

for i in range(m):
   for j in range(1<<n):
      bitdp[i+1][j] = min(bitdp[i][j], bitdp[i+1][j])
      bitdp[i+1][j|abl[i][1]] = min(bitdp[i][j] + abl[i][0], bitdp[i][j|abl[i][1]], bitdp[i+1][j|abl[i][1]])

if bitdp[-1][(1<<n)-1] == float('inf'):
   print(-1)
else:
   print(bitdp[-1][(1<<n)-1])

Fixed submission:
n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))

bitdp = [[float('inf') for i in range(1<<n)] for i in range(m+1)]
   
bitdp[0][0] = 0

for i in range(m):
   for j in range(1<<n):
      bitdp[i+1][j] = min(bitdp[i][j], bitdp[i+1][j])
      bitdp[i+1][j|abl[i][1]] = min(bitdp[i][j] + abl[i][0], bitdp[i][j|abl[i][1]], bitdp[i+1][j|abl[i][1]])

if bitdp[-1][(1<<n)-1] == float('inf'):
   print(-1)
else:
   print(bitdp[-1][(1<<n)-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))


ans = float("inf")
for i in range(2 ** m):
   bit = [0] * m
   for j in range(m):
       if ((i >> j) & 1):
           bit[j] = 1
   state = 0
   tmp = 0
   for j in range(m):
      if bit[j] == 1:
         state |= abl[j][1]
         tmp += abl[j][0]
   if state == (1 << n) - 1:
      ans = min(ans, tmp)

if ans == float("inf"):
   print(-1)
else:
   print(ans)
   

Fixed submission:
n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))

bitdp = [[float('inf') for i in range(1<<n)] for i in range(m+1)]
   
bitdp[0][0] = 0

for i in range(m):
   for j in range(1<<n):
      bitdp[i+1][j] = min(bitdp[i][j], bitdp[i+1][j])
      bitdp[i+1][j|abl[i][1]] = min(bitdp[i][j] + abl[i][0], bitdp[i][j|abl[i][1]], bitdp[i+1][j|abl[i][1]])

if bitdp[-1][(1<<n)-1] == float('inf'):
   print(-1)
else:
   print(bitdp[-1][(1<<n)-1])
Buggy python submission (verdict: Runtime Error):
import sys

A = list(map(int, input().split()))
a, b = A[0], A[1]
kazu = 0
kuti = 1
while True:
    if kuti >= b:
        print(kazu)
        sys.quit()
    kazu += 1
    kuti = kuti - 1 + a

Fixed submission:
import sys

A = list(map(int, input().split()))
a, b = A[0], A[1]
kazu = 0
kuti = 1
while True:
    if kuti >= b:
        print(kazu)
        sys.exit()
    kazu += 1
    kuti = kuti - 1 + a
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!


n,m,p = map(int,input().split())

el = []
for _ in range(m):
    a,b,c = map(int,input().split())
    el.append((a-1,b-1,c-p))
cost = [-float("inf") for _ in range(n)]
cost[0] = 0
for i in range(n+1):
    for j in range(m):
        e = el[j]
        if cost[e[1]] < cost[e[0]] + e[2]:
            cost[e[1]] = cost[e[0]] + e[2]
            if i == n:
                cost[e[1]] = float("inf")
              
if ans != cost[-1]:
    print(-1)
else:
    print(max(cost[-1], 0))
        

Fixed submission:
# coding: utf-8
# Your code here!


n,m,p = map(int,input().split())

el = []
for _ in range(m):
    a,b,c = map(int,input().split())
    el.append((a-1,b-1,c-p))
cost = [-float("inf") for _ in range(n)]
cost[0] = 0
for i in range(2*n):
    for j in range(m):
        e = el[j]
        if cost[e[1]] < cost[e[0]] + e[2]:
            cost[e[1]] = cost[e[0]] + e[2]
            if i >= n:
                cost[e[1]] = float("inf")
    if i == n-1:
        ans = cost[-1]
        
              
if ans != cost[-1]:
    print(-1)
else:
    print(max(ans, 0))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!
import copy 
import sys

sl = list(input())
n = len(sl)
hl = [1 for _ in range(n)]
log = []
newl = [0 for _ in range(n)]
for i in range(10**100):
    newl[0] = hl[1] if sl[1] == "L" else 0
    newl[-1] = hl[-2] if sl[-2] == "R" else 0
    for j in range(1,n-1):
        left = hl[j+1] if sl[j+1] == "L" else 0
        right = hl[j-1] if sl[j-1] == "R" else 0
        newl[j] = left + right
    if i % 2 == 1:
        if newl == log:
            for i in newl:
                print(i)
            sys.exit()
        log = copy.deepcopy(newl)
    hl = copy.deepcopy(newl)
        

Fixed submission:
# coding: utf-8
# Your code here!

sl = list(input())
n = len(sl)

ans_l = []
r_n = 0
l_n = 0
for s in sl:
    if s == "R":
        if l_n > 0:
            ans_l += [0] * (r_n - 1)
            ans_l += [l_n // 2 + (r_n + 1) // 2]
            ans_l += [r_n // 2 + (l_n + 1) // 2]
            ans_l += [0] * (l_n - 1)
            r_n = 0
            l_n = 0
        r_n += 1
    else:
        l_n += 1
ans_l += [0] * (r_n - 1)
ans_l += [l_n // 2 + (r_n + 1) // 2]
ans_l += [r_n // 2 + (l_n + 1) // 2]
ans_l += [0] * (l_n - 1)
for i in ans_l:
    print(i)
Buggy python submission (verdict: Runtime Error):
n = int(input())
al = list(map(int,input().split()))


from collections import defaultdict
dic = {}

for a in al:
    if a not in dic:
        dic[a] = 0
    dic[a] += 1
if dic[0] == n:
    print("Yes")
    exit()
if 0 in dic:
    if n % 3 == 0:
        if dic[0] == 2 * n // 3:
            print("Yes")
            exit()
if n % 3 != 0:
    print("No")
    exit()
else:
    if len(dic) == 3:
        if max(dic.values()) == n // 3:
            a = 0
            for i in dic:
                a ^= i
            if a == 0:
                print("Yes")
                exit()
print("No")




Fixed submission:
n = int(input())
al = list(map(int,input().split()))


from collections import defaultdict
dic = {}

for a in al:
    if a not in dic:
        dic[a] = 0
    dic[a] += 1
if 0 in dic:
    if dic[0] == n:
        print("Yes")
        exit()
if 0 in dic:
    if n % 3 == 0:
        if dic[0] == 1 * n // 3:
            print("Yes")
            exit()
if n % 3 != 0:
    print("No")
    exit()
else:
    if len(dic) == 3:
        if max(dic.values()) == n // 3:
            a = 0
            for i in dic:
                a ^= i
            if a == 0:
                print("Yes")
                exit()
print("No")
Buggy python submission (verdict: Runtime Error):
import math

a,b,c,d = map(int,input().split())

c_num = (b // c - math.ceil(a / c) + 1)
d_num = (b // d - math.ceil(a / d) + 1)


def lcm(x, y):
    return (x * y) // math.gcd(x, y)
    
e = lcm(c,d)

e_num = (b // e - math.ceil(a / e) + 1)

print((b-a+1)-(c_num+d_num-e_num))

Fixed submission:
import math
from fractions import gcd
a,b,c,d = map(int,input().split())

c_num = b // c - (a-1) // c
d_num = b // d - (a-1) // d


def lcm(x, y):
    return (x * y) // gcd(x, y)
    
e = lcm(c,d)

e_num = b // e - (a-1) // e

print((b-a+1)-(c_num+d_num-e_num))
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())

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

dpa = [[0 for j in range(k+2)] for i in range(k+2)]
dpb = [[0 for j in range(k+2)] for i in range(k+2)]
suma = []
sumb = []
for i in range(k):
    suma += [vl[i]]
    sumb += [vl[-i-1]]
    suma = sorted(suma)
    sumb = sorted(sumb)
    for j in range(min(i+1, k+1-i)):
        dpa[i][j] = sum(suma[j:])
        dpb[i][j] = sum(sumb[j:])
    
ans = 0
for a in range(k+1):
    for b in range(k+1-a):
        for c in range(min(a+1, k+1-a-b)):
            for d in range(min(b+1, k+1-a-b-c)):
                tmp = dpa[a-1][c] + dpb[b-1][d]
                if tmp > ans:
                    ans = tmp

print(ans)
    

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

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

ans = 0
for a in range(k+1):
    suba = vl[:a]
    for b in range(min(n+1-a, k+1-a)):
        subb = vl[-b:]
        if b == 0:
            subb = []
        sub = suba + subb
        ssub = sorted(sub)
        for _ in range(k-a-b):
            if len(ssub) == 0:
                break
            if ssub[0] < 0:
                ssub.pop(0)
            else:
                break
        if sum(ssub) > ans:
            ans = sum(ssub)

print(ans)

Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())

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

dpa = [[0 for j in range(k+1)] for i in range(k+1)]
dpb = [[0 for j in range(k+1)] for i in range(k+1)]
suma = []
sumb = []
for i in range(k):
    suma += [vl[i]]
    sumb += [vl[-i-1]]
    suma = sorted(suma)
    sumb = sorted(sumb)
    for j in range(min(i+1, k+1-i)):
        dpa[i][j] = sum(suma[j:])
        dpb[i][j] = sum(sumb[j:])
    
ans = 0
for a in range(k+1):
    for b in range(k+1-a):
        for c in range(min(a+1, k+1-a-b)):
            for d in range(min(b+1, k+1-a-b-c)):
                tmp = dpa[a-1][c] + dpb[b-1][d]
                if tmp > ans:
                    ans = tmp

print(ans)
    

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

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

ans = 0
for a in range(k+1):
    suba = vl[:a]
    for b in range(min(n+1-a, k+1-a)):
        subb = vl[-b:]
        if b == 0:
            subb = []
        sub = suba + subb
        ssub = sorted(sub)
        for _ in range(k-a-b):
            if len(ssub) == 0:
                break
            if ssub[0] < 0:
                ssub.pop(0)
            else:
                break
        if sum(ssub) > ans:
            ans = sum(ssub)

print(ans)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())

lmin = 1
rmax = n
for _ in range(m):
    l,r = map(int,input().split())
    if l > lmin:
        lmin = l
    if rmax > r:
        rmax = r
    
print(max(rmax - lmin + 1), 0)
    

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

lmin = 1
rmax = n
for _ in range(m):
    l,r = map(int,input().split())
    if l > lmin:
        lmin = l
    if rmax > r:
        rmax = r
    
print(max(rmax - lmin + 1, 0))
Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7
N = 10**5 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)

Fixed submission:
MOD = 10**9 + 7
N = 10**6 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)

Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7
N = 10**5 + 1

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)

Fixed submission:
MOD = 10**9 + 7
N = 10**6 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w%2))
    path[v-1].append((u-1, w%2))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w))
    path[v-1].append((u-1, w))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Buggy python submission (verdict: Runtime Error):
n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w))
    path[v-1].append((u-1, w))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w))
    path[v-1].append((u-1, w))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Buggy python submission (verdict: Runtime Error):
n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w))
    path[v-1].append((u-1, w))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w))
    path[v-1].append((u-1, w))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)