All Tracks Math Problem
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\)
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 \).
CODE EDITOR
Contributor
This Problem was Asked in
Challenge Name
3 Address Code - On site Hackathon - Finals
3 Address Code - On site Hackathon - Finals
-
Algorithms > Dynamic Programming
-
Math > Game Theory
-
Algorithms > Dynamic Programming
-
Math > Number Theory
