Sei $B$ ein Array der Länge $M$, das aus positiven ganzen Zahlen besteht.
In einer Operation darfst du eine nicht-leere Teilfolge$^\dagger$ von Indizes $1 \le i_1 < i_2 < \dots < i_k \le M$ wählen, sodass die Werte $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ paarweise verschieden sind, und anschließend jeden gewählten Wert um $1$ verringern.
Definiere den Score von $B$, bezeichnet mit $\text{score}(B)$, als die minimale Anzahl von Operationen, die benötigt werden, um jedes Element von $B$ gleich $0$ zu machen.
Gegeben ist ein Array $A$ der Länge $N$.
Bestimme die Summe der Scores über alle nicht-leeren Teilfolgen von $A$.
Da der Wert groß sein kann, gib ihn modulo $998\,244\,353$ aus.
$^\dagger$ Eine Folge $C$ heißt Teilfolge einer Folge $D$, wenn sie aus $D$ durch Löschen mehrerer Elemente (möglicherweise keiner oder aller) erhalten werden kann, ohne die Reihenfolge der verbleibenden Elemente zu ändern.
Eingabe
Die Eingabe erfolgt im folgenden Format:
T N A_1 A_2 ... A_N :
- Alle Eingabewerte sind ganze Zahlen.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Es wird garantiert, dass die Summe von $N^2$ über alle Testfälle hinweg $5000^2$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall eine einzige ganze Zahl aus — die Summe der Scores über alle nicht-leeren Teilfolgen von $A$, modulo $998\,244\,353$.
Beispiele
Beispieleingabe 1
3 1 5 3 1 1 3 4 2 2 2 2
Beispielausgabe 1
5 16 47
Hinweis
Testfall 1: Die einzige nicht-leere Teilfolge ist $[5]$ mit Score $5$. Daher lautet die Antwort $5$.
Testfall 2: Die nicht-leeren Teilfolgen von $[1, 1, 3]$ sind:
- zwei Teilfolgen gleich $[1]$, jeweils mit Score $1$,
- $[3]$ mit Score $3$,
- $[1, 1]$ mit Score $2$,
- zwei Teilfolgen gleich $[1, 3]$, jeweils mit Score $3$,
- $[1, 1, 3]$ mit Score $3$.
Also beträgt die Gesamtsumme $16$.