题目描述
Problem Background
Xiao K is a high school student who has just finished the college entrance examination. He is planning a graduation trip but is stuck with some details. Help him out!
Problem Description
The graduation trip plan includes $n$ attractions, which will be visited in a certain order, with each attraction being visited exactly once.
Each attraction has a coordinate $a_i$. Traveling by car from an attraction at coordinate $a$ to another at coordinate $b$ will cause discomfort of $a \times b$. The discomfort resets to zero after each trip (i.e., discomfort does not accumulate). If the discomfort of a trip exceeds a constant $w$, someone will get sick.
Xiao K wants to know how many ways there are to visit all attractions such that no one gets sick throughout the trip. The answer should be taken 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 a single integer, which is the answer.
Sample Input and Output
Sample Input #1
3 3
1 2 3
Sample Output #1
2
Sample Input #2
6 5
1 1 4 5 1 4
Sample Output #2
144
Sample Input #3
16 20
9 9 3 2 4 4 8 5 3 -1 -9 -1 -9 -8 -1 0
Sample Output #3
802901549
Notes
Sample Explanation
For Sample #1, there are two valid orders: $2-1-3$ and $3-1-2$.
Data Range
This problem consists of 10 subtasks. You need to pass all test cases within a subtask to earn the points for that subtask.
For all data, $0 \le w, |a_i| \le 10^9$, $1 \le n \le 50000$.
| # | $n$ | $a$ | Points |
|---|---|---|---|
| 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$ | Only three distinct $a_i$, $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$ |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分