All Tracks Math Problem

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...
Your Rating:

Contributor

This Problem was Asked in

Johnson & Johnson

Challenge Name

3 Address Code - On site Hackathon - Finals

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?