#include <bits/stdc++.h>
using namespace std;
const long long N = 1e9 + 7;
long long C[1005][1005] = {0};
long long cnt[1005] = {0};
long long trs[1005] = {0};
long long k, l, sum = 0;
string s;
long long trans(long long x) {
  long long cnt = 0;
  while (x) {
    if (x & 1) cnt++;
    x >>= 1;
  }
  return cnt;
}
void init() {
  C[0][0] = 1;
  for (long long i = 1; i <= 1001; i++) {
    C[i][0] = 1;
    C[i][i] = 1;
  }
  for (long long i = 2; i <= 1001; i++) {
    for (long long j = 1; j < i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % N;
    }
  }
  trs[0] = -1;
  trs[1] = 0;
  for (long long i = 2; i <= 1001; i++) {
    trs[i] = trs[trans(i)] + 1;
  }
}
int main() {
  long long ocn = 0;
  init();
  cin >> s;
  cin >> k;
  if (!k) {
    cout << 1 << endl;
    return 0;
  }
  l = s.length();
  for (long long i = 0; i < l; i++) {
    if (s[i] == '1') {
      for (long long j = 0; j < l; j++) {
        if (i + j >= l) break;
        cnt[ocn + j] += C[l - i - 1][j];
        cnt[ocn + j] %= N;
      }
      ocn++;
    }
  }
  for (long long i = 0; i <= 1001; i++) {
    if (trs[i] == k - 1) {
      sum += cnt[i];
      sum %= N;
    }
  }
  if (k == 1) sum--;
  if (trs[ocn] == k - 1) sum++;
  sum = (sum + N) % N;
  cout << sum << endl;
  return 0;
}
