#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
void add(int& x, int y) { ((x += y) >= MOD) && (x -= MOD); }
int mul(int x, int y) { return x * 1ll * y % MOD; }
vector<int> n;
int k;
bool read() {
  string s;
  if (!getline(cin, s)) {
    return 0;
  }
  scanf("%d\n", &k);
  n.resize(((int)(s).size()));
  for (int i = 0; i < int(((int)(s).size())); ++i) {
    n[i] = s[i] - '0';
  }
  return 1;
}
const int MAXN = 1e3 + 10;
int to_1[MAXN];
int pop1(int i) {
  int ans = 0;
  while (i) {
    ans += i & 1;
    i /= 2;
  }
  return ans;
}
void precalc() {
  to_1[0] = -1;
  to_1[1] = 0;
  for (int i = 2; i < MAXN; ++i) {
    int cnt = pop1(i);
    to_1[i] = to_1[cnt] + 1;
  }
}
int dp[2][MAXN][MAXN];
int solve() {
  if (k == 0) {
    return 1;
  }
  memset(dp, 0, sizeof dp);
  dp[0][0][0] = 1;
  for (int i = 0; i < int(((int)(n).size())); ++i) {
    for (int ls = 0; ls < int(2); ++ls) {
      for (int cnt = 0; cnt < int(i + 1); ++cnt) {
        const int cur_dp = dp[ls][i][cnt];
        if (!cur_dp) {
          continue;
        }
        for (int cur = 0; cur < int(2); ++cur) {
          if (!ls && cur > n[i]) {
            continue;
          }
          const int nls = ls | (cur < n[i]);
          const int ncnt = cnt + cur;
          add(dp[nls][i + 1][ncnt], cur_dp);
        }
      }
    }
  }
  int ans = 0;
  for (int cnt = 0; cnt < int(((int)(n).size()) + 1); ++cnt) {
    int cur = 0;
    for (int ls = 0; ls < int(2); ++ls) {
      add(cur, dp[ls][((int)(n).size())][cnt]);
    }
    int moves = to_1[cnt] + 1;
    if (cnt == 1) {
      add(cur, -1 + MOD);
    }
    if (moves == k) {
      add(ans, cur);
    }
  }
  return ans;
}
int main() {
  precalc();
  while (read()) {
    printf("%d\n", solve());
  }
  return 0;
}
