#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;
}
