该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 X 的糖果促销策略很成功，现在糖果店只剩下了 $n$ 颗糖果，其中第 $i$ ($1 ≤ i ≤ n$) 颗糖果的原价为 $a_i$ 元。小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会 将每颗糖果的清仓价格分别定为 $1$ 元或 $2$ 元。设第 $i$ ($1 ≤ i ≤ n$) 颗糖果的清仓价格为 $w_i ∈ \{1, 2\}$ 元，则它的性. 价. 比. 被定义为原价与清仓价格的比值，即 $a_i / w_i$。 小 R 又带了 $m$ 元钱买糖果。这一次，小 R 希望他购买到的糖果的原价总和最大， 于是他采用了以下购买策略：将所有糖果按照性. 价. 比. 从. 大. 到. 小. 排. 序. ，然后依次考虑每一 颗糖果。具体地，若小 R 在考虑第 $i$ ($1 ≤ i ≤ n$) 颗糖果时剩余的钱至少为 $w_i$ 元，则他 会购买这颗糖果，否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果 的性价比相同，则小 R 会先考虑原. 价. 较. 高. 的糖果；若存在两颗糖果的性价比与原价均 相同，则小 R 会先考虑编号较小的糖果。

例如，若小 X 的糖果商店剩余 $3$ 颗糖果，原价分别为 $a_1 = 1$，$a_2 = 3$，$a_3 = 5$，而 清仓价格分别为 $w_1 = w_2 = 1$，$w_3 = 2$，则性价比分别为 $1, 3, \frac{5}{2}$。因此小 R 会先考虑第 $2$ 颗糖果，然后考虑第 $3$ 颗糖果，最后考虑第 $1$ 颗糖果。

小 R 想知道，在小 X 的所有 $2^n$ 种定价方案中，有多少种定价方案使得他按照上述 购买策略能购买到的糖果的原. 价. 总. 和. 最. 大. 。你需要帮助小 R 求出满足要求的定价方案 的数量。由于答案可能较大，你只需要求出答案对 $998244353$ 取模后的结果。

输入格式

从文件 sale.in 中读入数据。 本. 题. 包. 含. 多. 组. 测. 试. 数. 据. 。 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： • 第一行包含两个正整数 $n, m$，分别表示糖果的数量与小 R 的钱数。 • 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，分别表示每颗糖果的原价。

输出格式

输出到文件 sale.out 中。 对于每组测试数据，输出一行一个非负整数，表示使得小 R 购买到的糖果的原价 总和达到最大值的定价方案数对 $998244353$ 取模后的结果。

样例 1 输入

1 0 1
2 3 2
3 1 3 5

样例 1 输出

6

样例 1 解释

该样例即为【题目描述】中的例子。共有以下 $6$ 种定价方案使得小 R 购买到的糖 果原价总和最大，分别为： • $w_1 = w_2 = w_3 = 1$，小 R 购买到的糖果原价总和为 $8$； • $w_1 = w_3 = 1$，$w_2 = 2$，小 R 购买到的糖果原价总和为 $6$； • $w_1 = 1$，$w_2 = w_3 = 2$，小 R 购买到的糖果原价总和为 $5$； • $w_2 = w_3 = 1$，$w_1 = 2$，小 R 购买到的糖果原价总和为 $8$； • $w_3 = 1$，$w_1 = w_2 = 2$，小 R 购买到的糖果原价总和为 $5$； • $w_1 = w_2 = w_3 = 2$，小 R 购买到的糖果原价总和为 $5$。

注意：若 $w_1 = w_2 = 1$，$w_3 = 2$，则小 R 会依次购买第 $2$ 颗和第 $1$ 颗糖果，原价总 和为 $4$，但小 R 可以只购买第 $3$ 颗糖果，原价总和为 $5$。因此该定价方案无法使小 R 购 买到的糖果的原价总和达到最大值。

样例 2

见选手目录下的 sale/sale2.in 与 sale/sale2.ans。 该样例满足测试点 $1 ∼ 3$ 的约束条件。

样例 3

见选手目录下的 sale/sale3.in 与 sale/sale3.ans。 该样例满足测试点 $4, 5$ 的约束条件。

样例 4

见选手目录下的 sale/sale4.in 与 sale/sale4.ans。 该样例满足测试点 $7 ∼ 9$ 的约束条件。

样例 5

见选手目录下的 sale/sale5.in 与 sale/sale5.ans。 该样例满足测试点 $10 ∼ 12$ 的约束条件。

样例 6

见选手目录下的 sale/sale6.in 与 sale/sale6.ans。 该样例满足测试点 $13$ 的约束条件。

样例 7

见选手目录下的 sale/sale7.in 与 sale/sale7.ans。 该样例满足测试点 $14, 15$ 的约束条件。

样例 8

见选手目录下的 sale/sale8.in 与 sale/sale8.ans。 该样例满足测试点 $17$ 的约束条件。

样例 9

见选手目录下的 sale/sale9.in 与 sale/sale9.ans。 该样例满足测试点 $19, 20$ 的约束条件。

样例 10

见选手目录下的 sale/sale10.in 与 sale/sale10.ans。 该样例满足测试点 $21 ∼ 23$ 的约束条件。

样例 11

见选手目录下的 sale/sale11.in 与 sale/sale11.ans。 该样例满足测试点 $24, 25$ 的约束条件。

数据范围

设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有： • $1 ≤ t ≤ 5 × 10^4$； • $1 ≤ n ≤ 5000$，$N ≤ 5 × 10^4$，$1 ≤ m ≤ 2^n − 1$； • 对于所有 $1 ≤ i ≤ n$，均有 $1 ≤ a_i ≤ 10^9$。

特殊性质 A：$a_1 = a_2 = \cdots = a_n$。
特殊性质 B：对于所有 $1 ≤ i ≤ n$，均有 $a_i > 5 × 10^8$。