33OJ
登录 注册

#P17806. [ICPC 2019 Nanchang R] And and Pair

[ICPC 2019 Nanchang R] And and Pair

题目描述

给定一个极大的非负整数 nn,你需要统计满足以下条件的整数对 (i,j)(i,j) 的个数:

  • 0≤j≤i≤n0\leq j\leq i\leq n;
  • i & n=ii \ \& \ n = i;且
  • i & j=0i \ \& \ j = 0。

这里 &\& 表示按位与运算符。

为简单起见,nn 将以二进制表示的形式给出。同时,你只需要输出答案对 (109+7)(10^9+7) 取模的结果。

输入格式

第一行包含一个整数 TT (1≤T≤20)(1\le T\le 20),表示测试数据的组数。

接下来的 TT 行,每行包含一个字符串 SS (1≤∣S∣≤105)(1 \le |S| \le 10^5),它是非负整数 nn 的二进制表示。注意,输入中可能出现前导零。

输出格式

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

2
111
1010
14
15

提示

翻译由 DeepSeek V4 Pro 完成