388. 【25NOIP提高组】清仓甩卖(sale) 中等

小 X 的糖果促销策略很成功，现在糖果店只剩下了 $n$ 颗糖果，其中第 $i (1 ≤ i ≤ n)$颗糖果的原价为 $a_i$ 元。小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会将每颗糖果的清仓价格分别定为 $1$ 元或 $2$ 元。设第 $i (1 ≤ i ≤ n)$ 颗糖果的清仓价格为$w_i ∈ \{1, 2\}$ 元，则它的性价比被定义为原价与清仓价格的比值，即 $\frac{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 求出满足要求的定价方案的数量。由于答案可能较大，你只需要求出答案对 $998, 244, 353$ 取模后的结果。