给你一个多重集 $$$a$$$,它由 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ 组成。您想通过以下过程生成新的多重集 $$$s$$$:
- 将 $$$a$$$ 划分为任意数量的非空多重集 $$$x_1,x_2,\ldots,x_k$$$,使得 $$$a$$$ 的每个元素恰好属于这些多重集之一。
- 最初,$$$s$$$ 是空的。从每个 $$$x_i$$$ 中选择 一 其 模式$$$^{\text{*}}$$$ 并将其插入到 $$$s$$$ 中。
请计算通过该过程可以生成的不同多重集 $$$s$$$ 的数量,以 $$$998\,244\,353$$$ 为模。
请注意数量不同 多套 被计数,这意味着元素的顺序并不重要。然而,每个元素的计数确实很重要,即 $$$\{1,1,2\},\{1,2\},\{1,1,2,2\}$$$ 都被认为是不同的。
$$$^{\text{*}}$$$多重集的众数定义为出现次数最多的元素;如果多个元素都被视为最大值,则所有这些元素都被视为众数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le5000$$$) — 多重集 $$$a$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,打印一行包含一个整数 - 您可以获得的不同多重集的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
531 2 331 1 131 2 2101 1 1 1 2 2 2 3 3 4101 1 1 2 2 2 3 3 3 4
输出复制
734111126
注意
在第一个测试用例中,可以实现 $$$\{1,2,3\}$$$ 的任何非空子集,总共 $$$7$$$ 多重集。
在第三个测试用例中,我们可以生成 $$$4$$$ 不同的多重集:
- 将元素划分为集合 $$$\{1,2,2\}$$$,产生多重集 $$$\{2\}$$$。
- 将元素划分为集合 $$$\{1,2\},\{2\}$$$,得到多重集 $$$\{2,2\}$$$。
- 将元素划分为集合 $$$\{1\},\{2,2\}$$$,得到多重集 $$$\{1,2\}$$$。
- 将元素划分为集合 $$$\{1\},\{2\},\{2\}$$$,得到多重集 $$$\{1,2,2\}$$$。
可以证明没有其他多重集是可能的。