P7224 [RC-04] Subset Product

Given $n$ integers $a_1\sim a_n$, in the multiset formed by them, how many subsets have a product of elements greater than $m$? (The product of elements of the empty set is equal to $1$.) Two subsets are different if and only if the **indices** of the elements they contain are different. The answer is very large, so please output its value modulo $998244353$.

The first line contains two integers $n, m$. The next line contains $n$ positive integers $a_1\sim a_n$, describing this multiset.

Output one integer in one line, which is the answer modulo $998244353$.

[Sample $1$ Explanation] The following subsets satisfy the requirement: $\{a_3,a_4\}$, $\{a_1,a_3,a_4\}$, $\{a_2,a_3,a_4\}$, $\{a_1,a_2,a_3,a_4\}$. [Constraints] For all testdata, $0\le n,m\le 10^6$, $1\le a_i\le 10^6$. The detailed constraints are shown in the table below: | Test Point ID | $n$ | $m$ | $a_i$ | Score per Test Point | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $=0$ | | | $1$ | | $2$ | | $=0$ | | $1$ | | $3\sim 6$ | $\le 22$ | | | $4$ | | $7\sim 10$ | $\le 1000$ | $\le 1000$ | | $4$ | | $11\sim 14$ | | | All distinct | $4$ | | $15\sim 19$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | | $5$ | | $20\sim 24$ | | | | $5$ | Translated by ChatGPT 5