Divisor Set

题意翻译

给一个数 $m$ 的质因子分解 $m=\prod_{i=1}^np_i$，找出一个最大的集合 $S$ 满足 $\forall x\in S,\,x\mid m$ 且 $\forall x,\,y\in S,\,x\nmid y\;(x\neq y)$ 。 输出 $|S|\bmod 998244353$ 。

题目描述

You are given an integer $ x $ represented as a product of $ n $ its prime divisors $ p_1 \cdot p_2, \cdot \ldots \cdot p_n $ . Let $ S $ be the set of all positive integer divisors of $ x $ (including $ 1 $ and $ x $ itself). We call a set of integers $ D $ good if (and only if) there is no pair $ a \in D $ , $ b \in D $ such that $ a \ne b $ and $ a $ divides $ b $ . Find a good subset of $ S $ with maximum possible size. Since the answer can be large, print the size of the subset modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains the single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of prime divisors in representation of $ x $ . The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 2 \le p_i \le 3 \cdot 10^6 $ ) — the prime factorization of $ x $ .

输出格式

Print the maximum possible size of a good subset modulo $ 998244353 $ .

输入输出样例

输入样例 #1

3
2999999 43 2999957

输出样例 #1

3

输入样例 #2

6
2 3 2 3 2 2

输出样例 #2

3

说明

In the first sample, $ x = 2999999 \cdot 43 \cdot 2999957 $ and one of the maximum good subsets is $ \{ 43, 2999957, 2999999 \} $ . In the second sample, $ x = 2 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 2 = 144 $ and one of the maximum good subsets is $ \{ 9, 12, 16 \} $ .

题意翻译

给一个数 $m$ 的质因子分解 $m=\prod_{i=1}^np_i$，找出一个最大的集合 $S$ 满足 $\forall x\in S,\,x\mid m$ 且 $\forall x,\,y\in S,\,x\nmid y\;(x\neq y)$ 。 输出 $|S|\bmod 998244353$ 。