令 $B$ 為一個長度為 $M$ 且由正整數組成的陣列。
在一次操作中,你可以選擇一個非空的下標子序列$^\dagger$ $1 \le i_1 < i_2 < \dots < i_k \le M$,使得對應的值 $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ 兩兩不同,然後將每個選定位置的值減 $1$。
定義 $B$ 的分數(記作 $\text{score}(B)$)為使 $B$ 的每個元素都變為 $0$ 所需的最少操作次數。
給定一個長度為 $N$ 的陣列 $A$。
求 $A$ 的所有非空子序列的分數之和。
由於結果可能很大,請將答案對 $998\,244\,353$ 取模後輸出。
$^\dagger$ 如果序列 $C$ 可以透過從 $D$ 中刪除若干個元素(可以不刪,也可以全刪)而不改變其餘元素的順序來獲得,則稱其為序列 $D$ 的子序列。
輸入格式
輸入按以下格式給出:
T N A_1 A_2 ... A_N :
- 所有輸入值均為整數。
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- 保證所有測試資料的 $N^2$ 之和不超過 $5000^2$。
輸出格式
對於每組測試資料,輸出一個整數—— $A$ 的所有非空子序列的分數之和對 $998\,244\,353$ 取模後的結果。
範例
範例輸入 1
3 1 5 3 1 1 3 4 2 2 2 2
範例輸出 1
5 16 47
說明
測試資料 1:唯一的非空子序列是 $[5]$,其分數為 $5$。因此,答案為 $5$。
測試資料 2:$[1, 1, 3]$ 的非空子序列有:
- 兩個等於 $[1]$ 的子序列,每個的分數為 $1$;
- $[3]$,其分數為 $3$;
- $[1, 1]$,其分數為 $2$;
- 兩個等於 $[1, 3]$ 的子序列,每個的分數為 $3$;
- $[1, 1, 3]$,其分數為 $3$。
因此,總和為 $16$。