#include <bits/stdc++.h>   using namespace std;   const int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};   const int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};   long long dp[1005][1005][2];   string s;   int k;   int ar[1026];   long long Dance_of_Death(int x, int rem, int f) {     if (x == s.size()) {       if (ar[rem] + 1 == k) {         return 1;       } else {         return 0;       }     }     if (dp[x][rem][f] != -1) {       return dp[x][rem][f];     }     long long y = 0;     if (!f && s[x] ==  0 ) {       y = Dance_of_Death(x + 1, rem, 0) % 1000000007;     }     if (f) {       y = Dance_of_Death(x + 1, rem, f) % 1000000007;       y = (y + Dance_of_Death(x + 1, rem + 1, f)) % 1000000007;     }     if (f == 0 && s[x] ==  1 ) {       y = Dance_of_Death(x + 1, rem, 1) % 1000000007;       y = (y + Dance_of_Death(x + 1, rem + 1, f)) % 1000000007;     }     return dp[x][rem][f] = y;   }   void build() {     ar[1] = 0;     for (int i = 2; i < 1026; i++) {       int x = i;       int c = 0;       while (x) {         if (x % 2) {           c++;         }         x /= 2;       }       ar[i] = ar[c] + 1;     }     ar[0] = 10000;   }   int main() {     build();     cin >> s;     cin >> k;     memset(dp, -1, sizeof(dp));     if (k == 0) {       cout << 1 << endl;       return 0;     }     int f = 0;     if (k == 1) {       f = 1;     }     cout << Dance_of_Death(0, 0, 0) - f << endl;   }   