D. Подсчет факторизаций
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Факторизация положительного целого числа $$$m$$$ — это единственный способ записать его в виде $$$\displaystyle m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}$$$, где $$$p_1, p_2, \ldots, p_k$$$ — простые числа, $$$p_1 < p_2 < \ldots < p_k$$$ и $$$e_1, e_2, \ldots, e_k$$$ — положительные целые числа.

Для каждого положительного целого числа $$$m$$$, определим $$$f(m)$$$ как мультимножество всех чисел в его факторизации, то есть $$$f(m)=\{p_1,e_1,p_2,e_2,\ldots,p_k,e_k\}$$$ .

Например, $$$f(24)=\{2,3,3,1\}$$$, $$$f(5)=\{1,5\}$$$ и $$$f(1)=\{\}$$$.

Вам задан список, состоящий из $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$. Подсчитайте, сколько положительных целых чисел $$$m$$$ удовлетворяют условию $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$, поскольку это число может быть большим, выведите его по модулю $$$998\,244\,353$$$.

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

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

Вторая строка содержит $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1\le a_i\le 10^6$$$) — заданный список.

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

Выведите одно целое число — количество положительных целых чисел $$$m$$$, удовлетворяющих условию $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
2
1 3 2 3
Выходные данные
2
Входные данные
2
2 2 3 5
Выходные данные
5
Входные данные
1
1 4
Выходные данные
0
Примечание

В первом примере два значения $$$m$$$, такие что $$$f(m)=\{1,2,3,3\}$$$: $$$m=24$$$ и $$$m=54$$$. Их факторизации: $$$24=2^3\cdot 3^1$$$ и $$$54=2^1\cdot 3^3$$$.

Во втором примере пять значений $$$m$$$, таких что $$$f(m)=\{2,2,3,5\}$$$: $$$200, 225, 288, 500$$$ и $$$972$$$.

В третьем примере не существует такого значения $$$m$$$, что $$$f(m)=\{1,4\}$$$. Ни $$$1^4$$$, ни $$$4^1$$$ не являются факторизациями, потому что $$$1$$$ и $$$4$$$ не являются простыми числами.