CF2165B.Marble Council

You are given a multiset $a$, which consists of $n$ integers $a_1,a_2,\ldots,a_n$. You would like to generate a new multiset $s$ through the following procedure:

• Partition $a$ into any number of non-empty multisets $x_1,x_2,\ldots,x_k$, such that each element of $a$ belongs to exactly one of these multisets.
• Initially, $s$ is empty. From each $x_i$, choose one of its modes$^{\text{∗}}$ and insert it into $s$.

Please count the number of different multisets $s$ that can be generated through the procedure, modulo $998\,244\,353$.

Please note that the number of different multisets is counted, which means that the order of elements does not matter. However, the count of each element does matter, i.e. ${1,1,2},{1,2},{1,1,2,2}$ are all considered different.

$^{\text{∗}}$The mode of a multiset is defined as the element which appears the most; if several elements are tied as the maximum, then all of them are considered modes.

你被给定一个多重集 $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{∗}}$ 一个多重集的众数定义为其中出现次数最多的元素；若存在多个元素并列出现次数最多，则它们均被视为众数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le5000$) — the size of multiset $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print one line containing a single integer — the number of different multisets you can obtain, modulo $998\,244\,353$.

对于每个测试用例，输出一行，包含一个整数——你能得到的不同多重集的数量，对 $998\,244\,353$ 取模。

In the first test case, any non-empty subset of ${1,2,3}$ can be achieved, for a total of $7$ multisets.

In the third test case, we can generate $4$ different multisets:

• Partition the elements into set ${1,2,2}$, resulting in multiset ${2}$.
• Partition the elements into sets ${1,2},{2}$, resulting in multiset ${2,2}$.
• Partition the elements into sets ${1},{2,2}$, resulting in multiset ${1,2}$.
• Partition the elements into sets ${1},{2},{2}$, resulting in multiset ${1,2,2}$.

It can be proven that no other multisets are possible.

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

可以证明不存在其他可能的多重集。