#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int K = 1024;
string nbit;
int k;
int dist_to_one[K];
int fact[K], inv[K];
int power(int a, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) {
      ret = 1LL * ret * a % MOD;
    }
    a = 1LL * a * a % MOD;
    n >>= 1;
  }
  return ret;
}
int C(int n, int k) {
  return (k < 0 || k > n) ? 0 : 1LL * fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int main() {
  cin >> nbit;
  cin >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  fact[0] = fact[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i < K; i++) {
    dist_to_one[i] = 1 + dist_to_one[__builtin_popcount(i)];
    fact[i] = 1LL * fact[i - 1] * i % MOD;
    inv[i] = power(fact[i], MOD - 2);
  }
  int ans = 0;
  for (int i = 1; i < K; i++) {
    if (dist_to_one[i] + 1 != k) {
      continue;
    }
    if (i == 1) {
      ans--;
    }
    for (int j = 0, set_bit = 0; j < (int)nbit.length(); j++) {
      if (nbit[j] == '0') {
        continue;
      }
      ans += C((int)nbit.length() - j - 1, i - set_bit);
      ans %= MOD;
      set_bit++;
    }
  }
  int set_bit = 0;
  for (int i = 0; i < (int)nbit.length(); i++) {
    if (nbit[i] == '1') {
      set_bit++;
    }
  }
  if (dist_to_one[set_bit] + 1 == k) {
    ans++;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}
