#include <bits/stdc++.h>   using namespace std;   const int MAXN = 1010;   const int MOD = 1e9 + 7;   int dp[MAXN][MAXN][2];   int Steps[MAXN];   int add(int a, int b) { return ((a + b) >= MOD ? a + b - MOD : a + b); }   void PreproccessSteps() {     Steps[1] = 1;     for (int i = (2); i < (1010); i++)       Steps[i] = Steps[__builtin_popcount(i)] + 1;   }   int Ones(int N, string s) {     int cnt = 0;     for (int i = (1); i < (N); i++)       if (s[i] ==  1 ) cnt++;     return cnt;   }   void FillDP(int N, string s) {     for (int j = (0); j < (N + 1); j++) dp[0][j][0] = dp[0][j][1] = 1;     for (int i = (1); i < (N + 1); i++)       for (int j = (1); j < (N + 1); j++) {         if (s[j - 1] ==  1 )           dp[i][j][0] = add(dp[i - 1][j - 1][0], dp[i][j - 1][1]);         if (s[j - 1] ==  0 ) dp[i][j][0] = dp[i][j - 1][0];         dp[i][j][1] = add(dp[i - 1][j - 1][1], dp[i][j - 1][1]);       }   }   int main() {     int N, k, sum = 0;     string s;     cin >> s >> k;     reverse(s.begin(), s.end());     PreproccessSteps();     N = (int)s.size();     FillDP(N, s);     for (int i = (1); i < (N + 1); i++)       if (Steps[i] == k) sum = add(sum, dp[i][N][0]);     if (k == 1) {       cout << dp[1][N][0] - 1;       return 0;     }     if (!k) sum++;     cout << sum;     return 0;   }   