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$$$。