为了获得你最喜欢的角色,你已经黑进了游戏的源代码。经过几天的努力,你终于找到了编码游戏扭蛋系统的二进制字符串。为了解码它,您必须首先解决以下问题。
给你一个长度为$$$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