D. Counting Factorizations
combinatorics; divide and conquer; dp; math; number theory
The prime factorization of a positive integer \(m\) is the unique way to write it as \(\displaystyle m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}\), where \(p_1, p_2, \ldots, p_k\) are prime numbers, \(p_1 < p_2 < \ldots < p_k\) and \(e_1, e_2, \ldots, e_k\) are positive integers. For each positive integer \(m\), \(f(m)\) is defined as the multiset of all numbers in its prime factorization, that is \(f(m)=\{p_1,e_1,p_2,e_2,\ldots,p_k,e_k\}\). For example, \(f(24)=\{2,3,3,1\}\), \(f(5)=\{1,5\}\) and \(f(1)=\{\}\).You are given a list consisting of \(2n\) integers \(a_1, a_2, \ldots, a_{2n}\). Count how many positive integers \(m\) satisfy that \(f(m)=\{a_1, a_2, \ldots, a_{2n}\}\). Since this value may be large, print it modulo \(998\,244\,353\).
The first line contains one integer \(n\) (\(1\le n \le 2022\)).The second line contains \(2n\) integers \(a_1, a_2, \ldots, a_{2n}\) (\(1\le a_i\le 10^6\)) — the given list.
Print one integer, the number of positive integers \(m\) satisfying \(f(m)=\{a_1, a_2, \ldots, a_{2n}\}\) modulo \(998\,244\,353\).
In the first sample, the two values of \(m\) such that \(f(m)=\{1,2,3,3\}\) are \(m=24\) and \(m=54\). Their prime factorizations are \(24=2^3\cdot 3^1\) and \(54=2^1\cdot 3^3\).In the second sample, the five values of \(m\) such that \(f(m)=\{2,2,3,5\}\) are \(200, 225, 288, 500\) and \(972\).In the third sample, there is no value of \(m\) such that \(f(m)=\{1,4\}\). Neither \(1^4\) nor \(4^1\) are prime factorizations because \(1\) and \(4\) are not primes.