← 返回题目列表

Codeforces · 1257/G

G. 除数设置

中文机器翻译题面 查看原题

给定一个整数 $$$x$$$,表示为 $$$n$$$ 其素因数 $$$p_1 \cdot p_2, \cdot \ldots \cdot p_n$$$ 的乘积。令 $$$S$$$ 为 $$$x$$$ 的所有正整数除数的集合(包括 $$$1$$$ 和 $$$x$$$ 本身)。

当(且仅当)不存在一对 $$$a \in D$$$、$$$b \in D$$$ 使得 $$$a \ne b$$$ 和 $$$a$$$ 整除 $$$b$$$ 时,我们称一组整数 $$$D$$$ 为好。

找到 $$$S$$$ 的一个好的子集,其大小可能最大。由于答案可能很大,因此打印子集的大小对 $$$998244353$$$ 取模。

输入

第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 表示 $$$x$$$ 的素因数的数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$2 \le p_i \le 3 \cdot 10^6$$$) — $$$x$$$ 的质因数分解。

输出

打印一个好的子集模 $$$998244353$$$ 的最大可能大小。

示例

输入 #1

3
2999999 43 2999957

输出 #1

3

输入 #2

6
2 3 2 3 2 2

输出 #2

3

注意

在第一个样本中,$$$x = 2999999 \cdot 43 \cdot 2999957$$$,最大的好子集之一是 $$$\{ 43, 2999957, 2999999 \}$$$。

在第二个样本中,$$$x = 2 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 2 = 144$$$,最大的好子集之一是 $$$\{ 9, 12, 16 \}$$$。