问题 CQ: And and Pair
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
xsy在一个神奇的星球发现一个金矿n，同时这个星球有一种神奇的铁锹（数值为i），每一次能挖i&n个，贪婪的xsy不管多长时间能挖完，他只在乎眼前利益，他只想每次都把铁锹装满 即（i&n=i），同时他要有一个与铁锹互补的机械臂j（i&j=0），以此支撑残疾的他来搬运黄金，现在xsy想计算出他有多少种铁锹与机械臂的组合来支持他来挖取黄金，你能帮帮他吗？
输入
第一行包含测试样例总数T
接下来T行每行一个字符串（长度<=1e5）
来表示一个非常大的整数n（用二进制表示）.
输出
输出符合条件的i，j整数对数目（0<=j<=i<=n）
答案对1e9+7取模
样例输入 复制
2
111
1010样例输出 复制
14
15