#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int N = 1e3 + 3;
const long long mod = 1e9 + 7;
int op[N], k;
long long dp[N][N][2];
string n;
long long go(int ct, int at, bool menor) {
  if (at == (int)n.size()) {
    return op[ct] == k - 1;
  }
  long long &r = dp[ct][at][menor];
  if (r != -1) return r;
  r = 0;
  if (n[at] == '1')
    r += go(ct, at + 1, true);
  else
    r += go(ct, at + 1, menor);
  if (menor)
    r += go(ct + 1, at + 1, menor);
  else if (n[at] == '1')
    r += go(ct + 1, at + 1, menor);
  r %= mod;
  return r;
}
int main(void) {
  ios_base::sync_with_stdio(false);
  memset(op, -1, sizeof op);
  op[0] = INF;
  op[1] = 0;
  for (int i = 2; i < N; i++) op[i] = op[__builtin_popcount(i)] + 1;
  cin >> n >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  int ct = 0;
  for (auto c : n) ct += c - '0';
  memset(dp, -1, sizeof dp);
  long long res = go(0, 0, 0);
  if (k == 1) res--;
  if (res < 0) res += mod;
  cout << res << endl;
  return 0;
}
