Background

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!

Problem Description

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$.

Input Format

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 Format

Output one line containing one integer, the answer.

3 3
1 2 3

2

6 5
1 1 4 5 1 4

144

16 20
9 9 3 2 4 4 8 5 3 -1 -9 -1 -9 -8 -1 0

802901549

Hint

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$.

Translated by ChatGPT 5