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: def e_cell_distance(N, M, K, MOD=10**9 + 7):
      class Combination(object):
          """
          組み合わせ
          参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb
          """
  
          __slots__ = ["mod", "factorial", "inverse"]
  
          def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
              fac, inv = [1], []
              fac_append, inv_append = fac.append, inv.append
  
              for i in range(1, max_n + 1):
                  fac_append(fac[-1] * i % mod)
  
              inv_append(pow(fac[-1], mod - 2, mod))
  
              for i in range(max_n, 0, -1):
                  inv_append(inv[-1] * i % mod)
  
              self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]
  
          def combination(self, n, r):
              if r == n or r == 0:
                  return 1
              if r > n:
                  return 0
              return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod
  
      comb = Combination(N * M).combination(N * M - 2, K - 2)
      t1 = sum([d * (M - d) * (N**2) for d in range(1, M)])
      t2 = sum([d * (N - d) * (M**2) for d in range(1, N)])
      t = (t1 + t2) % MOD
      return (comb * t) % MOD
  
  
  N, M, K = [int(i) for i in input().split()]
  print(e_cell_distance(N, M, K))
  
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."}]