P16281 「MierOI R1」Beyond

某一天，小 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](https://www.luogu.com.cn/problem/P14636) 的题。他突发奇想，便出了一道题来考考你。 给定 $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$ 取模。

#### 「样例 #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$ | ^ | $10$ | | $3$ | $40$ | ^ | $15$ | | $4$ | $200$ | ^ | $15$ | | $5$ | $2\,000$ | $=1$ | $5$ | | $6$ | ^ | $=2$ | $10$ | | $7$ | ^ | $=n-1$ | $5$ | | $8$ | ^ | $=n-2$ | $10$ | | $9$ | ^ | $\le n$ | $20$ |