题目链接：C. And and Pair

可以找规律，当然也可以数位dp。

只不过这个数位dp是二维的数位dp。

我们对于每一个数字：如果当前某一位二进制为1，但是n这一位不为1，那么不合法，continue。

如果当前这一位 i，j都为1，也不合法，continue。

然后我们没有处理 i == j 和 j<= i 的关系的情况，i == j 并且合法，那么都为。我们利用对称性除以二就可以避免 j>i 然后加上 1就行了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,p=1e9+7;
int T,dp[N][2][2],n; char str[N];
inline int qmi(int a,int b=p-2){
	int res=1;
	while(b){if(b&1) res=res*a%p; b>>=1; a=a*a%p;}
	return res;
}
int dfs(int pos,int l1,int l2){
	if(!pos)	return 1;
	if(dp[pos][l1][l2]!=-1)	return dp[pos][l1][l2];
	int up1=l1?str[pos]-'0':1,up2=l2?str[pos]-'0':1,res=0;
	for(int i=0;i<=up1;i++){
		for(int j=0;j<=up2;j++){
			if((i&&(str[pos]=='0'))||(i==1&&j==1))	continue;
			res=(res+dfs(pos-1,l1&&i==up1,l2&&j==up2))%p;
		}
	}
	dp[pos][l1][l2]=res;
	return res;
}
inline int solve(){
	n=strlen(str+1);	reverse(str+1,str+1+n);
	return dfs(n,1,1);
}
signed main(){
	cin>>T; int inv=qmi(2);
	while(T--){
		scanf("%s",str+1);	memset(dp,-1,sizeof dp);
		printf("%lld\n",(solve()+1)*inv%p);
	}
	return 0;
}