#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int ile[1000010], n, k, jedynki;
char s[1000010];
long long fact[1000010], inv[1000010], ans;
long long pot(long long a, long long b) {
  long long p = a, wyn = 1;
  for (int i = 1; i <= b; i <<= 1) {
    if (b & i) {
      wyn = (wyn * p) % MOD;
    }
    p = (p * p) % MOD;
  }
  return wyn;
}
void sil() {
  fact[0] = inv[0] = 1;
  for (int i = 1; i <= 1e3; i++) {
    fact[i] = (fact[i - 1] * i) % MOD;
    inv[i] = pot(fact[i], MOD - 2);
  }
}
int dwumian(int n, int k) {
  return ((fact[n] * inv[k]) % MOD * inv[n - k]) % MOD;
}
int main() {
  scanf("%s", s + 1);
  sil();
  int n = strlen(s + 1);
  scanf("%d", &k);
  if (k == 0) {
    return puts("1"), 0;
  }
  ile[1] = 0;
  ile[0] = -1e6;
  for (int i = 2; i <= 1000; i++) {
    ile[i] = ile[__builtin_popcount(i)] + 1;
  }
  for (int i = 1; i <= n; i++) {
    if (s[i] == '1') {
      for (int j = 0; j <= n - i; j++) {
        if (ile[jedynki + j] == k - 1) {
          if (j == 1 && jedynki == 0) {
            ans = (ans + dwumian(n - i, j) - 1 + MOD) % MOD;
          } else {
            ans = (ans + dwumian(n - i, j)) % MOD;
          }
        }
      }
      jedynki++;
    }
  }
  if (ile[jedynki] == k - 1 && n != 1) {
    ans++;
  }
  printf("%lld", ans);
  return 0;
}
