G. Множество делителей
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано число $$$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 \}$$$.