#include <bits/stdc++.h>
using namespace std;
vector<string> split(const string& s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
void err(vector<string>::iterator it) {}
template <typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
  cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\t';
  err(++it, args...);
}
const int NN = 2004;
long long int mod = (long long int)1e9 + 7;
int steps[NN];
int call(int x) {
  int c = 0;
  while (x > 0) {
    c++;
    x = x & (x - 1);
  }
  return steps[c] + 1;
}
long long int C[NN][NN];
void pre() {
  for (int i = 0; i <= 1002; i++) {
    for (int j = 0; j <= i; j++) {
      if (i == j || j == 0)
        C[i][j] = 1;
      else
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
}
long long int ncr(int x, int y) {
  if (x < y || x < 0 || y < 0) return 0;
  return C[x][y];
}
int main() {
  int n, i, h, j, k, m, prr;
  string s;
  cin >> s >> k;
  if (k == 0) {
    cout << 1;
    return 0;
  } else if (k == 1) {
    cout << (s.size() - 1);
    return 0;
  }
  pre();
  steps[1] = 0;
  steps[2] = 1;
  steps[3] = steps[5] = steps[6] = 2;
  steps[7] = 3;
  steps[4] = 1;
  for (i = 8; i < NN; i++) {
    steps[i] = call(i);
  }
  vector<int> vv;
  for (i = 1; i < NN; i++) {
    if (steps[i] == k - 1) {
      vv.push_back(i);
    }
  }
  m = s.size();
  long long int ans;
  ans = 0;
  int sav = k;
  for (auto b : vv) {
    if (b > m) continue;
    j = b;
    for (i = 0; i < m; i++) {
      if (s[i] == '1') {
        k = m - i - 1;
        ans = (ans + ncr(k, j)) % mod;
        j--;
      }
    }
    if (j == 0) ans = (ans + 1) % mod;
  }
  cout << ans << endl;
  return 0;
}
