#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long pasc[1010][1010];
long long tik(long long v) {
  long long ans = 0;
  while (v != 0) {
    ans += (v % 2);
    v /= 2;
  }
  return ans;
}
int main() {
  string s;
  long long k, p = 0;
  cin >> s >> k;
  if (k == 0) {
    cout << 1;
    return 0;
  }
  for (int i = 0; i < s.size(); ++i) p += (s[i] == '1');
  pasc[0][0] = 1;
  for (int i = 0; i <= 1001; ++i) {
    pasc[i][0] = pasc[i][i] = 1;
  }
  for (int i = 1; i <= 1001; ++i) {
    for (int j = 1; j < i; ++j) {
      pasc[i][j] = pasc[i - 1][j] + pasc[i - 1][j - 1];
      pasc[i][j] %= MOD;
    }
  }
  vector<long long> magic(1010);
  magic[p] += 1;
  for (long long i = 1; i <= s.size(); ++i) {
    long long c = 0;
    for (int j = 0; j < s.size(); ++j) {
      if (s[j] == '1') {
        if (i - c < 0) continue;
        magic[i] += pasc[s.size() - 1 - j][i - c];
        magic[i] %= MOD;
        ++c;
      }
    }
  }
  magic[1] -= 1;
  long long answer = 0;
  for (long long i = 1; i <= 1000; ++i) {
    long long ctu = 0, ctp = i;
    while (ctp != 1) {
      ctp = tik(ctp);
      ++ctu;
    }
    if (ctu == k - 1) {
      answer += magic[i];
      answer %= MOD;
    }
  }
  cout << answer;
  return 0;
}
