Sia $B$ un array di lunghezza $M$ composto da interi positivi.
In un'operazione, puoi scegliere una sottosequenza non vuota$^\dagger$ di indici $1 \le i_1 < i_2 < \dots < i_k \le M$ tale che i valori $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ siano a due a due distinti, e poi diminuire ciascun valore scelto di $1$.
Definiamo il punteggio di $B$, indicato con $\text{score}(B)$, come il numero minimo di operazioni necessarie per rendere ogni elemento di $B$ uguale a $0$.
Ti viene dato un array $A$ di lunghezza $N$.
Trova la somma dei punteggi su tutte le sottosequenze non vuote di $A$.
Poiché il valore potrebbe essere grande, stampalo modulo $998\,244\,353$.
$^\dagger$ Una sequenza $C$ è detta sottosequenza di una sequenza $D$ se può essere ottenuta da $D$ cancellando diversi elementi, eventualmente nessuno o tutti, senza cambiare l'ordine degli elementi rimanenti.
Input
L'input è fornito nel seguente formato:
T N A_1 A_2 ... A_N :
- Tutti i valori di input sono interi.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- È garantito che la somma di $N^2$ su tutti i casi di test non supera $5000^2$.
Output
Per ogni caso di test, stampa un singolo intero — la somma dei punteggi su tutte le sottosequenze non vuote di $A$, modulo $998\,244\,353$.
Esempi
Input di esempio 1
3 1 5 3 1 1 3 4 2 2 2 2
Output di esempio 1
5 16 47
Nota
Caso di test 1: L'unica sottosequenza non vuota è $[5]$, con punteggio $5$. Pertanto, la risposta è $5$.
Caso di test 2: Le sottosequenze non vuote di $[1, 1, 3]$ sono:
- due sottosequenze uguali a $[1]$, ciascuna con punteggio $1$,
- $[3]$, con punteggio $3$,
- $[1, 1]$, con punteggio $2$,
- due sottosequenze uguali a $[1, 3]$, ciascuna con punteggio $3$,
- $[1, 1, 3]$, con punteggio $3$.
Quindi, la somma totale è $16$.