Harryxun/stf_run huggingface dataset:
from collections import defaultdict
N = int( input())
S = list( map( int, input().split()))

ans = 0
for c in range(1,N):
    now = 0
    k = 1
    for _ in range(1,N):
        if k*2 + 1 > N-2:
            break
        if k*c >= N-1:
            break
        if (N-1-k*c)%c <= k:
            break
        now += S[k*c] + S[N-1-k*c]
        d[k*c] = 1
        d[N-1-k*c] = 1
        if now > ans:
            ans = now
        k += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int( input())
S = list( map( int, input().split()))

ans = 0
for c in range(1,N):
    now = 0
    for t in range(c ,N, c):
        if ((N-1-t)%c == 0 and N-1-t <= t) or N-1-t - c <=0:
            break
        now += S[t] + S[N-1-t]
        if now > ans:
            ans = now
print(ans)
n=int(input())
xymap=[[-1 for j in range(101)] for i in range(101)]
inp=[]
for i in range(n):
    xi,yi,hi=map(int,input().split())
    if hi==0:
        inp.append(xi,yi,hi)
        pass
    else:
            
        for x in range(101):
            for y in range(101):
                a=abs(xi-x)+abs(yi-y)+hi
                if xymap[x][y]==a or xymap[x][y]==-1 :
                    xymap[x][y]=a
                else:
                    xymap[x][y]=-2
flag=0
for x in range(101):
    for y in range(101):
        if xymap[x][y]!=-2:
            flag=1
            print(x,y,xymap[x][y])
if flag==0:
    xymap=[[-1 for j in range(101)] for i in range(101)]
    for i in range(len(inp)):
        xi=inp[i][0]
        yi=inp[i][1]
        hi=inp[i][2]
        for x in range(101):
            for y in range(101):
                a=abs(xi-x)+abs(yi-y)+hi
                if xymap[x][y]==a or xymap[x][y]==-1 :
                    xymap[x][y]=a
                else:
                    xymap[x][y]=-2
    for x in range(101):
        for y in range(101):
            if xymap[x][y]!=-2:
                print(x,y,xymap[x][y])

### FIXED CODE ###

n=int(input())
xymap=[[-1 for j in range(101)] for i in range(101)]
inlist=[]
for i in range(n):
    xi,yi,hi=map(int,input().split())
    inlist.append([xi,yi,hi])
inlist.sort(key=lambda x :-x[2])
for i in range(n):
    xi,yi,hi=inlist[i]
    if hi==0:
        xymap[xi][yi]=-2
        for x in range(101):
            for y in range(101):
                a=abs(xi-x)+abs(yi-y)+hi
                if xymap[x][y]<=a:
                    pass
                else:
                    xymap[x][y]=-2
    else:
        for x in range(101):
            for y in range(101):
                a=abs(xi-x)+abs(yi-y)+hi
                if xymap[x][y]==a or xymap[x][y]==-1 :
                    xymap[x][y]=a
                else:
                    xymap[x][y]=-2
for x in range(101):
    for y in range(101):
        if xymap[x][y]!=-2:
            print(x,y,xymap[x][y])
import itertools
 
N,M,Q=map(int,input().split())
all=[]
for i in range(Q):
  all.append(list(map(int,input().split()))
 
x=[i for i in range(1,M+1)]
maxdsum=0
 
for A in itertools.combinations_with_replacement(x, N):
  dsum=0
  for num in range(Q):
    if A[all[num][1]-1]-A[all[num][0]-1]==all[num][2]:
      dsum+=all[num][3]
  if maxdsum<dsum:
    maxdsum=dsum
print(maxdsum)

### FIXED CODE ###

import itertools
 
N,M,Q=map(int,input().split())
all=[]
 
for i in range(Q):
  all.append(list(map(int,input().split())))
#print(all)
#print(len(all))
#print(all[0][1])
 
x=sorted([i for i in range(1,M+1)])
maxdsum=0
 
 
for A in itertools.combinations_with_replacement(x, N):
  dsum=0
  #print("A=="+str(A))
  for num in range(Q):
    if A[all[num][1]-1]-A[all[num][0]-1]==all[num][2]:
      dsum+=all[num][3]
  if maxdsum<dsum:
    maxdsum=dsum
print(maxdsum)
S = input()
N = len(S)+1
a = [-1]*N
l = []
for i in range(1,N-1):
    if S[i-1] == '>' and S[i] == '<':
        a[i] = 0
        l.append(i)

if S[0] == '<':
    a[0] = 0
    l.append(0)
if S[-1] == '>':
    a[N-1] = 0
    l.append(N-1)

for i in l:
    j = i-1
    while 0<=j<=N-2 and S[j]=='>' and S[j-1]=='>':
        a[j] = a[j+1]+1
        j -= 1
    j = i+1
    while 0<=j<=N-2 and S[j]=='<' and S[j+1]=='<':
        a[j] = a[j-1]+1
        j += 1

for i in range(1,N-1):
    if a[i] == -1:
        a[i] = max(a[i-1],a[i+1])+1


if S[0] == '>':
    a[0] = a[1]+1

if S[-1] == '<':
    a[N-1] = a[N-2]+1

print(sum(a))

### FIXED CODE ###

S = input()
N = len(S)+1
a = [-1]*N
l = []
for i in range(1,N-1):
    if S[i-1] == '>' and S[i] == '<':
        a[i] = 0
        l.append(i)

if S[0] == '<':
    a[0] = 0
    l.append(0)
if S[-1] == '>':
    a[N-1] = 0
    l.append(N-1)

for i in l:
    j = i-1
    while 0<=j<=N-2 and S[j]=='>' and S[j-1]=='>':
        a[j] = a[j+1]+1
        j -= 1
    j = i+1
    while 0<=j<=N-3 and S[j]=='<' and S[j+1]=='<':
        a[j] = a[j-1]+1
        j += 1

for i in range(1,N-1):
    if a[i] == -1:
        a[i] = max(a[i-1],a[i+1])+1


if S[0] == '>':
    a[0] = a[1]+1

if S[-1] == '<':
    a[N-1] = a[N-2]+1

print(sum(a))
n=int(input())
sp=[]
for i in range(n):
    s,p=input().split()
    sp.append([s,int(p),i+1])
    
sort=sorted(sp, key=lambda sp: sp[0], -sp[1])

for i in range(sort):
    print(i[2])
    

### FIXED CODE ###

n=int(input())
sp=[]
for i in range(n):
    s,p=input().split()
    sp.append([s,int(p),i+1])
    
sort=sorted(sp, key=lambda sp: (sp[0], -sp[1]))

for i in sort:
    print(i[2])
n = int(input())

MOD = 10**9 + 7

ans = pow(10, n, MOD)-pow(9, n, MOD) - pow(9, n, MOD) + pow(8, n, MOD)

#負の処理
ans (ans+MOD)%MOD

print(ans)

### FIXED CODE ###

n = int(input())

MOD = 10**9 + 7

ans = pow(10, n, MOD)-pow(9, n, MOD) - pow(9, n, MOD) + pow(8, n, MOD)

#負の処理
ans = (ans+MOD)%MOD

print(ans)
x = input()
y = [input() for i + 1 in range(x)]
z = y.split()
s = Case

for a in ragen(1,10001):
    print('{} {} : {}',format(s,a,z))

### FIXED CODE ###

i = 1
while True:
     x = int(input())
     if x == 0: break
     print('Case {}: {}'.format(i, x))
     i += 1
N = int(input())
*A, = map(int,input().split())
ans = 0
S = A[0]
for a in A[1:]:
    S1 = S+a
    if S1*S >= 0:
        ans += abs(S1)+1
        S1 = -S//abs(S)
    S = S1
print(ans)

### FIXED CODE ###

N = int(input())
*A, = map(int,input().split())
ans1 = 0
S = A[0]
if S <= 0:
    ans1 = abs(S)+1
    S = 1
for a in A[1:]:
    S1 = S+a
    if S1*S >= 0:
        ans1 += abs(S1)+1
        S1 = -S//abs(S)
    S = S1
ans2 = 0
S = A[0]
if S >= 0:
    ans2 = abs(S)+1
    S = -1
for a in A[1:]:
    S1 = S+a
    if S1*S >= 0:
        ans2 += abs(S1)+1
        S1 = -S//abs(S)
    S = S1
print(min(ans1,ans2))
a, b =[int(input() for i in range(2))]
c = a//500
if c <= b:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n = int(input())
a = int(input())
 
if n % 500  <=a:
  print("Yes")
else:
  print("No")
import statistics
n = int(input())
al = list(map(int,input().split()))

for i in range(n):
    al[i] -= i + 1

median = statistics.median(al)

ans = 0
for a in al:
    ans += abs(median - a)

print(int(ans))

### FIXED CODE ###

import numpy as np
n = int(input())
al = list(map(int,input().split()))

for i in range(n):
    al[i] -= i + 1

med = np.median(np.array(al))

ans = 0
for a in al:
    ans += abs(a-med)
print(int(ans))
def gcd(x,y):
    if y == 0:
        print(x)
        return x
    else:
        return gcd(y, x%y)

# def lcm(x,y):
#     return x/gcd(x,y)*y
#ans=1

a=int(input())
li=list(map(int,input().split()))
#li_same=li
num=0
num_li=[]
for i in range(a):
    #li=li_same
    b=li.pop(i)
    k=len(li)
    for j in range(1,k):
        ans=gcd(li[j-1],li[j])
        print(ans)
    print('hoge')
    num_li.append(ans)
    li.insert(i,b)

print(int(max(num_li)))



### FIXED CODE ###

 
#from functools import reduce
def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x
 
a=int(input())
li=list(map(int,input().split()))
left_gcd=[0]
#left_gcd.append(li[0])
right_gcd=[0]
#right_gcd.append(li[a-1])

for i in range(a):
    left_gcd.append(gcd(li[i],left_gcd[i]))
    right_gcd.append(gcd(li[a-1-i],right_gcd[i]))
    #k=k+1
# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)
#print(right_gcd)
#print(left_gcd)
num_li=[]
#num_li.append(right_gcd[a-2])
#num_li.append(left_gcd[a-2])
#s=2
for i in range(a):
    ans=gcd(left_gcd[(a-1)-i],right_gcd[i])
    #print(left_gcd[(a-3-i)],right_gcd[i])
  
    #print(ans)
    num_li.append(ans)
    

print(max(num_li))
n = int(input())
words = input()

count ≒ 0
for i in range(n - 2):
  if words[i] == 'A':
    if words[i + 1] == 'B':
      if words[i + 2] == 'C':
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
words = input()

count = 0
for i in range(n - 2):
  if words[i] == 'A':
    if words[i + 1] == 'B':
      if words[i + 2] == 'C':
        count += 1
print(count)
def tax_increase(a,b):

    al = [a+(i / 10) for i in range(0,10,1)]
    bl = [b+(i / 10) for i in range(0,10,1)]
    #print(al)
    #print(bl)

    atx8 = list(map(lambda x: x/t8 ,al))
    btx10 = list(map(lambda x: x/t10 ,bl))
    #print(atx8)
    #print(btx10)

    for i in atx8:
        if i in btx10:
            return i
        else:
            pass
    return -1

if __name__ == '__main__':
    a,b = map(int,input().split())
    ans = int(tax_increase(a,b))
    print(ans)

### FIXED CODE ###

def tax_increase(a,b):
    t8  = 0.08
    t10 = 0.1
    for i in range(b*10,(b+1)*10,1):
        if int(i*t8) == a:
            return i
    return -1
    
if __name__ == '__main__':
    a,b = map(int,input().split())
    ans = int(tax_increase(a,b))
    print(ans)
a o b = map(str, input().split())

if o == "+":
  print(int(a) + int(b))
else:
  print(int(a) - int(b))

### FIXED CODE ###

a, o, b = map(str, input().split())
 
if o == "+":
  print(int(a) + int(b))
else:
  print(int(a) - int(b))
n = int(input())
a = list(map(int, input().split()))

money = 1000
num_item = 0

kakaku = []

# かぶりをなくす
for i in a:
    if len(kakaku) == 0:
        kakaku.append(i)
    else:
        if kakaku[-1] == i:
            pass
        else:
            kakaku.append(i)

dp = []
MAX = 10000
MIN = -1
tmp_min = MAX
tmp_max = MIN

up_flag = False
down_flag = False

if kakaku[0] < kakaku[1]:
    up_flag = True
else:
    down_flag = True

if up_flag:
    dp.append(kakaku[0])

# 減=>増=>減....の形にする
for i in range(1, len(kakaku)):
    # いま増加中or下後中
    if kakaku[i - 1] > kakaku[i]:
        if down_flag:
            pass
        else:
            down_flag=True
            up_flag=False
            dp.append(kakaku[i-1])
        down_flag = True
    else:
        if up_flag:
            pass
        else:
            down_flag = False
            up_flag = True
            dp.append(kakaku[i-1])
        up_flag = True
    # print('up', up_flag, 'down', down_flag, 'now item',kakaku[i], 'dp', dp)

if kakaku[-2] < kakaku[-1]:
    dp.append(kakaku[-1])

for i in range(len(dp)):
    if i % 2 == 0:
        num_item += money // dp[i]
        money -= dp[i] * num_item
    else:
        money += dp[i] * num_item
        num_item = 0

if num_item != 0:
    money += dp[-1] * num_item

print(money)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
money = 1000
stock = 0
 
for i in range(N):
    if i == N-1:
        money += stock * A[i]
        break
    if A[i] < A[i+1]:
        tmp_stock = money // A[i]
        stock += tmp_stock
        money -= tmp_stock * A[i]
    elif A[i] > A[i+1]:
        money += stock * A[i]
        stock = 0
    else:
        pass
 
print(money)
s=input()
p=input()
print('Yes' if p in s+s else 'No')

### FIXED CODE ###

print(input().swapcase())
=input()
t=input()
n=len(s)
m=len(t)
li=[]
for i in range(n-m+1):
  u=s[i:i+m]
  c=0
  for j in range(m):
    if u[j]!="?" and u[j]!=t[j]:
      c=1
      break
  if c==0:
    if i==0:
      v=t+s[i+m]
    elif i==n-m:
      v=s[:i]+t
    else:
      v=s[:i]+t+s[i+m]
    for k in range(n):
      if v[k]=="?":
        v=v[:k]+"a"+v[k+1:]
    li.append(v)
if li==[]:
  print("UNRESTORABLE")
else:
  li.sort()
  print(li[0])

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
li=[]
for i in range(n-m+1):
  u=s[i:i+m]
  c=0
  for j in range(m):
    if u[j]!="?" and u[j]!=t[j]:
      c=1
      break
  if c==0:
    if i==0:
      v=t+s[i+m:]
    elif i==n-m:
      v=s[:i]+t
    else:
      v=s[:i]+t+s[i+m:]
    for k in range(n):
      if v[k]=="?":
        v=v[:k]+"a"+v[k+1:]
    li.append(v)
if li==[]:
  print("UNRESTORABLE")
else:
  li.sort()
  print(li[0])
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(n - 1, -1, -1):
    if i + 1 > n // 2:
        ans[i] = a[i]
    else:
        cnt = 0
        for j in range(i, n, i + 1):
            if ans[j] == 1:
                cnt += 1
        #ans[i] = cnt % 2 + a[i]
        if cnt % 2 == a[i]:
            ans[i] = 0
        else:
            ans[i] = 1 
print(sum(s))
for i, j in enumerate(s):
    if j == 1:
        print(i + 1)
            

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0] * n
for i in range(n - 1, -1, -1):
    if i + 1 > n // 2:
        s[i] = a[i]
    else:
        cnt = 0
        for j in range(i, n, i + 1):
            if s[j] == 1:
                cnt += 1
        if cnt % 2 == a[i]:
            s[i] = 0
        else:
            s[i] = 1
print(sum(s))
for i, j in enumerate(s):
    if j == 1:
        print(i + 1)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
z_list = factorization(N)
Z = []
for z in z_list:
        for e in range(1, z[1]+1):
            Z.append(z[0]**e)
sorted(Z)
counter = 0 
if N==i:
    print(0)
    quit()
for z in Z:
    if(N%z==0):
        N = N//z
        counter += 1
print(counter)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
z_list = factorization(N)
Z = []
for z in z_list:
        for e in range(1, z[1]+1):
            Z.append(z[0]**e)
sorted(Z)
counter = 0 
if N==1:
    print(0)
    quit()
for z in Z:
    if(N%z==0):
        N = N//z
        counter += 1
print(counter)
sum = 0
answer = 900
a, b = (int(i) for i in input().split())  
t = [int(input()) for j in range(a)] 
for k in range a:
    b = b - t[k]
    sum = sum + 1
t = t.sort()
z = b % t[0]
sum = sum + z
print(sum)
    


### FIXED CODE ###

sum = 0
a, b = (int(i) for i in input().split())  
t = [int(input()) for j in range(a)] 
for k in range (a):
    b = b - t[k]
    sum = sum + 1
t.sort()
if b < t[0]:
    print(sum)
else:
    z = b // t[0]
    sum = sum + z
    print(sum)
n = int(input())
A = list(map(int, input().split()))
q = int(input())
BC = [list(map(int, input().split())) for i in range(q)]

list=[0]*100000
sum=sum(A)
for i in A:
    list[i]+=1

for bc in BC:
    x=list[bc[0]]
    sum-=bc[0]*x
    sum+=bc[1]*x
    print(sum)
    list[bc[0]]-=x
    list[bc[1]]+=x

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
BC = [list(map(int, input().split())) for i in range(q)]

list=[0]*100001
sum=sum(A)
for i in A:
    list[i]+=1

for bc in BC:
    x=list[bc[0]]
    sum+=(bc[1]-bc[0])*x
    print(sum)
    list[bc[0]]-=x
    list[bc[1]]+=x
a=int(input())
input(a+a*a+a**3)

### FIXED CODE ###

a=int(input())
print(a+a*a+a*a*a)
N = input()
a = list(map(int,input().split()))
b = 0

for i in range(N):
  if a[i] % 2 == 0:
    if a[i] % 3 != 0 and a[i] % 5 != 0:
      b = 1
      break
if b == 0:
  print("APPROVED")
else:
  print("DENIED")


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
c = 0
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] %3 != 0 :
            if A[i] %5 != 0:
                c = 1
                break
if c == 0:
    print("APPROVED")
else:
    print("DENIED")
N=Input("")
if N % 10 == 7 || (N - N % 10) / 10 % 10 == 7 || (N - N % 100)/100 == 7:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input(""))
if N % 10 == 7 or (N - N % 10) / 10 % 10 == 7 or (N - N % 100)/100 == 7:
  print("Yes")
else:
  print("No")
print(700 + input().count('o')　*　100)

### FIXED CODE ###

s = input()
counter = 0
if s[0] == 'o':
  counter += 1
if s[1] == 'o':
  counter += 1
if s[2] == 'o':
  counter += 1
print(int(700+counter*100))
from operator import mul
from functools import reduce

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

def cmb(n,r,mod):
  if r==0 or n==r:return 1
  r = min(n-r,r)
  ue = reduce(mul, range(n, n-r, -1))
  shita = reduce(mul, range(1,r+1))
  return (ue//shita)%mod

for i in range(1,k+1):
  print(cmb(n-k+1,i,mod)*cmb(k-1,k-i,mod))

### FIXED CODE ###

from operator import mul
from functools import reduce

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

def cmb(n,r,mod):
  if r==0 or n==r:return 1
  r = min(n-r,r)
  ue = reduce(mul, range(n, n-r, -1))
  shita = reduce(mul, range(1,r+1))
  return (ue//shita)%mod

for i in range(1,k+1):
  try:print(cmb(n-k+1,i,mod)*cmb(k-1,k-i,mod)%mod)
  except:print(0)
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  edge[l].append((r,d))
  edge[r].append((l,-d))
ans=[10**20]*n
inf=10**20
for i in range(n):
  if ans[i]!=inf:continue
  stack=[i]
  visited={i}
  ans[i]=0
  for node in stack:
    for mode,d in edge[node]:
      if ans[node]+d!=ans[mode]!=inf:exit(print("No")) #ans[node]+d!=ans[mode] and ans[mode]!=inf
      if mode in visited:continue
      visited.add(mode)
      stack.append(mode)
      if ans[mode]==inf:
        ans[mode]=ans[node]+d
        #if ans[node]+d!=ans[mode]:exit(print("No"))
print("Yes")




### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

x=I()
a=I()
b=I()
ans=(x-a)%b
print(ans)
n,d =map(int, input().split())
L=[]
for i in range(n):
    L.append(list(map(int, input().split())))
ans =0

for i in range(n):
    for j in range(i+1,n):
        dis=0
        for k in range(d):
            dis = (L[i][k]-L[j][k])**2
        dis = dis**0.5
        if(dis == int(dis):
            ans +=1
print(ans)

### FIXED CODE ###

n,d =map(int, input().split())
L=[]
for i in range(n):
    L.append(list(map(int, input().split())))
ans =0

for i in range(n):
    for j in range(i+1,n):
        dis=0
        for k in range(d):
            dis += (L[i][k]-L[j][k])**2
        dis = dis**0.5
        if dis % 1.0 ==0:
            ans +=1
print(ans)
s = input()
print(s[:4]+' '+s[4:]+'\n')

### FIXED CODE ###

s = input()
print(s[:4]+' '+s[4:])
print("".join([o, e for o, e zip(input(), input())]))

### FIXED CODE ###

odd, even = input(), input()
p = "".join([o+e for o, e in zip(odd, even)])
if len(odd) != len(even):
  p += odd[-1]
print(p)
n = int(input())
s = input()
x = 0
ans = 0
for i in s:
  if i=="I:
    c+=1
  else:
    c-=1
    ans = max(c, ans)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = 0
ans = 0
for i in s:
  if i=="I":
    x+=1
    ans = max(x, ans)
  else:
    x-=1
print(ans)
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

xs, ys, xt, yt = map(int, input().split())
n = int(input())

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[0]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)

edge = csgraph_from_dense(edge,null_value=None)
d = dijkstra(edge,directed=False,indices=0)

print(d[1])


### FIXED CODE ###

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点sから各頂点への最短距離
#n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
d = [float("inf")] * n
used = [False] * n
d[s] = 0
    
while True:
    v = -1
    #まだ使われてない頂点の中から最小の距離のものを探す
    for i in range(n):
        if (not used[i]) and (v == -1):
           v = i
        elif (not used[i]) and d[i] < d[v]:
            v = i
    if v == -1:
           break
    used[v] = True
           
    for j in range(n):
           d[j] = min(d[j],d[v]+cost[v][j])
print(d[1])
a, b, c = map(int, input().split())

if a + b = c:
  print('yes')
elif b + c = a:
  print('yes')
elif c + a = b:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a, b, c = map(int, input().split())
 
if a + b == c:
  print('Yes')
elif b + c == a:
  print('Yes')
elif c + a == b:
  print('Yes')
else:
  print('No')
# 各数値の取得
a,b,c,d = map(int,input().split)

#各条件に沿ってメッセージを出力
#1:aとcの差分の絶対値がd以下の場合、直接会話が可能であるため「Yes」を出力
if abs(a-c) <= d:
    print("Yes")
#2:aとbの差分及びbとcの差分がd以下の場合、関節会話が可能であるため「Yes」を出力
elif abs(a-b) <=d and abs(b-c) <= d:
    print("Yes")
# 1及び2のどちらの条件にも当てはまらない場合、会話が不可能のため「No」を出力
else:
    print("No")

### FIXED CODE ###

# 各数値の取得
a,b,c,d = map(int,input().split())

#各条件に沿ってメッセージを出力
#1:aとcの差分の絶対値がd以下の場合、直接会話が可能であるため「Yes」を出力
if abs(a-c) <= d:
    print("Yes")
#2:aとbの差分及びbとcの差分がd以下の場合、関節会話が可能であるため「Yes」を出力
elif abs(a-b) <=d and abs(b-c) <= d:
    print("Yes")
# 1及び2のどちらの条件にも当てはまらない場合、会話が不可能のため「No」を出力
else:
    print("No")
N = int(input())
T = [[0,0,0]]+[map(int, input().split()) for _ in range(N)]
flag = 'Yes'
i = 0
while flag=='Yes' and i<len(T)-1:
    t1,x1,y1 = T[i] 
    t2,x2,y2 = T[i+1]
    dis = abs(x2-x1)+abs(y2-y1)
    _t = t2-t1
    if dis > _t or _t%2 != dis%2:
        flag = 'No'
    i += 1        
print(flag)
    

### FIXED CODE ###

N = int(input())
T = [[0,0,0]]+[ [int(x) for x in input().split()] for _ in range(N)]

flag = 'Yes'
i = 0
while flag=='Yes' and i<len(T)-1:
    t1,x1,y1 = T[i] 
    t2,x2,y2 = T[i+1]
    dis = abs(x2-x1)+abs(y2-y1)
    _t = t2-t1
    if dis > _t or _t%2 != dis%2:
        flag = 'No'
    i += 1        
print(flag)
def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up *= (_N - i)
        low *= (i + 1)
    ret = up /low
    if ret >= MAX:
        ret %= MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()


### FIXED CODE ###

MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = (M*N* ((M*(N+1)*(N-1))%MAX + (N*(M+1)*(M-1)) % MAX)) % MAX
    disSum *= mod_inv(6, MAX) % MAX
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

if __name__ == '__main__':
    solve()