Score : 500 points
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.
Input is given from Standard Input in the following format:
N M K
Print the sum of the costs of all possible arrangements of the pieces, modulo 10^9+7.
2 2 2
8
There are six possible arrangements of the pieces, as follows:
The sum of these costs is 8.
4 5 4
87210
100 100 5000
817260251
Be sure to print the sum modulo 10^9+7.