#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
string s;
int k;
int memo[1024][1024];
int numeros(int digitos, int unos) {
  if (digitos == 0) return unos == 0;
  if (memo[digitos][unos] != -1) return memo[digitos][unos];
  int res = 0;
  res += numeros(digitos - 1, unos);
  res += numeros(digitos - 1, unos - 1);
  res %= MOD;
  memo[digitos][unos] = res;
  return res;
}
int memoS[1024][1024];
int lessThanS(int from, int unos) {
  if (unos == 0) return 1;
  if (from == (int)s.size()) return 0;
  if (memoS[from][unos] != -1) return memoS[from][unos];
  int res = 0;
  res += lessThanS(from + 1, unos - (s[from] == '1'));
  if (s[from] == '1') {
    res += numeros(s.size() - from - 1, unos);
  }
  if (unos == 1 && from == 0) res--;
  res %= MOD;
  memoS[from][unos] = res;
  return res;
}
int amountTo1[1024];
int main() {
  memset(memo, -1, sizeof(memo));
  memset(memoS, -1, sizeof(memoS));
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> s;
  cin >> k;
  amountTo1[1] = 0;
  for (int i = (2); i < (int)(1024); i++) {
    amountTo1[i] = amountTo1[__builtin_popcount(i)] + 1;
  }
  if (k > 5)
    cout << 0 << endl;
  else if (k == 0)
    cout << 1 << endl;
  else {
    int res = 0;
    for (int i = (1); i < (int)(1024); i++) {
      if (amountTo1[i] == k - 1) {
        res += lessThanS(0, i);
        res %= MOD;
      }
    }
    cout << res << endl;
  }
}
