#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
string str;
int n;
int ncr[1005][1005], dp[1005];
int calc[1005][1005][2];
int answer(int idx, int k, int lim) {
  if (idx == n) return (k == 0);
  if (calc[idx][k][lim] != -1) return calc[idx][k][lim];
  if (lim == 0) {
    return calc[idx][k][lim] = ncr[n - idx][k];
  }
  if (str[idx] == '0')
    return calc[idx][k][lim] = answer(idx + 1, k, lim);
  else
    return calc[idx][k][lim] =
               (answer(idx + 1, k, 0) + answer(idx + 1, k - 1, lim)) % mod;
}
void init() {
  int i, j;
  memset(calc, -1, sizeof calc);
  memset(ncr, 0, sizeof ncr);
  ncr[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    ncr[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      ncr[i][j] += ncr[i - 1][j];
      ncr[i][j] += ncr[i - 1][j - 1];
      ncr[i][j] %= mod;
    }
  }
  dp[1] = 0;
  for (int i = 2; i <= 1000; i++) {
    dp[i] = dp[__builtin_popcount(i)] + 1;
  }
}
int main() {
  init();
  int k;
  cin >> str >> k;
  n = str.length();
  if (str == "1") {
    if (k == 1) {
      cout << 0 << endl;
      return 0;
    } else if (k == 0) {
      cout << 1 << endl;
      return 0;
    } else {
      cout << 0 << endl;
      return 0;
    }
  }
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  int cnt = 0;
  for (int i = 0; i < n; i++)
    if (str[i] == '1') cnt++;
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    if (dp[i] == k - 1) ans = (ans + answer(0, i, 1)) % mod;
  }
  if (k == 1)
    cout << ans - 1 << endl;
  else
    cout << ans << endl;
  return 0;
}
