В отчаянной попытке получить своего waifu любимого персонажа, вы взломали исходный код игры. После дней борьбы вы наконец нашли двоичную строку, которая кодирует систему гача в игре. Чтобы раскодировать ее, вам сначала нужно решить следующую задачу.
Дана двоичная строка \(s\) длиной \(n\). Для каждой пары целых чисел \((l, r)\) \((1 \leq l \leq r \leq n)\) посчитайте количество пар \((x, y)\) \((l \leq x \leq y \leq r)\) таких, что количество \(\mathtt{0}\) равно количеству \(\mathtt{1}\) в подстроке \(s_xs_{x+1}...s_y\).
Выведите сумму подсчетов для всех возможных \((l, r)\) по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите целое число — ответ по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0000
01010101
1100111001
11000000111
|
0
130
147
70
|