Problem Description

One day, Little M learned an algorithm called "fractional programming", which is used to solve the "fractional programming problem".

:::info[Fractional Programming Problem]{open}

There are $n$ items. The $i$-th item has a value of $a_i$ and a weight of $b_i$. Both $a_i$ and $b_i$ are positive integers.

Select $k$ items from the $n$ items, let the selected items be $i_1,i_2,\dots,i_k$, and maximize the value of

$$\frac{a_{i_1}+a_{i_2}+\dots+a_{i_k}}{b_{i_1}+b_{i_2}+\dots+b_{i_k}}$$

:::

Coincidentally, Little M had also solved a problem called sale. On a whim, he came up with a problem to test you.

Given $n,k$, and the value sequence $a$ of the items, find the number of possible weight sequences $b$ of the items satisfying $\bm{1 \le b_i \le 2}$, such that the following greedy strategy exactly finds the optimal solution to the "fractional programming problem":

• Sort the items in descending order of their values $\bm{a_i}$. For items with the same value, sort them in ascending order of their indices $\bm{i}$. Select the top $k$ items after sorting.

The answer should be modulo $998,244,353$.

Input Format

This problem contains multiple test cases.

The first line of the input contains a positive integer $T$, indicating the number of test cases.

Then, the $T$ test cases follow sequentially. For each test case:

• The first line contains two positive integers $n,k$.
• The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$.

Output Format

For each test case, output a single line containing a non-negative integer, representing the number of weight sequences $b$ satisfying the condition. The answer should be modulo $998,244,353$.

2
2 1
10 9
6 3
10 10 8 6 6 5

3
15

5
16 1
256 225 196 169 144 121 100 81 64 49 36 25 16 9 4 1
16 2
256 225 196 169 144 121 100 81 64 49 36 25 16 9 4 1
16 15
256 225 196 169 144 121 100 81 64 49 36 25 16 9 4 1
16 14
256 225 196 169 144 121 100 81 64 49 36 25 16 9 4 1
16 9
256 225 196 169 144 121 100 81 64 49 36 25 16 9 4 1

34816
18176
32996
16887
3171

Hint

Explanation for Sample #1

For the first test case, the weight sequences $b$ satisfying the condition are $(1,1),(1,2),(2,2)$. When $b=(2,1)$, the greedy solution is $\frac{a_1}{b_1}=\frac{10}{2}=5$, and the optimal solution is $\frac{a_2}{b_2}=\frac{9}{1}=9$, so the greedy strategy fails to find the optimal solution.

Data Range

This problem uses bundled subtasks.

For all test cases, it is guaranteed that $1 \le T \le 5$, $1 \le k \le n \le 2\,000$, and $1 \le a_i \le 10^9$.

::cute-table{tuack}

Subtask	$n \le$	$k$	Score
$1$	$5$	$\le n$	$10$
$2$	$16$	^
$3$	$40$		$15$
$4$	$200$
$5$	$2\,000$	$=1$	$5$
$6$	^	$=2$	$10$
$7$		$=n-1$	$5$
$8$		$=n-2$	$10$
$9$		$\le n$	$20$