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\)