設 $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$。