#include <bits/stdc++.h>

using namespace std;
map<int,int> repArr;
int arrN[10005];
string s;
int onBits(int x)
{
    int newF = 0;
        for(int i = 0;i <= 31;i++)
            if(x & (1 << i))
                newF++;
    return newF;
}
int countOp(int x)
{
    int op = 0;
    while(x != 1)
    {
        int newF = 0;
        for(int i = 0;i <= 31;i++)
            if(x & (1 << i))
                newF++;
        x = newF;
        op++;
    }
    return op;
}
int k;
long long dp[2005][2005][2];
long long solve(int idx,int ones,bool setAny)
{
    if(idx == s.length())
        return arrN[ones] == k;

    if(dp[idx][ones][setAny] != -1)
        return dp[idx][ones][setAny];
    long long C1 = 0;
    if(s[idx] == '1')
        C1 = ((solve(idx + 1,ones + 1,setAny) % 1000000007) + (solve(idx + 1,ones,true) % 1000000007)) % 1000000007;
    else if(s[idx] == '0')
    {
        if(setAny)
            C1 += solve(idx + 1,ones + 1,setAny) % 1000000007;
        C1 += solve(idx + 1,ones,setAny) % 1000000007;
    }
    return dp[idx][ones][setAny] = C1 % 1000000007;
}
int main()
{
    memset(dp,-1,sizeof dp);
    for(int i = 1;i <= 10000;i++)
        arrN[i] = countOp(i)+1;

    cin >> s >> k;
    cout << solve(0,0,false) % 1000000007;
}