怯战蜥蜴 II

Problem Description

坎格鲁斯普雷正在和袋鼠将军麾下的爪牙们进行决斗。 袋鼠将军麾下一共有 $n$ 名爪牙，第 $i$ 名爪牙的实力为 $a_i$ ，坎格鲁斯普雷的实力为 $c$ 。 坎格鲁斯普雷在和爪牙们决斗前，先会评估爪牙们的实力，坎格鲁斯普雷评估爪牙的实力时会存在至多 $k$ 的误差。设坎格鲁斯普雷评估第 $i$ 名爪牙的实力为 $b_i$ ，则 $b_i$ 满足 $a_i-k \leq b_i \leq a_i+k$ 。由于坎格鲁斯普雷喜欢随机化算法，所以 $b_i$ 是在 $[a_i-k,a_i+k]$ 这个范围内均匀随机选取的一个整数。 由于坎格鲁斯普雷是怯战蜥蜴，所以坎格鲁斯普雷与爪牙们的决斗过程如下： 坎格鲁斯普雷会不断地从所有它评估的实力小于等于 $c$ 且还没有跟他决斗过的爪牙中随机挑选一名爪牙进行决斗 ，直到坎格鲁斯普雷的获胜的决斗场数达到了 $m$ ，输掉了某场决斗或者目前没有满足以上条件的爪牙能和坎格鲁斯普雷进行决斗，那么此时坎格鲁斯普雷就会化身怯战蜥蜴，停止决斗并落荒而逃。若坎格鲁斯普雷挑选的这名爪牙的实力小于等于 $c$ ，那么坎格鲁斯普雷会在这场决斗中获胜；否则坎格鲁斯普雷会输掉这场决斗。 现在，作为坎格鲁斯普雷的死对头的袋鼠将军想问问你，坎格鲁斯普雷的期望胜利场数是多少，可以证明，答案总为一个有理数，你需要输出它对 $998244353$ 取模后的结果。

Input

输入第一行一个整数 $T$ ，表示测试数据组数。 $(1 \leq T \leq 100)$ 对于每组测试数据，第一行四个整数 $n$ ， $m$ ， $c$ ， $k$ 。 $(1 \leq n \leq 2 \times 10^5,1 \leq m \leq 20,1 \leq c,k \leq 10^8)$ 第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$ 。 $(1 \leq a_i \leq 10^8)$ 数据保证 $\sum n \leq 10^6,\sum m \leq 100$ 。

Output

对于每组测试数据，输出一行一个整数表示答案，不同测试数据的答案之间需换行。

Sample Input

3
3 1 2 1
1 2 3
5 3 2139 200
1743 2142 2127 1753 2005
8 4 1600 600
800 1200 1400 1600 1900 2100 2300 2400

Sample Output

314262112
558102885
146453175

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）