Little W has decided to go on a graduation trip to City T. There are $n$ tourist attractions in the city. He wants to start from his hotel, visit each attraction exactly once, and then return to the hotel.

However, Little W does not want to be too tired. Specifically, he feels tired when moving from one attraction to another. Each attraction $i$ has an integer weight $v_i$. If he moves from attraction $i$ to attraction $j$, his fatigue value for that move is $v_i \times v_j$. The total fatigue value of the entire trip is defined as the maximum fatigue value among all individual moves.

Little W wants to find a travel plan such that the total fatigue value is less than a non-negative integer $w$. He thinks this problem is too simple for you, so he wants to ask how many different travel plans satisfy this condition, modulo $998244353$.

Input Format

The first line contains two integers $n$ and $w$, representing the number of attractions and the limit on the fatigue value, respectively.

The second line contains $n$ integers $v_i$, representing the weight of each attraction.

Output Format

Output a single integer representing the answer.

Examples

Input 1

3 3
1 2 3

Output 1

2

Input 2

6 5
1 1 4 5 1 4

Output 2

144

Input 3

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

Output 3

802901549

Subtasks

For all data, $0 \le w, |v_i| \le 10^9$, $1 \le n \le 200000$.

• Subtask 1 (10 pts): $n \le 200$, $v_i \ge 0$
• Subtask 2 (10 pts): $n \le 2000$, $v_i \ge 0$
• Subtask 3 (10 pts): $n \le 50000$, $v_i \ge 0$
• Subtask 4 (10 pts): $n \le 200000$, $v_i \ge 0$
• Subtask 5 (10 pts): $n \le 200$
• Subtask 6 (10 pts): $n \le 2000$
• Subtask 7 (20 pts): $n \le 50000$
• Subtask 8 (20 pts): $n \le 200000$