#include <bits/stdc++.h>
using namespace std;
const double pi = 3.141592653589793238463;
const int m = 1000000007;
long long c[1009][1009];
long long choose(int n, int k) {
  if (n == k || k == 0) return 1;
  if (k == 1) return n;
  if (c[n][k] != -1) return c[n][k];
  return c[n][k] = (choose(n - 1, k) + choose(n - 1, k - 1)) % m;
}
int steps[1009];
int ReduceTo(int x) {
  int cnt = 0;
  while (x) cnt += x % 2, x /= 2;
  return cnt;
}
int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);
  memset((c), (-1), sizeof(c));
  steps[1] = 0;
  for (int x = 2; x < 1009; x++) steps[x] = 1 + steps[ReduceTo(x)];
  int k;
  string s;
  cin >> s >> k;
  int n = (int)s.length();
  if (k == 0) return cout << 1 << '\n', 0;
  if (k == 1) return cout << n - 1 << '\n', 0;
  long long ans = 0;
  for (int x = 2; x <= n; x++)
    if (steps[x] == k - 1) {
      ans += choose(n, x);
      ans = (ans + m) % m;
      int x2 = x;
      for (int bit = 0; bit < n; bit++) {
        if (x2 > n - bit) break;
        if (s[bit] == '1') {
          x2--;
          if (x2 == 0) break;
        } else {
          ans -= choose(n - bit - 1, x2 - 1);
          ans = (ans + m) % m;
        }
      }
    }
  cout << ans << '\n';
  return 0;
}
