题目背景：

Arul 是一位热爱数学与编程的年轻人，他在一次参加编程比赛时遇到了一个有趣的问题。这道题的背景是这样的：

在一个虚拟世界中，所有的数据都是由二进制数组表示的。Arul 在这个世界中发现了一个神秘的二进制数组 $a$，它的每个元素只有两种可能的值：0 或者 1。这个数组具有特殊的性质，能够表示某些有趣的统计信息。

一天，Arul 在研究这个数组时，发现了一个挑战：他想要计算数组中所有长度为 $k$（$k$ 为奇数）的子序列的中位数的总和。为了更好地理解这个问题，Arul 决定深入分析这些子序列的特点，并计算它们的中位数。

经过一番思考，Arul 得出了一个结论：每个子序列的中位数取决于其排序后中间位置的元素。而由于数组的长度较大，这些子序列的数量和计算中位数的过程可能会非常复杂，最终的结果可能会非常庞大。

为了避免计算时出现溢出，Arul 决定将结果对 $10^9 + 7$ 取余，这样既可以保证计算结果不会超出范围，又能够得到最终的正确答案。

于是，Arul 向你提出了这个问题，想要你帮他解决并计算出最终的结果。

你准备好接受挑战了吗？ 注释：

• 数组的中位数是指将数组排序后，取排序后中间位置的元素。如果数组长度为 $k$（为奇数），那么中位数是排序后的第 $\frac{k+1}{2}$ 个元素。

输入

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $k$ 为奇数) — 数组的长度和子序列的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_i$ ($0 \leq a_i \leq 1$) — 数组的元素。

可以保证所有测试用例的 $n$ 值的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出总和对 $10^9 + 7$ 取余后的结果。

输入样例：

8
4 3
1 0 0 1
5 1
1 1 1 1 1
5 5
0 1 0 1 0
6 3
1 0 1 0 1 1
4 3
1 0 1 1
5 3
1 0 1 1 0
2 1
0 0
34 17
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出样例：

2
5
0
16
4
7
0
333606206

注意

在第一个测试用例中，数组 $[1,0,0,1]$ 中有四个长度为 $k=3$ 的子序列：

• $[1,0,0]$：中位数 $= 0$。
• $[1,0,1]$：中位数 $= 1$。
• $[1,0,1]$：中位数 $= 1$。
• $[0,0,1]$：中位数 $= 0$。

这些中位数的总和是 $0 + 1 + 1 + 0 = 2$。

在第二个测试用例中，所有长度为 $1$ 的子序列的中位数都是 $1$，因此答案是 $5$。

来源

code.cpp 题目.md 题解