令 $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$ 中删除若干个元素（可以不删，也可以全删）而不改变其余元素的顺序来获得，则称序列 $C$ 是序列 $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$。