#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
long long fac[maxn], f[maxn], inv[maxn];
void init() {
  fac[0] = fac[1] = f[0] = f[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i < maxn; i++) {
    fac[i] = fac[i - 1] * i % mod;
    long long t = mod / i, k = mod % i;
    f[i] = (mod - t) * f[k] % mod;
    inv[i] = inv[i - 1] * f[i] % mod;
  }
}
long long C(long long n, long long m) {
  if (n < m) return 0;
  return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int dp[MAXN], k;
string n;
int get(int x) {
  int num = 0;
  while (x) {
    if (x & 1) num++;
    x >>= 1;
  }
  return num;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  dp[1] = 0;
  for (long long i = 2; i <= 1000; i++) {
    dp[i] = dp[get(i)] + 1;
  }
  cin >> n >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  long long ans = 0;
  if (k == 1) ans--;
  int len = n.size();
  int numm = 0;
  for (long long i = 0; i <= len - 1; i++) {
    if (n[i] - '0' == 1) numm++;
  }
  for (long long i = 1; i <= 1000; i++) {
    if (dp[i] == k - 1) {
      int p = 0;
      for (long long j = 0; j <= len - 1; j++) {
        if (i - p < 0) break;
        if (n[j] - '0' == 1) {
          ans = (ans + C(len - j - 1, i - p)) % mod;
          p++;
        }
      }
      if (p == i) ans = (ans + 1) % mod;
    }
  }
  printf("%I64d\n", ans);
  return 0;
}
