考虑一场有 $$$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]$$$。