#include<bits/stdc++.h>
using namespace std;

//mod逆元を使ったnCkの計算(速)
const int64_t MAX = 510000;
const int64_t MOD = 1000000007;

int64_t fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
int64_t COM(int64_t n, int64_t k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  int64_t N, M, K;
  cin >> N >> M >> K;
  int64_t ans = 0;
  
  int64_t n = N*(N*N-1) / 6;
  n %= MOD;
  n *= M*M;
  n %= MOD;
  
  int64_t m = M*(M*M-1) / 6;
  m %= MOD;
  m *= N*N;
  m %= MOD;
  
  ans = n + m;
  ans %= MOD;

  
  COMinit();
  int64_t all = COM(N*M-2,K-2);
  
  ans *= all;
  ans %= MOD;
  
  cout << ans << endl;
  
}
### Prompt

Generate a Cpp solution to the following problem:

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.

Constraints

* 2 \leq N \times M \leq 2 \times 10^5
* 2 \leq K \leq N \times M
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M K


Output

Print the sum of the costs of all possible arrangements of the pieces, modulo 10^9+7.

Examples

Input

2 2 2


Output

8


Input

4 5 4


Output

87210


Input

100 100 5000


Output

817260251

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

//mod逆元を使ったnCkの計算(速)
const int64_t MAX = 510000;
const int64_t MOD = 1000000007;

int64_t fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
int64_t COM(int64_t n, int64_t k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  int64_t N, M, K;
  cin >> N >> M >> K;
  int64_t ans = 0;
  
  int64_t n = N*(N*N-1) / 6;
  n %= MOD;
  n *= M*M;
  n %= MOD;
  
  int64_t m = M*(M*M-1) / 6;
  m %= MOD;
  m *= N*N;
  m %= MOD;
  
  ans = n + m;
  ans %= MOD;

  
  COMinit();
  int64_t all = COM(N*M-2,K-2);
  
  ans *= all;
  ans %= MOD;
  
  cout << ans << endl;
  
}
```