Pak Chanek 被赋予一个由 $$$n$$$ 整数组成的数组 $$$a$$$。对于每个 $$$i$$$ ($$$1 \leq i \leq n$$$),Pak Chanek 会在白板上写下单元素集 $$$\{a_i\}$$$。
之后,在一次操作中,Pak Chanek 可能会执行以下操作:
1. 在白板上选择两个不同的集合 $$$S$$$ 和 $$$T$$$,使得 $$$S \cap T = \varnothing$$$ ($$$S$$$ 和 $$$T$$$ 没有任何共同元素)。
2. 从白板上擦除 $$$S$$$ 和 $$$T$$$,并将 $$$S \cup T$$$ ($$$S$$$ 和 $$$T$$$ 的并集)写入白板上。
执行零次或多次操作后,Pak Chanek 将构造一个多重集 $$$M$$$,其中包含写在白板上的所有集合的大小。换句话说,$$$M$$$中的每个元素对应于运算后集合的大小。
此过程可以创建多少个不同的$$$^\dagger$$$多重集$$$M$$$?由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。
$$$^\dagger$$$ 多重集 $$$B$$$ 和 $$$C$$$ 是不同的,当且仅当存在一个值 $$$k$$$,使得 $$$B$$$ 中值为 $$$k$$$ 的元素数量与 $$$C$$$ 中值为 $$$k$$$ 的元素数量不同。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。
输出
输出不同多重集 $$$M$$$ 模 $$$998\,244\,353$$$ 的数量。
示例
输入 #1
6 1 1 2 1 4 3
输出 #1
7
输入 #2
7 3 5 4 3 7 4 5
输出 #2
11
注意
在第一个示例中,可能的多重集 $$$M$$$ 为 $$$\{1,1,1,1,1,1\}$$$, $$$\{1,1,1,1,2\}$$$, $$$\{1,1,1,3\}$$$, $$$\{1,1,2,2\}$$$, $$$\{1,1,4\}$$$、$$$\{1,2,3\}$$$ 和 $$$\{2,2,2\}$$$。
作为示例,让我们考虑可能的操作顺序。
1. 开始时,集合为 $$$\{1\}$$$、$$$\{1\}$$$、$$$\{2\}$$$、$$$\{1\}$$$、$$$\{4\}$$$ 和 $$$\{3\}$$$。
2. 对集合 $$$\{1\}$$$ 和 $$$\{3\}$$$ 进行运算。现在,集合为 $$$\{1\}$$$、$$$\{1\}$$$、$$$\{2\}$$$、$$$\{4\}$$$ 和 $$$\{1,3\}$$$。
3. 对集合 $$$\{2\}$$$ 和 $$$\{4\}$$$ 进行运算。现在,集合为 $$$\{1\}$$$、$$$\{1\}$$$、$$$\{1,3\}$$$ 和 $$$\{2,4\}$$$。
4. 对集合 $$$\{1,3\}$$$ 和 $$$\{2,4\}$$$ 进行运算。现在,这些集合是 $$$\{1\}$$$、$$$\{1\}$$$ 和 $$$\{1,2,3,4\}$$$。
5. 构造的多重集 $$$M$$$ 为 $$$\{1,1,4\}$$$。