Soit $B$ un tableau de longueur $M$ composé d'entiers strictement positifs.
En une opération, vous pouvez choisir une sous-séquence non vide$^\dagger$ d'indices $1 \le i_1 < i_2 < \dots < i_k \le M$ telle que les valeurs $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ soient deux à deux distinctes, puis diminuer chaque valeur choisie de $1$.
On définit le score de $B$, noté $\text{score}(B)$, comme le nombre minimal d'opérations nécessaires pour rendre chaque élément de $B$ égal à $0$.
On vous donne un tableau $A$ de longueur $N$.
Trouvez la somme des scores sur toutes les sous-séquences non vides de $A$.
Comme cette valeur peut être grande, affichez-la modulo $998\,244\,353$.
$^\dagger$ Une séquence $C$ est appelée sous-séquence d'une séquence $D$ si elle peut être obtenue à partir de $D$ en supprimant plusieurs éléments, éventuellement aucun ou tous, sans changer l'ordre des éléments restants.
Entrée
L'entrée est donnée dans le format suivant :
T N A_1 A_2 ... A_N :
- Toutes les valeurs d'entrée sont des entiers.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Il est garanti que la somme des $N^2$ sur l'ensemble des cas de test ne dépasse pas $5000^2$.
Sortie
Pour chaque cas de test, affichez un seul entier — la somme des scores sur toutes les sous-séquences non vides de $A$, modulo $998\,244\,353$.
Exemples
Exemple d'entrée 1
3 1 5 3 1 1 3 4 2 2 2 2
Exemple de sortie 1
5 16 47
Note
Cas de test 1 : La seule sous-séquence non vide est $[5]$, de score $5$. Par conséquent, la réponse est $5$.
Cas de test 2 : Les sous-séquences non vides de $[1, 1, 3]$ sont :
- deux sous-séquences égales à $[1]$, chacune de score $1$,
- $[3]$, de score $3$,
- $[1, 1]$, de score $2$,
- deux sous-séquences égales à $[1, 3]$, chacune de score $3$,
- $[1, 1, 3]$, de score $3$.
Ainsi, la somme totale vaut $16$.