#include <bits/stdc++.h>
using namespace std;
const long long md = 1e9 + 7;
char str[10000];
long long int k, s, c, d, fct[10000], mrk[10000], l, ans;
long long int ex(long long int y) {
  long long int f = md - 2, p = 1;
  while (f) {
    if (f & 1) p = (p * y) % md;
    y = (y * y) % md;
    f >>= 1;
  }
  return p;
}
int main() {
  long long int i, j;
  cin >> str;
  cin >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  if ((long long int)(strlen(str)) == 1) {
    cout << 0 << endl;
    return 0;
  }
  if (k == 1) {
    cout << (long long int)(strlen(str)) - 1 << endl;
    return 0;
  }
  for (i = 1; i <= 1000; i++) {
    s = i;
    c = 0;
    d = 0;
    while (c != 1) {
      d++;
      c = 0;
      while (s > 0) {
        if (s & 1) c++;
        s = s / 2;
      }
      s = c;
    }
    if (d == k - 1) mrk[i] = 1;
    if (i == 1 && k != 0) mrk[i] = 0;
  }
  for (i = 0; i <= 1000; i++) {
    if (i == 0 || i == 1)
      fct[i] = 1;
    else {
      fct[i] = (i * fct[i - 1]) % md;
    }
  }
  l = strlen(str);
  c = 0;
  for (i = l - 1; i >= 0; i--) {
    if (str[l - i - 1] == '1') {
      for (j = 0; j <= i; j++) {
        if (mrk[j + c])
          ans =
              (ans + (fct[i] * ex((fct[j] * fct[i - j]) % md) % md) % md) % md;
      }
      c++;
    }
  }
  if (mrk[c]) ans = (ans + 1) % md;
  cout << ans << endl;
  return 0;
}
