题目描述

某一天，小 M 学习了一个叫做「分数规划」的算法，它是用来解决「分数规划问题」的。

:::info[分数规划问题]{open}

有 $n$ 个物品，第 $i$ 个物品的价值为 $a_i$，重量为 $b_i$。$a_i,b_i$ 均为正整数。

从 $n$ 个物品中选出 $k$ 个，记所选物品为 $i_1,i_2,\dots,i_k$，最大化

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

的值。

:::

恰巧，小 M 还做过一道叫做 sale 的题。他突发奇想，便出了一道题来考考你。

给定 $n,k$，以及物品的价值序列 $a$，求有多少种物品的重量序列 $b$，满足 $\bm{1 \le b_i \le 2}$，使以下贪心策略恰好求得「分数规划问题」的最优解：

• 将物品 按价值 $\bm{a_i}$ 降序排序。对于价值相同的物品，按序号 $\bm{i}$ 升序排序。选取排序后的前 $k$ 个物品。

答案对 $998,244,353$ 取模。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据的组数。

接下来依次输入 $T$ 组测试数据。对于每组测试数据：

• 第一行，两个正整数 $n,k$。
• 第二行，$n$ 个正整数 $a_1,a_2,\dots,a_n$。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的物品的重量序列 $b$ 的个数。答案对 $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

提示

「样例 #1 解释」

对于第一组测试数据，满足条件的物品的重量序列 $b$ 有 $(1,1),(1,2),(2,2)$。当 $b=(2,1)$ 时，贪心解为 $\frac{a_1}{b_1}=\frac{10}{2}=5$，最优解为 $\frac{a_2}{b_2}=\frac{9}{1}=9$，贪心策略未求得最优解。

「数据范围」

本题采用子任务捆绑测试。

对于所有测试数据，保证 $1 \le T \le 5$，$1 \le k \le n \le 2\,000$，$1 \le a_i \le 10^9$。

::cute-table{tuack}

子任务	$n \le$	$k$	分值
$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$