#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
inline int mul(int a, int b) {
  long long ret = 1LL * a * b;
  if (ret >= mod) ret %= mod;
  return ret;
}
const int N = 1000 + 5;
int steps[N], memo[2][N][N], k;
string n;
int solve(bool less, int bit, int cnt) {
  if (bit == n.size()) return (steps[cnt] + 1 == k);
  int &ret = memo[less][bit][cnt];
  if (~ret) return ret;
  ret = solve(less || (n[bit] == '1'), bit + 1, cnt);
  if (less || n[bit] == '1') ret = add(ret, solve(less, bit + 1, cnt + 1));
  return ret;
}
int main() {
  steps[1] = 0;
  for (int i = 2; i < N; i++) {
    steps[i] = 1 + steps[__builtin_popcount(i)];
  }
  memset(memo, -1, sizeof memo);
  cin >> n >> k;
  if (k == 0)
    cout << 1;
  else if (k == 1) {
    cout << n.size() - 1;
  } else
    cout << solve(0, 0, 0);
}
