假设我们将数组 $$$b$$$ 的元素划分为任意数量的 $$$k$$$ 个非空多重集 $$$S_1, S_2, \ldots, S_k$$$,其中 $$$k$$$ 是任意正整数。将 $$$b$$$ 的分数定义为 $$$\operatorname{MEX}(S_1)$$$$$^{\text{∗}}$$$$$$ + \operatorname{MEX}(S_2) + \ldots + \operatorname{MEX}(S_k)$$$ 在 $$$b$$$ 的所有可能分区上对于任何整数 $$$k$$$ 的最大值。
Envy 被赋予一个大小为 $$$n$$$ 的数组 $$$a$$$。因为他知道计算$$$a$$$的分数对你来说太容易了,所以他转而要求你计算$$$a$$$的所有$$$2^n - 1$$$非空子序列的分数总和。$$$^{\text{†}}$$$由于这个答案可能很大,请输出它对$$$998\,244\,353$$$取模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < n$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出答案,模 $$$998\,244\,353$$$。
示例
输入 #1
4 3 0 0 1 4 0 0 1 1 5 0 0 1 2 2 4 1 1 1 1
输出 #1
11 26 53 0
注意
在第一个测试用例中,我们必须考虑七个子序列:
- $$$[0]$$$:得分为$$$1$$$。
- $$$[0]$$$:得分为$$$1$$$。
- $$$[1]$$$:得分为$$$0$$$。
- $$$[0,0]$$$:得分为 $$$2$$$。
- $$$[0,1]$$$:得分为$$$2$$$。
- $$$[0,1]$$$:得分为$$$2$$$。
- $$$[0,0,1]$$$:得分为$$$3$$$。
在最后一个测试用例中,所有子序列的分数均为 $$$0$$$。