#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30;
const int N = 1003, mod = 1000000007;
int n, q;
char a[N];
int k;
int p[N];
int calc(int x) {
  if (x == 1) return 0;
  if (p[x] != -1) return p[x];
  int cnt = 0, ret = 0;
  while (x) {
    cnt += (x % 2);
    x /= 2;
  }
  return ret = calc(cnt) + 1;
}
void pre() {
  memset(p, -1, sizeof p);
  for (int i = 1; i <= 1000; i++) {
    p[i] = calc(i);
  }
}
int mem[N][N][2];
int dp(int i, int kk, int f) {
  if (i == n) {
    return (k == p[kk] + 1 && kk != 0);
  }
  int &ret = mem[i][kk][f];
  if (ret != -1) return ret;
  ret = 0;
  if (f) {
    ret += dp(i + 1, kk + 1, f) % mod;
    ret %= mod;
    ret += dp(i + 1, kk, f) % mod;
    ret %= mod;
  } else {
    if (a[i] == '0') {
      ret += dp(i + 1, kk, f) % mod;
      ret %= mod;
    } else {
      ret += dp(i + 1, kk + 1, f) % mod;
      ret %= mod;
      ret += dp(i + 1, kk, 1) % mod;
      ret %= mod;
    }
  }
  return ret;
}
int main() {
  pre();
  scanf("%s", a);
  scanf("%d", &k);
  n = strlen(a);
  if (k == 0) {
    printf("1");
    return 0;
  }
  memset(mem, -1, sizeof mem);
  printf("%d", (dp(0, 0, 0) % mod + (k == 1 ? -1 : 0)));
  return 0;
}
