Reflector del Cielo


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Authors:
Problem type
Allowed languages
C, C++, Go, Java, Python

En una cuadrícula de N filas y M columnas, podemos escribir un entero entre 1 y K (inclusive) en cada cuadro y definimos las secuencias A,B de la siguiente manera:

  • Por cada i = 1,...,N , A_{i} es el mínimo valor escrito en un cuadro de la i-ésima fila.
  • Por cada j = 1,...,M , B_{j} es el máximo valor escrito en un cuadro de la j-ésima columna.

Dado N, M, K, encuentra el número de pares de secuencias diferentes que pueden ser (A,B), módulo 998244353. Una secuencia (A,B) es diferente a una secuencia (A\prime,B\prime) si existe un i (1 \leq i \leq N) tal que A_{i} \neq A\prime_{i} o si existe un j (1 \leq j \leq M) tal que B_{j} \neq B\prime_{j}.

Este problema no tendrá puntuación parcial.

Entrada

Una única línea con tres enteros N, M y K (1 \leq N,M,K \leq 200\,000) separados con espacios.

Salida

De como salida el número de pares de secuencias diferentes que pueden ser (A,B), módulo 998244353.

Ejemplos

Entrada 1
2 2 2
Salida 1
7

(A_1,A_2,B_1,B_2) pueden ser (1,1,1,1), (1,1,1,2), (1,1,2,1), (1,1,2,2), (1,2,2,2), (2,1,2,2), or (2,2,2,2) - hay siete candidatos.

Entrada 2
1 1 100
Salida 2
100
Entrada 3
31415 92653 58979
Salida 3
469486242

Comments

There are no comments at the moment.