Random flips
/

## Basic Probability, Mathematics, Medium-Hard, Probability, Probablity

Problem
Editorial
Analytics

Consider a matrix with $n$ rows and $m$ columns where each cell contains a value $0$. You are required to perform the following operation $k$ times:

• From the set of submatrices, select one submatrix at random.
• Toggle all the values in the selected submatrix. In other words, change all cells with a value $0$ to $1$ and vice versa.

Determine the expected sum of the matrix after completion of all the $k$ operations. Let this value be $E = \dfrac{P}{Q}$. Print the value of $P \cdot Q^{-1}$ modulo $10^9 + 7$, where $Q^{-1}$ denotes the modular inverse of $Q$ modulo $10^9 + 7$.

Input format

First line: Three integers $n, m$  and $k$

Output format

Print the value of $P \cdot Q^{-1}$ modulo $10^9 + 7$.

Constraints

$1 \le n, m \le 10^9$

$1 \le k \le 1000$

SAMPLE INPUT
1 2 1
SAMPLE OUTPUT
333333337

Explanation

There are three submatrices in total. One submatrix is equal to the full matrix, while the other two submatrices consist of one cell each.

With a probability $\dfrac{2}{3}$, a submatrix with one cell is chosen and we get the sum as $1$.

With a probability $\dfrac{1}{3}$, the full matrix  is chosen and we get the sum as $2$.

The expected value is hence $\dfrac{2}{3} \times 1 + \dfrac{1}{3} \times 2 = \dfrac{4}{3}$

$3^{-1} = 333333336$ modulo $10^9 + 7$.

Thus we print $4 \times 333333336$ modulo $10^9 + 7$, which is $333333337$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...