#include <bits/stdc++.h>
const long long mod = 1e9 + 7;
using namespace std;
long long c[1001][1001];
unordered_map<int, int> red, cc;
string in;
void precalc() {
  c[0][0] = 1;
  c[1001 - 1][1001 - 1] = 1;
  for (int n = 1; n < 1001; n++) {
    c[n][0] = 1;
    for (int k = 1; k <= n; k++)
      c[n][k] = (c[n - 1][k - 1] + c[n - 1][k]) % mod;
  }
}
int count_tr(int n) {
  if (n == 1)
    cc[n] == 0;
  else if (cc[n] == 0)
    cc[n] = 1 + count_tr(__builtin_popcount(n));
  return cc[n];
}
long long cnt(int st, int n) {
  int len = in.length();
  if (n == 0) return 1;
  if (st >= len || len - st < n) return 0;
  len = len - st;
  st++;
  while (st < in.length() && in[st] == '0') st++;
  return (c[len - 1][n] + cnt(st, n - 1)) % mod;
}
int main() {
  precalc();
  int k;
  cin >> in >> k;
  vector<int> v;
  if (k > 5) {
    cout << 0 << endl;
    return 0;
  }
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  if (in == "1") {
    cout << (k == 0);
    return 0;
  }
  for (int i = 1; i <= (1000); i++) {
    if (count_tr(i) == k - 1) v.push_back(i);
  }
  long long ans = 0;
  for (auto i : v) {
    if (i == 1) {
      ans += in.length() - 1;
      continue;
    }
    ans += cnt(0, i);
    ans %= mod;
  }
  cout << ans << endl;
}
