问题描述

Arul 有一个长度为 ~n~ 的二进制数组~^{\text{∗}}~ ~a~。

他将取出该数组的所有长度为 ~k~（~k~ 为奇数）的子序列~^{\text{†}}~，并找出它们的中位数~^{\text{‡}}~。

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

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

~^{\text{∗}}~ 二进制数组是仅由零和一组成的数组。

~^{\text{†}}~ 如果数组 ~b~ 可以通过从数组 ~a~ 中删除若干（可能为零个或全部）元素得到，则 ~b~ 是 ~a~ 的一个子序列。子序列不必是连续的。

~^{\text{‡}}~ 长度为奇数 ~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~。