У вас есть \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Каждое из \(a_i\) имеет от \(3\) до \(5\) делителей. Пусть \(a = \prod a_i\) — произведение всех входных чисел. Найдите количество делителей \(a\). Поскольку это число может быть очень большим, выведите его остаток от деления на простое число \(998244353\).
Выходные данные
Выведите одно целое число \(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;
- смотрите документацию для других языков.
Примечание
В первом примере \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
9
15
143
|
32
|
|
2
|
1
7400840699802997
|
4
|
|
3
|
8
4606061759128693
4606066102679989
4606069767552943
4606063116488033
4606063930903637
4606064745319241
4606063930904021
4606065559735517
|
1920
|
|
4
|
3
4
8
16
|
10
|