Random flips
Tag(s):

## 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

3 Address Code - On site Hackathon - Finals

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Game Theory
• Algorithms > Dynamic Programming
• Math > Number Theory