D. Делители
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Каждое из $$$a_i$$$ имеет от $$$3$$$ до $$$5$$$ делителей. Пусть $$$a = \prod a_i$$$ — произведение всех входных чисел. Найдите количество делителей $$$a$$$. Поскольку это число может быть очень большим, выведите его остаток от деления на простое число $$$998244353$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 500$$$) — количество чисел.

Каждая из следующих $$$n$$$ строк содержит одно целое число $$$a_i$$$ ($$$1 \leq a_i \leq 2\cdot 10^{18}$$$). Гарантируется, что количество делителей каждого $$$a_i$$$ от $$$3$$$ до $$$5$$$.

Выходные данные

Выведите одно целое число $$$d$$$ — количество делителей произведения $$$a_1 \cdot a_2 \cdot \dots \cdot a_n$$$ по модулю $$$998244353$$$.

Входные данные для взломов

Для взломов нужно вводить тест в специальном формате.

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 500$$$) — количество чисел.

Каждая из следующих $$$n$$$ строк содержит число $$$a_i$$$, представленное как произведение чисел. Строка содержит целое число $$$k_i$$$ ($$$2 \leq k_i \leq 4$$$) — количество простых множителей $$$a_i$$$ и $$$k_i$$$ целых чисел $$$p_{i,j}$$$ ($$$2 \leq p_{i,j} \leq 2 \cdot 10^{18}$$$), где $$$p_{i,j}$$$ — $$$j$$$-й простой делитель $$$a_i$$$.

Перед тем, как запустить решение участника, будут посчитаны все $$$a_i = \prod p_{i,j}$$$. Заметьте, что все $$$p_{i,j}$$$ должны быть простыми числами, каждый посчитанный $$$a_i$$$ должен удовлетворять $$$a_i \leq 2\cdot10^{18}$$$ и должен иметь от $$$3$$$ до $$$5$$$ делителей. Участникам будут даны только $$$a_i$$$, а не простые множители.

Например, чтобы получить первый пример, нужно ввести такой тест:


3
2 3 3
2 3 5
2 11 13
Протокол взаимодействия

Технически данная задача является интерактивной. Поэтому после вывода ответа не забудьте вывести перевод строки и сбросить буфер вывода. При этом не нужно считывать больше, чем нужно. Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.
Примеры
Входные данные
3
9
15
143
Выходные данные
32
Входные данные
1
7400840699802997
Выходные данные
4
Входные данные
8 
4606061759128693
4606066102679989
4606069767552943
4606063116488033
4606063930903637
4606064745319241
4606063930904021
4606065559735517
Выходные данные
1920
Входные данные
3
4
8
16
Выходные данные
10
Примечание

В первом примере $$$a = 19305$$$. Его делители равны: $$$1, 3, 5, 9, 11, 13, 15, 27, 33, 39, 45, 55, 65, 99, 117, 135, 143, 165, 195, 297, 351, 429, 495, 585, 715, 1287, 1485, 1755, 2145, 3861, 6435, 19305$$$ — всего $$$32$$$ делителя.

Во втором примере $$$a$$$ имеет четыре делителя: $$$1$$$, $$$86028121$$$, $$$86028157$$$ и $$$7400840699802997 $$$.

В третьем примере $$$a = 202600445671925364698739061629083877981962069703140268516570564888699 375209477214045102253766023072401557491054453690213483547$$$.

В четвертом примере $$$a=512=2^9$$$, поэтому ответ $$$10$$$.