Вам задано число x, представленное в виде произведения n своих простых делителей p1⋅p2,⋅…⋅pn. Пусть S — это множество всех положительных целых делителей числа x (включая 1 и само число x).
Назовем множество (set) целых чисел D хорошим тогда (и только тогда), когда не существует пары a∈D, b∈D таких, что a≠b и a делит b.
Найдите хорошее подмножество S с максимально возможным размером. Так как ответ может быть очень большим, выведите размер подмножества по модулю 998244353.
В первой строке задано единственное число n (1≤n≤2⋅105) — количество простых делителей в представлении числа x.
Во второй строке заданы n простых чисел p1,p2,…,pn (2≤pi≤3⋅106) — разложение числа x на простые.
Выведите максимально возможный размер хорошего подмножества по модулю 998244353.
3 2999999 43 2999957
3
6 2 3 2 3 2 2
3
В первом примере x=2999999⋅43⋅2999957 и одним из его максимальных хороших подмножеств является {43,2999957,2999999}.
Во втором примере x=2⋅3⋅2⋅3⋅2⋅2=144 и одним из его максимальных хороших подмножеств является {9,12,16}.
