P17806 [ICPC 2019 Nanchang R] And and Pair

给定一个极大的非负整数 $n$，你需要统计满足以下条件的整数对 $(i,j)$ 的个数： - $0\leq j\leq i\leq n$； - $i \ \& \ n = i$；且 - $i \ \& \ j = 0$。 这里 $\&$ 表示按位与运算符。 为简单起见，$n$ 将以二进制表示的形式给出。同时，你只需要输出答案对 $(10^9+7)$ 取模的结果。

第一行包含一个整数 $T$ $(1\le T\le 20)$，表示测试数据的组数。 接下来的 $T$ 行，每行包含一个字符串 $S$ $(1 \le |S| \le 10^5)$，它是非负整数 $n$ 的二进制表示。注意，输入中可能出现前导零。

对于每组测试数据，输出一行包含上述答案对 $(10^9+7)$ 取模的结果。

翻译由 DeepSeek V4 Pro 完成