D. Marble Council

D. Marble Council

时间限制：每测试点 2 秒
内存限制：512 MB

问题描述

给定一个多重集 $a$，包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。你需要通过以下过程生成一个新的多重集 $s$：

1. 将 $a$ 划分为任意数量的非空多重集 $x_1, x_2, \dots, x_k$，使得 $a$ 中的每个元素恰好属于其中一个多重集。
2. 初始时 $s$ 为空。从每个 $x_i$ 中选择它的一个众数*，并将其插入 $s$。

请计算通过此过程可以生成的不同多重集 $s$ 的数量，对 $998244353$ 取模。

请注意，这里统计的是不同多重集的数量，这意味着元素的顺序不重要。但是，每个元素的数量很重要，即 $\{1,1,2\}$、$\{1,2\}$、$\{1,1,2,2\}$ 都被认为是不同的。

• 多重集的众数定义为出现次数最多的元素；如果有多个元素出现次数相同且都是最大值，那么它们都被视为众数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \leq t \leq 5000$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$）—— 多重集 $a$ 的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。

保证所有测试用例的 $n$ 之和不超过 $5000$。

输出格式

对于每个测试用例，输出一行包含一个整数 —— 你可以获得的不同多重集的数量，对 $998244353$ 取模。

样例输入

5
3
1 2 3
3
1 1 1
3
1 2 2
10
1 1 1 1 2 2 2 3 3 4
10
1 1 1 2 2 2 3 3 3 4

样例输出

7
3
4
111
126

样例说明

第一个测试用例中，$\{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\}$。

可以证明没有其他多重集是可能的。