Niech $B$ będzie tablicą o długości $M$ składającą się z dodatnich liczb całkowitych.
W jednej operacji możesz wybrać niepusty podciąg$^\dagger$ indeksów $1 \le i_1 < i_2 < \dots < i_k \le M$ taki, że wartości $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ są parami różne, a następnie zmniejszyć każdą wybraną wartość o $1$.
Zdefiniujmy wynik tablicy $B$, oznaczany przez $\text{score}(B)$, jako minimalną liczbę operacji potrzebnych, aby każdy element tablicy $B$ stał się równy $0$.
Dana jest tablica $A$ o długości $N$.
Wyznacz sumę wyników po wszystkich niepustych podciągach tablicy $A$.
Ponieważ wartość ta może być duża, wypisz ją modulo $998\,244\,353$.
$^\dagger$ Ciąg $C$ nazywamy podciągiem ciągu $D$, jeśli można go otrzymać z $D$ poprzez usunięcie kilku elementów (być może żadnego lub wszystkich) bez zmiany kolejności pozostałych elementów.
Wejście
Wejście jest podawane w następującym formacie:
T N A_1 A_2 ... A_N :
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- Gwarantuje się, że suma $N^2$ po wszystkich przypadkach testowych nie przekracza $5000^2$.
Wyjście
Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — sumę wyników po wszystkich niepustych podciągach tablicy $A$, modulo $998\,244\,353$.
Przykłady
Przykładowe wejście 1
3 1 5 3 1 1 3 4 2 2 2 2
Przykładowe wyjście 1
5 16 47
Uwaga
Przypadek testowy 1: Jedynym niepustym podciągiem jest $[5]$ o wyniku $5$. Zatem odpowiedź wynosi $5$.
Przypadek testowy 2: Niepustymi podciągami $[1, 1, 3]$ są:
- dwa podciągi równe $[1]$, każdy o wyniku $1$,
- $[3]$ o wyniku $3$,
- $[1, 1]$ o wyniku $2$,
- dwa podciągi równe $[1, 3]$, każdy o wyniku $3$,
- $[1, 1, 3]$ o wyniku $3$.
Zatem łączna suma wynosi $16$.