喵哈哈村最近热衷于玩一个叫做狼人杀的游戏！
沈宝宝同学今天他抽到的是狼人的身份，按照他的一贯玩法，他喜欢一开始就自爆，让大家都不能说话，可谓心狠手辣。
于是他早早的就出去了。
但是他现在很无聊，于是他出了一道题给自己玩。
如果一个数的二进制表示中有k个1的话，那么这个就是就是k-th数。
比如有10(1010)就是2-th数,8(100)就是1-th数。
现在给你一个n和一个R，让你确认这些n-th数，输出满足要求的n-th数的和，这些数得满足在区间[0,R)内。
本题包含若干组测试数据。
每组测试数据包含两个整数，n,R.
满足 0<=n<=1000,0<R<=2^1000
注意 R 的读入是以2进制的方式读入的。
输出数的和，答案需要对10^9+7取模
7
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MX 1005s
#define MOD 1000000007
LL C[MX][MX], bit[MX];
int N;
char R[MX];
void init() {
int i, j;
bit[0] = 1LL;
for (i = 1; i < MX; i ++) {
bit[i] = 2 * bit[i - 1] % MOD;
}
C[0][0] = 1;
for (i = 1; i < MX; i ++) {
C[i][0] = C[i][i] = 1;
for (j = 1; j < i; j ++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
}
int main(){
init();
int Tcase, i, one;
while (scanf("%d %s", &N, R) == 2) {
int len = strlen(R);
int rlt = 0;
long long B = 0;
for (i = 0; i < len && N >= 0; i ++) {
if (R[i] == '1') {
if (N <= len - i - 1) {
if (N) rlt = (rlt + (long long) (bit[len - i - 1] - 1) * C[len - i - 2][N - 1] % MOD) % MOD;
rlt = (rlt + B * C[len - i - 1][N] % MOD) % MOD;
B += bit[len - i - 1];
B %= MOD;
N --;
}
}
}
if (rlt < 0) rlt += MOD;
printf("%d
", rlt);
}
}