Вам задано число \(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\).
Выходные данные
Выведите максимально возможный размер хорошего подмножества по модулю \(998244353\).
Примечание
В первом примере \(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 \}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2999999 43 2999957
|
3
|
|
2
|
6
2 3 2 3 2 2
|
3
|