Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×
F. Expected Median
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Arul has a binary array∗ a of length n.

He will take all subsequences† of length k (k is odd) of this array and find their median.‡

What is the sum of all these values?

As this sum can be very large, output it modulo 109+7. In other words, print the remainder of this sum when divided by 109+7.

∗A binary array is an array consisting only of zeros and ones.

†An array b is a subsequence of an array a if b can be obtained from a by the deletion of several (possibly, zero or all) elements. Subsequences don't have to be contiguous.

‡The median of an array of odd length k is the k+12-th element when sorted.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains two integers n and k (1≤k≤n≤2⋅105, k is odd) — the length of the array and the length of the subsequence, respectively.

The second line of each test case contains n integers ai (0≤ai≤1) — the elements of the array.

It is guaranteed that sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, print the sum modulo 109+7.

Example
Input
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
Output
2
5
0
16
4
7
0
333606206
Note

In the first test case, there are four subsequences of [1,0,0,1] with length k=3:

  • [1,0,0]: median =0.
  • [1,0,1]: median =1.
  • [1,0,1]: median =1.
  • [0,0,1]: median =0.
The sum of the results is 0+1+1+0=2.

In the second test case, all subsequences of length 1 have median 1, so the answer is 5.