← 返回题目列表

Codeforces · 1999/F

F. 预期中位数

中文机器翻译题面 查看原题

Arul 有一个二进制数组$$$^{\text{*}}$$$ $$$a$$$,长度为$$$n$$$。

他将获取此数组中长度为 $$$k$$$($$$k$$$ 为奇数)的所有子序列$$$^{\text{†}}$$$,并找到它们的中位数。$$$^{\text{‡}}$$$

所有这些值的总和是多少?

由于这个总和可能非常大,因此输出它对 $$$10^9 + 7$$$ 取模。换句话说,打印该总和除以 $$$10^9 + 7$$$ 后的余数。

输入

第一行包含一个整数 $$$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$$$ 模的总和。

示例

输入 #1

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

输出 #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$$$。

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