Арул имеет бинарный массив\(^{\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\).
В первом наборе входных данных есть четыре подпоследовательности массива \([1,0,0,1]\) длины \(k=3\):
Во втором наборе входных данных все подпоследовательности длины \(1\) имеют медиану \(1\), поэтому ответ равен \(5\).
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
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач