对于一个正整数x，我们定义一次操作是将其变为它二进制下“1”的个数,比如我们知道13(10)=1101(2),而1101有三个"1",所以对13进行一次操作就会将其变为3。显而易见的是，对于一个正整数，我们在进行若干次操作后，一定会将其变为1。

给定n和k，其中n是在二进制下被给出，求出所有不大于n且将其变为1的最小操作次数为k的数的个数对10^9+7取模的结果。

因为strlen(str) <= 1000, 使用在预处理1-1000中变化到1时要多少步,中枚举1-1000,然后使用组合数学（）

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>

using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1005;
char str[maxn];
int dp[maxn], m;

int getbit(int x) {
    int ans = 0;
    while (x) {ans += x % 2; x /= 2;}
    return ans;
}
int C[maxn][maxn];
void init() {
    for(int i = 0; i <= 1000; ++i)
        C[i][0] = 1;
    for(int i = 1; i <= 1000; ++i) {
        for(int j = 1; j <= 1000; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
}

/*
 *
 */
int main() {
//    freopen("in.in", "r", stdin);
    init();
    cin >> str + 1;
    strrev(str + 1);
    int n = strlen(str + 1);
    cin >> m;
    int ans = 0;
    if (m == 0) {cout << "1" << endl; return 0;}
    for(int i = 2; i <= 1000; i++) dp[i] = dp[getbit(i)] + 1;
    for (int i = 1; i <= 1000; i++) {
        if (dp[i] != m - 1) continue;
        int cnt = 0;
        for (int j = n, k = i; j >= 1; j--) {
            if (str[j] == '0') continue;
            if (k == 1) { //这个地方要特别注意一下，因为就剩下最后一个1，所以1-j个位子都可以放1
                ans = (ans + C[j][1]) % mod; break;
            }
            if (j - 1 >= k ) ans = (ans + C[j - 1][k]) % mod; k--;
        }
    }
    if (m == 1) {
        ans = (ans - 1 + mod) % mod;
    }
    cout << ans << endl;
    return 0;
}