E. Декодирование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В отчаянной попытке получить своего 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