Låt $B$ vara ett fält av längd $M$ bestående av positiva heltal.
I en operation får du välja en icke-tom delföljd$^\dagger$ av index $1 \le i_1 < i_2 < \dots < i_k \le M$ sådan att värdena $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ är parvis skilda, och sedan minska varje valt värde med $1$.
Definiera poängen för $B$, betecknad med $\text{score}(B)$, som det minsta antalet operationer som krävs för att göra varje element i $B$ lika med $0$.
Du får ett fält $A$ av längd $N$.
Bestäm summan av poängen över alla icke-tomma delföljder av $A$.
Eftersom värdet kan vara stort, skriv ut det modulo $998\,244\,353$.
$^\dagger$ En följd $C$ kallas en delföljd av en följd $D$ om den kan erhållas från $D$ genom att ta bort ett antal element, möjligen inga eller alla, utan att ändra ordningen på de återstående elementen.
Indata
Indatan ges i följande format:
T N A_1 A_2 ... A_N :
- Alla indatavärden är heltal.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Det garanteras att summan av $N^2$ över alla testfall inte överstiger $5000^2$.
Utdata
För varje testfall, skriv ut ett enda heltal — summan av poängen över alla icke-tomma delföljder av $A$, modulo $998\,244\,353$.
Exempel
Exempelindata 1
3 1 5 3 1 1 3 4 2 2 2 2
Exempelutdata 1
5 16 47
Förklaring
Testfall 1: Den enda icke-tomma delföljden är $[5]$, med poäng $5$. Därför är svaret $5$.
Testfall 2: De icke-tomma delföljderna av $[1, 1, 3]$ är:
- två delföljder lika med $[1]$, vardera med poäng $1$,
- $[3]$, med poäng $3$,
- $[1, 1]$, med poäng $2$,
- två delföljder lika med $[1, 3]$, vardera med poäng $3$,
- $[1, 1, 3]$, med poäng $3$.
Alltså är den totala summan $16$.