La $B$ være en tabell med lengde $M$ som består av positive heltall.
I én operasjon kan du velge en ikke-tom delfølge$^\dagger$ av indekser $1 \le i_1 < i_2 < \dots < i_k \le M$ slik at verdiene $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ er parvis forskjellige, og deretter redusere hver valgte verdi med $1$.
Definer poengsummen til $B$, betegnet med $\text{score}(B)$, som det minste antallet operasjoner som trengs for å gjøre hvert element i $B$ lik $0$.
Du får gitt en tabell $A$ med lengde $N$.
Finn summen av poengsummer over alle de ikke-tomme delfølgene av $A$.
Siden verdien kan være stor, skriv den ut modulo $998\,244\,353$.
$^\dagger$ En følge $C$ kalles en delfølge av en følge $D$ hvis den kan oppnås fra $D$ ved å slette flere elementer, muligens ingen eller alle, uten å endre rekkefølgen på de gjenværende elementene.
Inndata
Inndataene er gitt på følgende format:
T N A_1 A_2 ... A_N :
- Alle inndataverdier er heltall.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Det er garantert at summen av $N^2$ over alle testtilfeller ikke overstiger $5000^2$.
Utdata
For hvert testtilfelle, skriv ut ett enkelt heltall — summen av poengsummer over alle de ikke-tomme delfølgene av $A$, modulo $998\,244\,353$.
Eksempler
Eksempelinndata 1
3 1 5 3 1 1 3 4 2 2 2 2
Eksempelutdata 1
5 16 47
Merk
Testtilfelle 1: Den eneste ikke-tomme delfølgen er $[5]$, med poengsum $5$. Derfor er svaret $5$.
Testtilfelle 2: De ikke-tomme delfølgene av $[1, 1, 3]$ er:
- to delfølger lik $[1]$, hver med poengsum $1$,
- $[3]$, med poengsum $3$,
- $[1, 1]$, med poengsum $2$,
- to delfølger lik $[1, 3]$, hver med poengsum $3$,
- $[1, 1, 3]$, med poengsum $3$.
Den totale summen er altså $16$.