#P0007. 中位数之和

中位数之和

题目描述

Waylon 有一个二进制数组 aa ,它的长度为 nn。

他将取该数组长度为 kk ( kk 为奇数)的所有子序列 †^{\text{†}} ,并求出它们的中位数 ‡^{\text{‡}} 。

所有这些值的和是多少?

由于这个和可能非常大,因此输出它的模数 109+710^9 + 7 。换句话说,输出这个数除以 109+710^9 + 7 的余数。

输入格式

第一行包含一个整数 tt ( 1≤t≤1041 \leq t \leq 10^4 )--测试用例数。

每个测试用例的第一行包含两个整数 nn 和 kk ( 1≤k≤n≤2⋅1051 \leq k \leq n \leq 2 \cdot 10^5,kk 为奇数),分别是数组的长度和子序列的长度。

每个测试用例的第二行包含 nn 个整数 aia_i ( 0≤ai≤10 \leq a_i \leq 1 ) - 数组 aia_i 的元素。

保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5 。

输出格式

对于每个测试用例,输出所有可能的中位数的总和,对 109+710^9 + 7 取模。

样例 #1

样例输入 #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

提示

†^{\text{†}} 一个二进制数组是一个只由 0 和 1 组成的数组。

†^{\text{†}} 如果 bb 可以从 aa 中删除几个元素(可能是零,也可能是全部元素),那么数组 bb 就是数组 aa 的子序列。子序列不必是连续的。

‡^{\text{‡}} 长度为奇数 kk 的数组的中位数是排序后的第 k+12\frac{k+1}{2} 个元素。


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

  • [1,0,0][1,0,0] :中位数 =0= 0 。
  • [1,0,1][1,0,1] :中位数 =1= 1 。
  • [1,0,1][1,0,1] :中位数 =1= 1 。
  • [0,0,1][0,0,1] :中位数 =0= 0 。

结果之和为 0+1+1+0=20+1+1+0=2 。

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