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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    S = INPUT()
    Q = INT()

    flag_order = True
    D_MAP = lambda: map(str, query.split())
    for i in range(Q):
        query = INPUT()
        if len(query.split()) == 1:
            T = 1
        else:
            T = 2
            _, F, C = D_MAP()
            F = int(F)

        if T == 1:
            if flag_order: flag_order = False
            else: flag_order = True
        if T == 2:
            if flag_order:
                if F == 1: S = C + S
                else: S = S + C
            else:
                if F == 1: S = S + C
                else: S = C + S

    print(S if flag_order else ''.join(list(reversed(S))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())


def main():
    S = deque(INPUT())
    Q = INT()

    flag_order = True
    D_MAP = lambda: map(str, query.split())
    for i in range(Q):
        query = INPUT()
        if len(query.split()) == 1:
            T = 1
        else:
            T = 2
            _, F, C = D_MAP()
            F = int(F)

        if T == 1:
            if flag_order: flag_order = False
            else: flag_order = True
        if T == 2:
            if flag_order:
                if F == 1: S.appendleft(C)
                else: S.append(C)
            else:
                if F == 1: S.append(C)
                else: S.appendleft(C)

    print(''.join(S) if flag_order else ''.join(reversed(S)))


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

n,a,b,c,d,e = [int(input()) for _ in range(6)]

s = [n,0,0,0,0,0]
cnt = 0
while 1:
  A = min(a,s[0])
  s[0] = s[0] - A
  B = min(b,s[1])
  s[1] = s[1] + A - B
  C = min(c,s[2])
  s[2] = s[2] + B - C
  D = min(d,s[3])
  s[3] = s[3] + C - D
  E = min(e,s[4])
  s[4] = s[4] + D - E
  s[5] = s[5] + E
  cnt += 1
  if s[5]==n:
    break
print(cnt)

### FIXED CODE ###

n = int(input())
l = [int(input()) for _ in range(5)]
print(-(-n//min(l))+4)
### BUGGY CODE ###

import copy
import math
n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort()
A.reverse()
maxX = max(F) * max(A)
x = [-1 for i in range(maxX + 1)]
def is_able(low, up):
    target = (low + up) // 2
    if low == up - 1:
        return up
    if check(target):
        x[target] = 1
        return is_able(low, target)
    else:
        x[target] = 0
        return is_able(target, up)

def check(time):
    #time が可能かどうか
    practice = copy.deepcopy(k)
    for i in range(n):
        if A[i] * F[i] > time:
            practice -= A[i] - math.floor(time / F[i]) 
            if practice < 0:
                return False
    return True
x[0] = int(check(0))
x[maxX] = int(check(maxX))
print(is_able(-1, maxX))

### FIXED CODE ###

import copy
import math
n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort()
A.reverse()
maxX = max(F) * max(A)
def is_able(low, up):
    target = (low + up) // 2
    if low == up - 1:
        return up
    if check(target):
        return is_able(low, target)
    else:
        return is_able(target, up)
def check(time):
    #time が可能かどうか
    practice = copy.deepcopy(k)
    for i in range(n):
        if A[i] * F[i] > time:
            practice -= A[i] - math.floor(time / F[i]) 
            if practice < 0:
                return False
    return True
print(is_able(-1, maxX))
### BUGGY CODE ###

a = int(input())
b = list(map(int, input().split()))
c = b[0]
for i in range(a-1):
  c *= b[i+1]

if c > 1000000000000000000:
  print(-1)
else:
  print(c)

### FIXED CODE ###

a = int(input())
b = list(map(int, input().split()))
b = sorted(b)
c = b[0]
if c == 0:
  print(c)
  exit()
else:
  for i in range(a-1):
    c *= b[i+1]
    if c > 1000000000000000000:
      break

if c > 1000000000000000000:
  print(-1)
else:
  print(c)
### BUGGY CODE ###

# AtCoder Beginner Contest 097
#s = input()
#K = int(input())

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

pdic = {i:[] for i in range(N)}
outidx = {}
pl = []

for i in range(M):
    p, y = input().split()
    p = int(p)-1
    y = int(y)
    pl.append(p)
    pdic[p].append(y)
    outidx[i] = y

for i in range(N):
    pdic[i] = sorted(pdic[i])

for i, j in enumerate(pl):
    #print(pdic[j])
    print('{:06}{:06}'.format(1+j, 1+pdic[j].index(outidx[i])))

### FIXED CODE ###

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

pdic = {i:[] for i in range(N)}
ppdic = {i:[] for i in range(N)}
outidx = {}
pl = []

for i in range(M):
    p, y = input().split()
    p = int(p)-1
    y = int(y)
    pl.append(p)
    pdic[p].append(y)
    outidx[i] = y

for i in range(N):
    if len(pdic[i]) ==0:
        continue

    pdic[i] = sorted(pdic[i])
    ppdic[i] = {jj : j for j, jj in enumerate(pdic[i])}
#print(ppdic)
#print(pdic)
for i, j in enumerate(pl):
    #print(pdic[j])
    ii = ppdic[j][outidx[i]]
    ##print(ii)
    print('{:06}{:06}'.format(1+j, ii+1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

k,s=mii()

cnt=0

for i in range(0,k+1):
    for j in range(0,k+1):
        for k in range(0,k+1):
            if i+j+k==s:
                cnt+=1
print(cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

k,s=mii()

cnt=0

for i in range(0,k+1):
    for j in range(0,k+1):
        if 0<=s-(i+j)<=k:
            cnt+=1
print(cnt)
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None in ANS[i:i+L] :
            while True:
                if ANS[i] :
                    i += 1
                    continue
                else : 
                    ANS[i] = min(Whole[i+1-L:i+1])
                    i += 1
                    break
        else :
            i += L
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

def main():
    n = int(input())
    inlis = list(map(int, input().split()))

    total = sum(inlis)
    ans = 10 ** 20

    for i in range(n-1):
        x = sum(inlis[:i+1])
        y = total - x
        tmp = abs(x-y)
        if tmp < ans:
            ans = tmp

    print(ans)





if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    inlis = list(map(int, input().split()))

    total = sum(inlis)
    ans = 10 ** 20

    for i in range(n-1):
        if i == 0:
            x = inlis[i]
        else:
            x += inlis[i]
        y = total - x
        tmp = abs(x-y)
        if tmp < ans:
            ans = tmp

    print(ans)





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

# aising2020_c.py
def f(n):
    cnt = 0
    for i in range(1,int(n**0.5)+1):
        for j in range(i,int(n**0.5)+1):
            for k in range(j,int(n**0.5)+1):
                if i**2+j**2+k**2+i*j+j*k+k*i == n:
                    if i==j and i==k and j==k:
                        cnt+=1
                    else:
                        cnt+=3
    return cnt


N = int(input())
for i in range(1,N+1):
    print(f(i))


### FIXED CODE ###

# aising2020_c.py
N = int(input())
ans=[0]*(N+1)
for i in range(1,int(N**0.5)):
    for j in range(1,int(N**0.5)):
        for k in range(1,int(N**0.5)):
            num = i**2+j**2+k**2+i*j+j*k+k*i
            if num<=N:
                ans[num] += 1
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

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

rn = range(A, B+1)
ln = len(rn)
for i, e in enumerate(rn, 1):
    if K >= i:
        print(e)
    elif ln - K < i:
        print(e)


### FIXED CODE ###

# AtCoder
A, B, K = map(int, input().split())
for i in range(A, min(A+K, B+1)):
    print(i)
for j in range(max(B-K+1, A+K), B+1):
    print(j)
### BUGGY CODE ###

n = input()
s = 1
for i  in input().split():
  s = s * int(i)

if s > 1e+18:
  print(-1)  
else:
  print(s)

### FIXED CODE ###

n = input()
s = 1

int_list = [int(s) for s in input().split()]
if 0 in int_list:
  print(0)
else:
  for i in int_list:
    s = s * int(i)
    if s > 1e+18:
      s = -1
      break
  print(s)
### BUGGY CODE ###

def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
  
n, W = map(int, input().split()) 
val = [] 
wt = [] 

for _ in range(n):
    w, v = map(int, input().split()) 
    val.append(v)
    wt.append(w)

print(knapSack(W, wt, val, n))

### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())
 
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))
 
 
main()
### BUGGY CODE ###

mod = 10**9 + 7
N = 10**9
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, N + 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


n,a,b = map(int,input().split())
#mod = 10**9+7

#print(cmb(n,a) % mod)
#print(cmb(n,b) % mod)
print((2**n - 1 - cmb(n,a,mod) - cmb(n,b,mod)) % mod)

### FIXED CODE ###

def cmb(n, r):
	if n - r < r:
		r = n - r
	if r == 0:
		return 1
	if r == 1:
		return n
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
			result = result % mod
	
	return result

n,a,b = map(int,input().split())
mod = 10**9+7

print((pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)) % mod)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

AB = [a+b for a in A for b in B]
AB.sort(reverse=True)
AB = AB[0:min(3001,X*Y*Z+1)]

ABC = [ab+c for ab in AB for c in C]
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

### FIXED CODE ###

# 通ってるコードをコピペ、ほぼ同じはずなんだけどこれは通る？
x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n = int(input())
a = [int(i) for i in input().split()]

left_gcd = [0]
right_gcd = [0]

for i in range(n):
    left_gcd.append(gcd(left_gcd[-1], a[i]))
    right_gcd.insert(0, gcd(right_gcd[0], a[(n - 1) - i]))

max_gcd = 0

for i in range(n):
    get_gcd = gcd(left_gcd[i], right_gcd[i + 1])
    if get_gcd > max_gcd:
        max_gcd = get_gcd

print(max_gcd)


### FIXED CODE ###

from collections import deque

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n = int(input())
a = [int(i) for i in input().split()]

left_gcd = deque()
left_gcd.append(0)
right_gcd = deque()
right_gcd.append(0)

for i in range(n):
    left_gcd.append(gcd(left_gcd[-1], a[i]))
    right_gcd.appendleft(gcd(right_gcd[0], a[(n - 1) - i]))

max_gcd = 0

for i in range(n):
    get_gcd = gcd(left_gcd[i], right_gcd[i + 1])
    if get_gcd > max_gcd:
        max_gcd = get_gcd

print(max_gcd)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

def popcount(x):
    res = 0
    for i in range(n+1):
        if x & (1 << i):
            res += 1 
    return res

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % popcount(x), cnt + 1)
        memo[x] = ans - cnt
        return ans


px = popcount(x)
ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)


    

        


### FIXED CODE ###

from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)
### BUGGY CODE ###

#しゃくとり法忘れてた
n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
now=[0]*20#2^20なので
for i in range(n):
    left=i
    if i!=0:
        for j in range(20):
            if (a[left-1]>>j)&1:
                now[j]-=1
    else:
        for j in range(20):
            if (a[left]>>j)&1:
                now[j]+=1
    while all([now[j]<=1 for j in range(20)]):
        #print(100000000)
        right+=1
        if right==n:
            break
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]+=1
    else:
        #print(right)
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]-=1
    right-=1
    ans+=(right-left+1)
    #print(left,right)
print(ans)

### FIXED CODE ###

#しゃくとり法忘れてた
n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
now=[0]*20#2^20なので
for i in range(n):
    left=i
    if i!=0:
        for j in range(20):
            if (a[left-1]>>j)&1:
                now[j]-=1
    else:
        for j in range(20):
            if (a[left]>>j)&1:
                now[j]+=1
    while all([now[j]<=1 for j in range(20)]):
        #print(100000000)
        right+=1
        if right==n:
            break
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]+=1
    else:
        #print(right)
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]-=1
    right-=1
    ans+=(right-left+1)
    #print(left,right)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans=[]
for j in range(n):
  for idx,num in enumerate(a):
    if num==j+1:
      ans.append(idx+1)

print(*ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans=[0]*n
for i in range(n):
    ans[a[i]-1] = i+1 

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

N=int(input())
S=input()
Sf=S[:N]
Sb=S[N:2*N]
Sb=Sb[::-1]
ans=0
for i in range(2**N):
  R=[]
  B=[]
  for k in range(N):
    if i&(1<<k):
      R.append(Sf[k])
    else:
      B.append(Sf[k])
  dp=[[0]*(N+1) for i in range(N+1)]
  dp[0][0]=1
  f=True
  for k in range(1,N+1):
    for j in range(N):
      if j<len(R):
        if Sb[k-1]==R[j]:
          dp[k][j+1]+=dp[k-1][j]
      if 0<=k-j-1<len(B):
        if Sb[k-1]==B[k-j-1]:
          dp[k][j]+=dp[k-1][j]
  ans+=sum(dp[N])
print(ans)
   
      
    

### FIXED CODE ###

N=int(input())
S=input()
Sf=S[:N]
Sb=S[N:2*N]
Sb=Sb[::-1]
ans=0
for i in range(2**N):
  R=[]
  B=[]
  for k in range(N):
    if i&(1<<k):
      R.append(Sf[k])
    else:
      B.append(Sf[k])
  dp=[[0]*(N+1) for i in range(N+1)]
  dp[0][0]=1
  f=True
  for k in range(1,N+1):
    for j in range(k):
      if j<len(R):
        if Sb[k-1]==R[j]:
          dp[k][j+1]+=dp[k-1][j]
      if 0<=k-j-1<len(B):
        if Sb[k-1]==B[k-j-1]:
          dp[k][j]+=dp[k-1][j]
  ans+=sum(dp[N])
print(ans)
### BUGGY CODE ###

modout = lambda x: x%1000000007

N, M, K = map(int, input().split())
N2 = N**2
M2 = M**2
Xpattern = [x * (N-x)*M2 for x in range(N)]
Ypattern = [y * (M-y)*N2 for y in range(M)]
coef = 1
num = min(K-2, N*M-K)
for i in range(N*M-2, N*M-2-num, -1):
    coef *= i
for j in range(1, num+1):
    coef //= j


print(modout((sum(Xpattern)+sum(Ypattern))*coef))

### FIXED CODE ###

mod = 1000000007
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())


def cmb(n, r):
    if n<0 or r<0 or r>n:
        return None
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = [0]*r
    denominator = [0]*r
    for k in range(r):
        numerator[k] = n-r+k+1
        denominator[k] = k+1
    for p in range(2, r+1):
        pivot = denominator[p-1]
        if pivot > 1:
            offset = (n-r) % p
            for k in range(p-1, r, p):
                numerator[k-offset] //= pivot
                denominator[k] //= pivot
    res = 1
    for n in numerator:
        if n > 1:
            res *= n
    return res

N2 = N**2
M2 = M**2
Xpattern = [(x * (N-x)) % mod for x in range(N)]
Ypattern = [(y * (M-y)) % mod for y in range(M)]
coef = cmb(N*M-2, K-2)

print(((sum(Xpattern)*M2+sum(Ypattern)*N2)*coef)%mod)
### BUGGY CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    N, *a = map(int, read().split())
    a = tuple(a)
    INF = float('inf')
    memo = [[INF] * N for _ in range(N)]

    def f(i, j):
        if memo[i][j] != INF:
            return memo[i][j]
        n = j - i + 1
        n %= 2
        if i == j:
            if n == r:
                s = a[i]
            else:
                s = -a[i]
            memo[i][j] = s
            return s
        if n == r:
            s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
        else:
            s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
        memo[i][j] = s
        return s

    r = N % 2
    f(0, N - 1)
    return memo[0][N - 1]


print(solve())


### FIXED CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            if L > R:
                dp[i][j] = L
            else:
                dp[i][j] = R
    return dp[0][n - 1]


print(solve())
### BUGGY CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))
  dp=[0]*n
  for i in range(1,n):
    dp[i]=dp[i-1]+abs(h[i-1]-h[i])
    for j in range(1,k+1):
      if i-j<0:
        break
      dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]))
      #print("i",i,"j",j,dp)
  print(dp[-1])

main()

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  dp[i]=dp[i-1]+abs(h[i-1]-h[i])
  for j in range(1,k+1):
    if i-j<0:
      break
    dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]))
    #print("i",i,"j",j,dp)
print(dp[-1])