Monstruos en el Calabozo

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Sekai02

Problem type

Allowed languages

C++, Python

Sekai ama los juegos de tablero. Esta vez está jugando Monstruos en el Calabozo, un videojuego que consiste en ubicar $K$ ~K~ monstruos en un tablero de dimensiones $N \times M$ ~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$ ~3 \times 3~.

Sample

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$ ~N~ y $M$ ~M~ y la cantidad de monstruos $K$ ~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$ ~\mod 10^{9}+7~.

Entrada

La primera y unica línea contiene tres enteros $1\leq N, M, K \leq 10^5$ ~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$ ~\mod 10^{9}+7~.

Subtareas

Subtareas:

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

Ejemplos

Entrada 1

4 1 1

Salida 1

Entrada 2

3 3 2

Salida 2

Entrada 3

3 3 3

Salida 3

Entrada 4

3 3 4

Salida 4

Comments

1

Jona_Fonsi commented on May 22, 2026, 10:48 p.m.

1 0 1 0 1 0 0 0 0 0

2 0 0 1 1 0 0 0 0 0

3 1 0 0 0 1 0 0 0 0

4 0 0 1 0 1 0 0 0 0

5 1 0 0 0 0 1 0 0 0

6 0 1 0 0 0 1 0 0 0

7 0 1 0 0 0 0 1 0 0

8 0 0 1 0 0 0 1 0 0

9 0 0 0 0 1 0 1 0 0

10 0 0 0 0 0 1 1 0 0

11 1 0 0 0 0 0 0 1 0

12 0 0 1 0 0 0 0 1 0

13 0 0 0 1 0 0 0 1 0

14 0 0 0 0 0 1 0 1 0

15 1 0 0 0 0 0 0 0 1

16 0 1 0 0 0 0 0 0 1

17 0 0 0 1 0 0 0 0 1

18 0 0 0 0 1 0 0 0 1

[Program finished]

0

Rafael_Balseiro commented on May 22, 2026, 12:27 a.m.

Alguien me puede explicar porque en el caso 2 la respuesta es 18?