#include <bits/stdc++.h>
using namespace std;
long long mod = 1000 * 1000 * 1000 + 7;
long long ncr[1004][1004];
long long binomial(long long n, long long k) { return ncr[n][k]; }
int main() {
  for (int i = 0; i < 1001; i++) {
    ncr[i][0] = 1;
  }
  for (int i = 1; i < 1001; i++) {
    for (int j = 1; j < 1001; j++) {
      ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % mod;
    }
  }
  int precalc[] = {
      0, 0, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 2, 1, 2, 2, 3, 2, 3, 3, 2, 2,
      3, 3, 2, 3, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 3,
      3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3,
      2, 3, 2, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 2,
      3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3,
      3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 3, 2,
      2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3,
      3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 2, 3, 2, 2, 3,
      3, 2, 2, 3, 2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 3,
      2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3,
      3, 4, 3, 4, 4, 2, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3,
      2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3,
      2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 2, 3,
      2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3,
      3, 4, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3,
      4, 3, 3, 3, 4, 3, 4, 4, 2, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3,
      3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 3, 2,
      3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 2, 3, 2,
      2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3,
      4, 3, 4, 4, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 4,
      3, 4, 4, 2, 3, 4, 4, 2, 4, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3,
      2, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 2,
      2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3,
      4, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3,
      2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2,
      3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 2, 2, 3, 3, 2, 3, 2, 2, 3, 3, 2,
      2, 3, 2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2,
      3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4,
      3, 4, 4, 2, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3,
      3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4,
      4, 2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 4, 4, 2, 4, 2, 2, 3, 2, 3, 3, 2, 3, 2, 2,
      3, 3, 2, 2, 3, 2, 3, 3, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4,
      3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3,
      3, 3, 4, 3, 4, 4, 2, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3,
      3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3,
      4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 4, 4, 2, 4, 2, 2, 3, 3, 2, 2, 3,
      2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3,
      4, 4, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4,
      4, 2, 3, 4, 4, 2, 4, 2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4,
      2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 4, 4, 2, 4, 2, 2, 3, 3, 3, 3, 4, 3, 4, 4, 2,
      3};
  long long k;
  string n;
  cin >> n >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  if (k == 1) {
    cout << n.size() - 1 << endl;
    return 0;
  }
  long long ans = 0;
  for (int i = 1; i < 1001; i++) {
    if (precalc[i] == k - 1) {
      auto ones_count = 0;
      for (unsigned int j = 0; j < n.size(); j++) {
        if (n[j] == '1' and ones_count <= i) {
          ans = (ans + binomial(n.size() - j - 1, i - ones_count)) % mod;
          ones_count++;
        }
      }
    }
  }
  if (precalc[count(n.begin(), n.end(), '1')] + 1 == k) {
    ++ans;
  }
  cout << ans % mod << endl;
  return 0;
}
