310285: CF1809G. Prediction

G. Predictiontime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Consider a tournament with $n$ participants. The rating of the $i$-th participant is $a_i$.

The tournament will be organized as follows. First of all, organizers will assign each participant an index from $1$ to $n$. All indices will be unique. Let $p_i$ be the participant who gets the index $i$.

Then, $n-1$ games will be held. In the first game, participants $p_1$ and $p_2$ will play. In the second game, the winner of the first game will play against $p_3$. In the third game, the winner of the second game will play against $p_4$, and so on — in the last game, the winner of the $(n-2)$-th game will play against $p_n$.

Monocarp wants to predict the results of all $n-1$ games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings $x$ and $y$ play, and $|x - y| > k$, the participant with the higher rating wins. But if $|x - y| \le k$, any of the two participants may win.

Among all $n!$ ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all $n-1$ games. Since the answer can be large, print it modulo $998244353$.

Input

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^6$; $0 \le k \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$).

Output

Print one integer — the number of ways to assign the indices to the participants so that Monocarp can predict the results of all $n-1$ games.

ExamplesInput

4 3
7 12 17 21

Output

24

Input

3 7
4 9 28

Output

4

Input

4 1
1 2 3 4

Output

0

Input

4 1
1 2 2 4

Output

12

Input

16 30
8 12 15 27 39 44 49 50 51 53 58 58 59 67 68 100

Output

527461297

Note

In the first example, a match with any pair of players can be predicted by Monocarp, so all $24$ ways to assign indices should be counted.

In the second example, suitable ways are $[1, 3, 2]$, $[2, 3, 1]$, $[3, 1, 2$] and $[3, 2, 1]$.

题目大意：
预测比赛结果。有n个参赛者，第i个参赛者的等级为a_i。首先给每个参赛者分配一个从1到n的唯一编号，设p_i为获得编号i的参赛者。然后进行n-1场比赛，第一场是p_1和p_2，第二场是第一场的胜者和p_3，以此类推，最后一场是第n-2场的胜者和p_n。已知如果两个参赛者的等级差大于k，等级高的获胜；如果等级差小于等于k，则任何一方可能获胜。在所有n!种分配编号的方式中，计算能预测所有n-1场比赛结果的方式数量，结果对998244353取模。

输入数据格式：
第一行包含两个整数n和k（2≤n≤10^6；0≤k≤10^9）。
第二行包含n个整数a_1, a_2, …, a_n（0≤a_1≤a_2≤…≤a_n≤10^9）。

输出数据格式：
打印一个整数，即能预测所有n-1场比赛结果的分配编号方式数量。题目大意： 预测比赛结果。有n个参赛者，第i个参赛者的等级为a_i。首先给每个参赛者分配一个从1到n的唯一编号，设p_i为获得编号i的参赛者。然后进行n-1场比赛，第一场是p_1和p_2，第二场是第一场的胜者和p_3，以此类推，最后一场是第n-2场的胜者和p_n。已知如果两个参赛者的等级差大于k，等级高的获胜；如果等级差小于等于k，则任何一方可能获胜。在所有n!种分配编号的方式中，计算能预测所有n-1场比赛结果的方式数量，结果对998244353取模。 输入数据格式： 第一行包含两个整数n和k（2≤n≤10^6；0≤k≤10^9）。 第二行包含n个整数a_1, a_2, …, a_n（0≤a_1≤a_2≤…≤a_n≤10^9）。 输出数据格式： 打印一个整数，即能预测所有n-1场比赛结果的分配编号方式数量。