题目描述

Arul 有一个长度为 $n$ 的二进制数组 $a$。

他将取出该数组所有长度为 $k$（$k$ 为奇数）的子序列，并找到它们的中位数。

所有这些中位数的值之和是多少？

由于这个和可能非常大，请输出它对 $10^9 + 7$ 取模的结果。换句话说，输出这个和除以 $10^9 + 7$ 的余数。

一个二进制数组是仅由 $0$ 和 $1$ 组成的数组。

数组 $b$ 是数组 $a$ 的子序列，如果 $b$ 可以通过从 $a$ 中删除若干（可能为零或全部）元素得到。子序列不要求连续。

长度为奇数 $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$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1999F，英文题名 Expected Median。