В отчаянной попытке получить своего 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\).
В первой строке содержится \(t\) (\(1 \leq t \leq 1000\)) — количество наборов входных данных.
Каждый набор входных данных содержит двоичную строку \(s\) (\(1 \leq |s| \leq 2 \cdot 10^5\)). Гарантируется, что \(s\) содержит только символы \(\mathtt{0}\) и \(\mathtt{1}\).
Гарантируется, что сумма \(|s|\) по всем наборам входных данных не превышает \(2 \cdot 10^5\).
Для каждого набора входных данных выведите целое число — ответ по модулю \(10^9+7\).
4 0000 01010101 1100111001 11000000111
0 130 147 70
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач