Арул имеет бинарный массив\(^{\text{∗}}\) \(a\) длины \(n\).
Он возьмет все подпоследовательности\(^{\text{†}}\) длины \(k\) (\(k\) — нечетное) этого массива и найдет их медиану.\(^{\text{‡}}\)
Какова сумма всех этих значений?
Поскольку эта сумма может быть очень большой, выведите ее по модулю \(10^9 + 7\). Другими словами, напечатайте остаток этой суммы при делении на \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите сумму по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных есть четыре подпоследовательности массива \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|