#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, k, c[1005], F[1005][1005][2];
bool Free[1005][1005][2];
char s[1005];
int Cal(int x) {
  if (x == 1) return 0;
  int sum = 0;
  while (x > 0) {
    sum += x % 2;
    x /= 2;
  }
  return Cal(sum) + 1;
}
int f(int i, int j, int smaller) {
  if (Free[i][j][smaller] == true) return F[i][j][smaller];
  Free[i][j][smaller] = true;
  if (i == n) return F[i][j][smaller] = (j > 0 && c[j] + 1 == k);
  if (smaller == 0)
    for (int t = 0; t <= int(s[i + 1] - '0'); t++)
      F[i][j][0] =
          (F[i][j][0] + f(i + 1, j + t, (t < int(s[i + 1] - '0')))) % mod;
  else
    for (int t = 0; t <= 1; t++)
      F[i][j][1] = (F[i][j][1] + f(i + 1, j + t, 1)) % mod;
  return F[i][j][smaller];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> s + 1 >> k;
  n = strlen(s + 1);
  c[1] = 0;
  for (int i = 2; i <= n; i++) c[i] = Cal(i);
  if (k == 0)
    cout << 1;
  else if (k == 1)
    cout << (f(0, 0, 0) - 1 + mod) % mod;
  else
    cout << f(0, 0, 0);
}
