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
  
  mod = 7 + 10**9
  
  
  def comb(n, r, fact, revfact):
      return (fact[n] * revfact[n - r] * revfact[r]) % mod
  
  
  def solve():
      input = sys.stdin.readline
      N, M, K = map(int, input().split())
      fact = [1] * (N * M + 1)
      for i in range(1, N * M + 1):
          fact[i] = (fact[i - 1] * i) % mod
      revfact = [1] * (N * M + 1)
      revfact[N * M] = pow(fact[N * M], mod - 2, mod)
      for i in reversed(range(1, N * M)):
          revfact[i] = ((i + 1) * revfact[i + 1]) % mod
  
      others = comb(N * M - 2, K - 2, fact, revfact)
      pair_type = 0
      for i in range(N):  # 縦の距離がi
          if i == 0:
              for j in range(1, M):  # 横の距離がj
                  pair_type += (i + j) * (N - i) * (M - j) % mod
                  pair_type %= mod
          else:
              for j in range(M):
                  if j == 0:
                      pair_type += (i + j) * (N - i) * (M - j) % mod
                  else:
                      pair_type += 2 * (i + j) * (N - i) * (M - j) % mod
                  pair_type %= mod
  
      print(pair_type * others % mod)
      return 0
  
  
  if __name__ == "__main__":
      solve()
  
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."}]