P5606 Xiao K and the Graduation Trip

Xiao K is a high school student who has just finished the college entrance exam. He is planning a graduation trip, but some details are troubling him. Please help him!

There are $n$ attractions in the graduation trip plan. Everyone will visit these attractions in some order, and each attraction will be visited exactly once. Each attraction has a coordinate $a_i$. Taking a ride from the attraction with coordinate $a$ to the attraction with coordinate $b$ will cause discomfort of $a \times b$. After getting off the vehicle each time, the discomfort is reset to $0$ (that is, discomfort does not accumulate). If the discomfort of any ride exceeds a certain constant $w$, someone will get sick. Xiao K wants to know how many visiting orders of all attractions make sure that no one gets sick throughout the whole trip. Output the answer modulo $998244353$.

The first line contains a positive integer $n$ and a non-negative integer $w$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output one line containing one integer, the answer.

**Sample Explanation** For sample $1$, there are two valid orders: $2-1-3$ and $3-1-2$. **Constraints** This problem has $10$ subtasks. You must pass all test points within a subtask to get the score for that subtask. For all data, $0 \le w, |a_i| \le 10^9$, $1 \le n \le 50000$. | # | $n$ | $a$ | Score | | ---- | ---- | ---- | ---- | | 1 | $n \le 10$ | No special restrictions | $5$ | | 2 | $n \le 20$ | No special restrictions | $5$ | | 3 | $n \le 2000 $ | $a_i \in \{ 1,w \}$ | $5$ | | 4 | $n\le 2000 $ | There are only three distinct $a_i$, and $a_i \ge 0$ | $5$ | | 5 | $n\le 200 $ | $a_i\ge 0 $ | $10$ | | 6 | $n\le 2000$ | $a_i\ge 0$ | $15$ | | 7 | $n\le 50000$ | $a_i \ge 0 $ | $20$ | | 8 | $n\le 200 $ | No special restrictions | $15$ | | 9 | $n\le 2000 $ | No special restrictions | $10$ | | 10 | $n\le 50000 $ | No special restrictions | $10$ | Translated by ChatGPT 5