Арул имеет бинарный массив∗ a длины n.
Он возьмет все подпоследовательности† длины k (k — нечетное) этого массива и найдет их медиану.‡
Какова сумма всех этих значений?
Поскольку эта сумма может быть очень большой, выведите ее по модулю 109+7. Другими словами, напечатайте остаток этой суммы при делении на 109+7.
∗Бинарный массив — это массив, состоящий только из нулей и единиц.
†Массив b является подпоследовательностью массива a, если b может быть получен из a путем удаления нескольких (возможно, нуля или всех) элементов. Элементы подпоследовательности не обязаны быть соседними.
‡Медиана массива нечётной длины k — это k+12-й элемент в отсортированном виде.
Первая строка содержит одно целое число t (1≤t≤104) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа n и k (1≤k≤n≤2⋅105, k нечетное) — длина массива и длина подпоследовательности соответственно.
Вторая строка каждого набора входных данных содержит n целых чисел ai (0≤ai≤1) — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2⋅105.
Для каждого набора входных данных выведите сумму по модулю 109+7.
84 31 0 0 15 11 1 1 1 15 50 1 0 1 06 31 0 1 0 1 14 31 0 1 15 31 0 1 1 02 10 034 171 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 имеют медиану 1, поэтому ответ равен 5.
| Codeforces Round 964 (Div. 4) |
|---|
| Закончено |
