给定一个整数 $$$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 \}$$$。