← 返回题目列表

Codeforces · 1996/E

E. 解码

中文机器翻译题面 查看原题

为了获得你最喜欢的角色,你已经黑进了游戏的源代码。经过几天的努力,你终于找到了编码游戏扭蛋系统的二进制字符串。为了解码它,您必须首先解决以下问题。

给你一个长度为$$$n$$$的二进制字符串$$$s$$$。对于每对整数 $$$(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$$$ 为模。

示例

输入 #1

4
0000
01010101
1100111001
11000000111

输出 #1

0
130
147
70