说明

你是 Jag 航空集团的一名机场接待员。这里有 $N$ 位乘客，你已从每位乘客那里收到了一件行李。根据值机记录，你知道第 $i$ 位乘客的行李重量为 $A_i$ 千克。

然而，你忘记给行李贴上标签了。

如果你随机分配标签，那么为所有行李贴上正确标签的概率是 $\frac{1}{N!}$，这太低了。在思考如何提高这个概率时，你在仓库里发现了一台有点故障的电子秤。

经过一番调查，你发现当物品放在这台秤上时，它会显示不超过实际总重量的 $B^0, B^1, B^2, \ldots$（以千克为单位）中的最大值。这里的 $B$ 是一个给定的整数，且 $B \geq 2$。

你可以将任意非空子集的行李放在秤上，并且可以重复此操作任意多次。假设你采取最优策略，请找出为所有行李贴上正确标签的最大概率，并将答案对 $998244353 = 119 \times 2^{23} + 1$ 取模后输出。

什么是模 $998244353$ 下的概率？

可以证明，所求的概率总是有理数。在本问题的约束下，还可以证明，当用两个互质的整数 $P$ 和 $Q$ 将该值表示为 $\frac{P}{Q}$ 时，恰好存在一个整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请找出这个 $R$。

输入格式

输入包含多个测试用例。

第一行包含一个整数 $T$（$1 \leq T \leq 10$），表示测试用例的数量。

接下来是 $T$ 个测试用例。每个测试用例的格式如下。

$$\begin{aligned} & N \ B \\ & A_1 \ A_2 \ \ldots \ A_N \end{aligned}$$

对于每个测试用例，第一行包含两个整数 $N$（$1 \leq N \leq 300$）和 $B$（$2 \leq B \leq 1500$），分别表示行李的数量和电子秤的参数 $B$。

第二行包含 $N$ 个整数 $A_i$（$1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 1500$），表示第 $i$ 位乘客的行李重量。

此外，所有测试用例的 $N$ 的总和不超过 $300$。

输出格式

对于 $T$ 个测试用例，逐行输出答案。对于每个测试用例，输出在最优策略下为所有行李贴上正确标签的最大概率（对 $998244353$ 取模后的值）。

3
3 3
9 15 17
5 23
41 41 41 41 41
14 10
101 102 103 104 105 106 107 108 109 110 111 112 113 114

499122177
856826403
314148269

提示

在第一个测试用例中，如果你每次只放一件行李，秤总是显示 $3^2 = 9$（千克），因此你无法区分它们中的任何一个。但是，如果你每次放两件行李，只有组合 $15 + 17$ 会得到 $3^3 = 27$（千克）。因此，此时没有放在秤上的那件行李必定是标签为 $1$（$9$ 千克）的那件。由于标签为 $2$ 和 $3$ 的行李无法通过任何称量序列区分，所以最大概率为 $\frac{1}{2}$。

:::align{center} :::

翻译由 DeepSeek V3.2 完成