output_description: Print the sum of the costs of all possible arrangements of the pieces, modulo
  10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M K
attempt: import sys
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  
  import numpy as np
  
  # 2点間の距離の平均を求めればよい
  
  MOD = 10**9 + 7
  
  N, M, K = map(int, read().split())
  
  
  def cumprod(arr, MOD):
      L = len(arr)
      Lsq = int(L**0.5 + 1)
      arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
      for n in range(1, Lsq):
          arr[:, n] *= arr[:, n - 1]
          arr[:, n] %= MOD
      for n in range(1, Lsq):
          arr[n] *= arr[n - 1, -1]
          arr[n] %= MOD
      return arr.ravel()[:L]
  
  
  def make_fact(U, MOD):
      x = np.arange(U, dtype=np.int64)
      x[0] = 1
      fact = cumprod(x, MOD)
      x = np.arange(U, 0, -1, dtype=np.int64)
      x[0] = pow(int(fact[-1]), MOD - 2, MOD)
      fact_inv = cumprod(x, MOD)[::-1]
      return fact, fact_inv
  
  
  U = 10**6
  fact, fact_inv = make_fact(U, MOD)
  
  coef = fact[N * M - 2] * fact_inv[K - 2] % MOD * fact_inv[N * M - K] % MOD
  
  x = (N - 1) * N * (N + 1) * M * M // 6
  y = (M - 1) * M * (M + 1) * N * N // 6
  answer = coef * ((x + y) % MOD) % MOD
  print(answer)
  
problem_description: Statement
  
  We have a grid of squares with N rows and M columns. Let (i, j) denote the
  square at the i-th row from the top and j-th column from the left. We will
  choose K of the squares and put a piece on each of them.
  
  If we place the K pieces on squares (x_1, y_1), (x_2, y_2), ..., and (x_K,
  y_K), the _cost_ of this arrangement is computed as:
  
  \sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)
  
  Find the sum of the costs of all possible arrangements of the pieces. Since
  this value can be tremendous, print it modulo 10^9+7.
  
  We consider two arrangements of the pieces different if and only if there is a
  square that contains a piece in one of the arrangements but not in the other.
samples: [{"input": "2 2 2", "output": "8\n    \n\nThere are six possible arrangements of the pieces, as follows:\n\n  * ((1,1),(1,2)), with the cost |1-1|+|1-2| = 1\n  * ((1,1),(2,1)), with the cost |1-2|+|1-1| = 1\n  * ((1,1),(2,2)), with the cost |1-2|+|1-2| = 2\n  * ((1,2),(2,1)), with the cost |1-2|+|2-1| = 2\n  * ((1,2),(2,2)), with the cost |1-2|+|2-2| = 1\n  * ((2,1),(2,2)), with the cost |2-2|+|1-2| = 1\n\nThe sum of these costs is 8.\n\n* * *"}, {"input": "4 5 4", "output": "87210\n    \n\n* * *"}, {"input": "100 100 5000", "output": "817260251\n    \n\nBe sure to print the sum modulo 10^9+7."}]