Факторизация положительного целого числа \(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\).
Выходные данные
Выведите одно целое число — количество положительных целых чисел \(m\), удовлетворяющих условию \(f(m)=\{a_1, a_2, \ldots, a_{2n}\}\), по модулю \(998\,244\,353\).
Примечание
В первом примере два значения \(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\) не являются простыми числами.