Let $B$ be an array of length $M$ consisting of positive integers.
In one operation, you may choose a non-empty subsequence$^\dagger$ of indices $1 \le i_1 < i_2 < \dots < i_k \le M$ such that the values $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ are pairwise distinct, and then decrease each chosen value by $1$.
Define the score of $B$, denoted by $\text{score}(B)$, as the minimum number of operations needed to make every element of $B$ equal to $0$.
You are given an array $A$ of length $N$.
Find the sum of score over all the non-empty subsequences of $A$.
Since the value might be large, output it modulo $998\,244\,353$.
$^\dagger$ A sequence $C$ is called a subsequence of a sequence $D$ if it can be obtained from $D$ by deleting several elements, possibly none or all of them, without changing the order of the remaining elements.
Input
The input is given in the following format:
T N A_1 A_2 ... A_N :
- All input values are integers.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- It is guaranteed that the sum of $N^2$ over all test cases does not exceed $5000^2$.
Output
For each test case, output a single integer — the sum of score over all the non-empty subsequences of $A$, modulo $998\,244\,353$.
Examples
Sample Input 1
3 1 5 3 1 1 3 4 2 2 2 2
Sample Output 1
5 16 47
Note
Test case 1: The only non-empty subsequence is $[5]$, with score $5$. Therefore, the answer is $5$.
Test case 2: The non-empty subsequences of $[1, 1, 3]$ are:
- two subsequences equal to $[1]$, each with score $1$,
- $[3]$, with score $3$,
- $[1, 1]$, with score $2$,
- two subsequences equal to $[1, 3]$, each with score $3$,
- $[1, 1, 3]$, with score $3$.
So, the total sum is $16$.