Вам задано число $$$x$$$, представленное в виде произведения $$$n$$$ своих простых делителей $$$p_1 \cdot p_2, \cdot \ldots \cdot p_n$$$. Пусть $$$S$$$ — это множество всех положительных целых делителей числа $$$x$$$ (включая $$$1$$$ и само число $$$x$$$).
Назовем множество (set) целых чисел $$$D$$$ хорошим тогда (и только тогда), когда не существует пары $$$a \in D$$$, $$$b \in D$$$ таких, что $$$a \ne b$$$ и $$$a$$$ делит $$$b$$$.
Найдите хорошее подмножество $$$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$$$.
3 2999999 43 2999957
3
6 2 3 2 3 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 \}$$$.
Название |
---|