F. Ожидаемая медиана
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Арул имеет бинарный массив$$$^{\text{∗}}$$$ $$$a$$$ длины $$$n$$$.

Он возьмет все подпоследовательности$$$^{\text{†}}$$$ длины $$$k$$$ ($$$k$$$ — нечетное) этого массива и найдет их медиану.$$$^{\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$$$.