#include <bits/stdc++.h>
using namespace std;
long long com[1015][1015];
long long mo = 1000000007;
long long rec(long long n, long long r) {
  if (com[n][r] != -1) return com[n][r];
  if (r == 0) {
    return com[n][r] = 1;
  }
  if (n == r) return com[n][r] = 1;
  com[n][r] = (rec(n - 1, r - 1) + rec(n - 1, r)) % mo;
  return com[n][r];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long pre[1015][1015], k;
  memset(pre, 0, sizeof(pre));
  memset(com, -1, sizeof(com));
  string s;
  cin >> s >> k;
  long long l = s.size();
  long long one = 0;
  for (long long i = 0; i < l; i++) {
    if (s[i] == '1') one++;
  }
  if (k == 0) {
    if (one == 0) {
      cout << 0;
    } else {
      cout << 1;
    }
    return 0;
  }
  long long no_bit[1015], r;
  for (long long i = 0; i < 1015; i++) {
    r = 0;
    for (long long j = 0; j < 10; j++) {
      if (i & (1LL << j)) r++;
    }
    no_bit[i] = r;
  }
  long long qqq = one;
  if (qqq > 0) pre[1][1]--;
  pre[1][one] += 1;
  long long z;
  for (long long i = l - 1; i >= 0; i--) {
    if (s[i] == '1') {
      one--;
      pre[1][one]++;
      pre[1][one] %= mo;
      z = l - 1 - i;
      for (long long j = 1; j <= z; j++) {
        pre[1][one + j] += rec(z, j);
        pre[1][one + j] %= mo;
      }
    }
  }
  for (long long i = 2; i <= k; i++) {
    for (long long j = 2; j < 1015; j++) {
      pre[i][no_bit[j]] += pre[i - 1][j];
      pre[i][no_bit[j]] %= mo;
    }
  }
  cout << pre[k][1] % mo;
  return 0;
}
