Sekai ama los juegos de tablero. Esta vez está jugando Monstruos en el Calabozo, un videojuego que consiste en ubicar ~K~ monstruos en un tablero de dimensiones ~N \times M~ sin que ninguno de ellos se moleste. Cuando logra hacer esto gana la partida.

Un monstruo está molesto cuando algún otro se encuentra en la misma fila o columna que él. En el siguiente ejemplo se muestran configuraciones con monstruos molestos y sin ellos en un tablero de ~3 \times 3~.

• En el ejemplo de la izquierda el tablero no es válido porque los monstruos en las columnas 1 y 3 están ubicados en la misma fila y se molestarán.
• En el ejemplo de la derecha el tablero es válido, todos los monstruos están ubicados en filas y columnas distintas entre sí y no se molestarán.

Dadas las dimensiones del tablero ~N~ y ~M~ y la cantidad de monstruos ~K~, Sekai está interesado en contar la cantidad de maneras de ganar la partida. Ayúdalo a encontrar este número ~\mod 10^{9}+7~.

Entrada

La primera y unica línea contiene tres enteros ~1\leq N, M, K \leq 10^5~ la cantidad de filas, columnas y la cantidad de monstruos a ubicar respectivamente.

Salida

Imprima un solo entero, la cantidad de maneras de ganar la partida ~\mod 10^{9}+7~.

Subtareas

Subtareas:

• Subtarea 1: ~K=1~ (5 puntos).
• Subtarea 2: ~K=2, N,M\leq30~ (5 puntos).
• Subtarea 3: ~K=2~, sin restricciones para ~N~ y ~M~ (15 puntos).
• Subtarea 4: ~N\leq8~ y ~M\leq8~ (15 puntos)
• Subtarea 5: ~N\leq10^{3}~ y ~M\leq10^{3}~ (50 puntos)
• Subtarea 6: Sin restricciones adicionales (10 puntos)

Ejemplos

Entrada 1

4 1 1

Salida 1

4

Entrada 2

3 3 2

Salida 2

18

Entrada 3

3 3 3

Salida 3

6

Entrada 4

3 3 4

Salida 4

0