Sea $B$ un arreglo de longitud $M$ compuesto por enteros positivos.
En una operación, puedes elegir una subsecuencia no vacía$^\dagger$ de índices $1 \le i_1 < i_2 < \dots < i_k \le M$ tal que los valores $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ sean distintos dos a dos, y luego disminuir cada valor elegido en $1$.
Definimos la puntuación de $B$, denotada por $\text{score}(B)$, como el número mínimo de operaciones necesarias para hacer que todos los elementos de $B$ sean iguales a $0$.
Se te da un arreglo $A$ de longitud $N$.
Halla la suma de las puntuaciones sobre todas las subsecuencias no vacías de $A$.
Como el valor puede ser grande, imprímelo módulo $998\,244\,353$.
$^\dagger$ Una secuencia $C$ se llama subsecuencia de una secuencia $D$ si puede obtenerse a partir de $D$ eliminando varios elementos, posiblemente ninguno o todos ellos, sin cambiar el orden de los elementos restantes.
Entrada
La entrada se proporciona en el siguiente formato:
T N A_1 A_2 ... A_N :
- Todos los valores de entrada son enteros.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Se garantiza que la suma de $N^2$ en todos los casos de prueba no supera $5000^2$.
Salida
Para cada caso de prueba, imprime un único entero: la suma de las puntuaciones sobre todas las subsecuencias no vacías de $A$, módulo $998\,244\,353$.
Ejemplos
Entrada de ejemplo 1
3 1 5 3 1 1 3 4 2 2 2 2
Salida de ejemplo 1
5 16 47
Nota
Caso de prueba 1: La única subsecuencia no vacía es $[5]$, con puntuación $5$. Por lo tanto, la respuesta es $5$.
Caso de prueba 2: Las subsecuencias no vacías de $[1, 1, 3]$ son:
- dos subsecuencias iguales a $[1]$, cada una con puntuación $1$,
- $[3]$, con puntuación $3$,
- $[1, 1]$, con puntuación $2$,
- dos subsecuencias iguales a $[1, 3]$, cada una con puntuación $3$,
- $[1, 1, 3]$, con puntuación $3$.
Así que la suma total es $16$.