#include <bits/stdc++.h>
using namespace std;
long long a[10001000], b[2000010], d[2000010], e[2000010], x = 0, y = 0, z = 0,
                                                           c[2002010];
double an[2000], S, D;
long long modulo(long long a, long long b, long long n) {
  long long x = 1, y = a;
  while (b > 0) {
    if (b % 2 == 1) {
      x = (x * y) % n;
    }
    y = (y * y) % n;
    b /= 2;
  }
  return x % n;
}
vector<long long> g[100001];
struct node {
  mutable long long v, i, n;
  node() {}
  node(long long x, long long y, long long z = 0) {
    v = x;
    i = y;
    n = z;
  }
  bool operator<(const node& y) const {
    if (v == y.v)
      if (i != y.i)
        return i < y.i;
      else
        return n < y.n;
    else
      return v < y.v;
  }
};
ostream& operator<<(ostream& o, node x) {
  o << '(' << x.i << ',' << x.v;
  if (x.n != 0) o << ',' << x.n;
  o << ")\t";
}
bool cmp(node x, node y) {
  if (x.i != y.i)
    return x.i < y.i;
  else if (x.v != y.v)
    return x.v > y.v;
  else
    return x.n < y.n;
}
long long vis[100001] = {-1};
long long dfs(long long i) {
  if (vis[i] >= 0) return vis[i];
  vis[i] = 0;
  cout << i << endl;
  for (long long j = 0; j < g[i].size(); j++) {
    cout << g[i][j] << ' ';
    if (a[g[i][j]] == 0 && a[i] == 1)
      vis[i] = max(vis[i], dfs(g[i][j]));
    else
      vis[i] = max(vis[i], dfs(g[i][j]) + 1);
  }
  cout << endl << ' ' << vis[i] << endl;
}
void factorial() {
  b[0] = 1;
  long long i;
  for (i = 1; i <= 1000005; i++) b[i] = b[i - 1] * i % 1000000007;
  c[1000005] = modulo(b[1000005], 1000000007 - 2, 1000000007);
  for (i = 1000004; i > -1; i--) c[i] = c[i + 1] * (i + 1) % 1000000007;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long t, j, r, q, aa, u, s1, s2, s3, v, bb, l, h, k, w, c1, v1, v2, z, c2,
      n1, nn, x1, hx, hy, tx, ty, n2, s, maxi, m, i, n, L, R, p, m1, N;
  string st[100001], ans, st1, st2;
  char str[1000001], ch1[1000100], ch, ch2, ch3, *si;
  t = 1;
  factorial();
  while (t--) {
    cin >> st1;
    cin >> k;
    if (k > 5) {
      cout << 0;
      return 0;
    }
    if (k == 0) {
      cout << 1;
      return 0;
    }
    if (k == 1) {
      cout << st1.length() - 1;
      return 0;
    }
    a[1] = 0;
    m = 0;
    for (i = 2; i < 1024; i++) {
      s = 0;
      for (j = 0; j < 12; j++)
        if (i & (1 << j)) s++;
      a[i] = a[s] + 1;
    }
    s = 0;
    vector<int> bit;
    for (i = 1; i < 1001; i++)
      if (a[i] == k - 1) bit.push_back(i);
    x = 0;
    for (i = 0; i < st1.length(); i++) {
      if (st1[i] == '1') {
        l = st1.length() - i - 1;
        for (j = 0; j < bit.size() && (bit[j] - x) <= l; j++)
          s = (s + b[l] * c[bit[j] - x] % 1000000007 * c[l - bit[j] + x] %
                       1000000007) %
              1000000007;
        x++;
      }
    }
    if (find(bit.begin(), bit.end(), x) != bit.end()) s++;
    cout << s << endl;
  }
}
