Xiao X's candy promotion strategy has been very successful. There are now $n$ candies left in the shop, where the original price of the $i$-th ($1 \le i \le n$) candy is $a_i$ yuan. Xiao X plans to reprice all of them for a clearance sale. Specifically, Xiao X will set the clearance price of each candy to either 1 yuan or 2 yuan. Let $w_i \in \{1, 2\}$ be the clearance price of the $i$-th ($1 \le i \le n$) candy. Its cost-performance ratio is defined as the ratio of the original price to the clearance price, i.e., $\frac{a_i}{w_i}$.

Xiao R has brought $m$ yuan to buy candies. This time, Xiao R wants to maximize the total original price of the candies he purchases, so he adopts the following purchasing strategy: sort all candies by their cost-performance ratio in descending order, and then consider each candy one by one. Specifically, if Xiao R has at least $w_i$ yuan remaining when considering the $i$-th ($1 \le i \le n$) candy, he will purchase this candy; otherwise, he will skip this candy and continue to consider the next one. In particular, if two candies have the same cost-performance ratio, Xiao R will first consider the candy with the higher original price; if two candies have the same cost-performance ratio and the same original price, Xiao R will first consider the candy with the smaller index.

For example, if Xiao X's candy shop has 3 candies left with original prices $a_1 = 1, a_2 = 3, a_3 = 5$, and clearance prices $w_1 = w_2 = 1, w_3 = 2$, the cost-performance ratios are $1, 3, \frac{5}{2}$ respectively. Therefore, Xiao R will first consider the 2nd candy, then the 3rd candy, and finally the 1st candy.

Xiao R wants to know, among all $2^n$ possible pricing schemes by Xiao X, how many schemes allow him to maximize the total original price of the candies purchased using the above strategy. You need to help Xiao R find the number of pricing schemes that satisfy the requirements. Since the answer may be large, you only need to output the result modulo $998,244,353$.

Input

The input is read from the file sale.in.

This problem contains multiple test cases.

The first line contains two non-negative integers $c, t$, representing the test case ID and the number of test cases, respectively. $c = 0$ indicates that this test case is a sample.

Then, each test case is input sequentially. For each test case: The first line contains two positive integers $n, m$, representing the number of candies and the amount of money Xiao R has. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the original price of each candy.

Output

Output to the file sale.out.

For each test case, output a single non-negative integer representing the number of pricing schemes that allow Xiao R to achieve the maximum total original price of purchased candies, modulo $998,244,353$.

Examples

Input 1

0 1
3 2
1 3 5

Output 1

6

Note 1

This sample is the same as the example in the problem description. There are 6 pricing schemes that maximize the total original price of the candies purchased by Xiao R: $w_1 = w_2 = w_3 = 1$, total original price is 8; $w_1 = w_3 = 1, w_2 = 2$, total original price is 6; $w_1 = 1, w_2 = w_3 = 2$, total original price is 5; $w_2 = w_3 = 1, w_1 = 2$, total original price is 8; $w_3 = 1, w_1 = w_2 = 2$, total original price is 5; $w_1 = w_2 = w_3 = 2$, total original price is 5.

Note: If $w_1 = w_2 = 1, w_3 = 2$, Xiao R will purchase the 2nd and 1st candies in order, with a total original price of 4, but Xiao R could just purchase the 3rd candy, with a total original price of 5. Therefore, this pricing scheme does not allow Xiao R to achieve the maximum total original price.

Constraints

Let $N$ be the sum of $n$ over all test cases in a single test file. For all test cases: $1 \le t \le 5 \times 10^4$; $1 \le n \le 5,000$, $N \le 5 \times 10^4$, $1 \le m \le 2n - 1$; * For all $1 \le i \le n$, $1 \le a_i \le 10^9$.

Special Property A: $a_1 = a_2 = \dots = a_n$. Special Property B: For all $1 \le i \le n$, $a_i > 5 \times 10^8$.