← 返回题目列表

Codeforces · 1809/G

G. 预测

中文机器翻译题面 查看原题

考虑一场有 $$$n$$$ 参与者的锦标赛。第 $$$i$$$ 参与者的评级为 $$$a_i$$$。

比赛将组织如下。首先,组织者将为每个参与者分配一个从$$$1$$$到$$$n$$$的索引。所有索引都是唯一的。令 $$$p_i$$$ 为获得索引 $$$i$$$ 的参与者。

然后将举行$$$n-1$$$场比赛。在第一场比赛中,参与者 $$$p_1$$$ 和 $$$p_2$$$ 将参加比赛。在第二场比赛中,第一场比赛的获胜者将对阵$$$p_3$$$。在第三场比赛中,第二场比赛的获胜者将对阵 $$$p_4$$$,依此类推 — 在最后一场比赛中,第 $$$(n-2)$$$ 场比赛的获胜者将对阵 $$$p_n$$$。

Monocarp想要预测所有$$$n-1$$$游戏的结果(当然,他只有在分配了参与者的索引后才会进行预测)。他确信,当两个评级为 $$$x$$$ 和 $$$y$$$ 的参与者玩游戏时,并且 $$$|x - y| > k$$$,评分较高的参与者获胜。但如果 $$$|x - y| \le k$$$,两个参与者中的任何一个都可能获胜。

在所有为参与者分配指数的 $$$n!$$$ 方法中,计算执行此操作的方法数量,以便 Monocarp 可以预测所有 $$$n-1$$$ 游戏的结果。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$0 \le k \le 10^9$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$)。

输出

打印一个整数 — 为参与者分配索引的方式数量,以便 Monocarp 可以预测所有 $$$n-1$$$ 游戏的结果。

示例

输入 #1

4 3
7 12 17 21

输出 #1

24

输入 #2

3 7
4 9 28

输出 #2

4

输入 #3

4 1
1 2 3 4

输出 #3

0

输入#4

4 1
1 2 2 4

输出#4

12

输入 #5

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

输出 #5

527461297

注意

在第一个示例中,Monocarp 可以预测任何一对玩家的比赛,因此所有分配索引的 $$$24$$$ 方式都应该被计算在内。

在第二个示例中,合适的方式是 $$$[1, 3, 2]$$$、$$$[2, 3, 1]$$$、$$$[3, 1, 2$$$] 和 $$$[3, 2, 1]$$$。