#include <bits/stdc++.h>
using namespace std;
inline long long qr() {
  long long x = 0, f = 1;
  char ch;
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = -1;
  for (; isdigit(ch); x = x * 10 + ch - 48, ch = getchar())
    ;
  return x * f;
}
const int mod = 1e9 + 7;
int k, a[1010], b[1010];
long long d[1010][2][1010];
long long dfs(int p, int pre, int x, bool lim) {
  if (p == 0) return b[x] == k;
  if (!lim && ~d[p][pre][x]) return d[p][pre][x];
  int mx = lim ? a[p] : 1;
  long long res = 0;
  for (int i = 0; i <= mx; ++i)
    res = (res + dfs(p - 1, i, x + (i == 1), lim && i == mx)) % mod;
  if (!lim) d[p][pre][x] = res;
  return res;
}
char s[1010];
void solve() {
  int len = strlen(s + 1);
  memset(d, -1, sizeof d);
  reverse(s + 1, s + 1 + len);
  for (int i = 1; i <= len; ++i) a[i] = s[i] - '0';
  long long ans = dfs(len, 0, 0, 1);
  ans = (ans % mod + mod) % mod;
  if (k == 1 && ans) ans--;
  printf("%lld\n", ans);
}
int main() {
  for (int i = 1; i <= 1000; ++i) {
    int t = i, ct = 0;
    while (t ^ 1) {
      int tt = 0;
      while (t) {
        if (t & 1) tt++;
        t >>= 1;
      }
      t = tt;
      ct++;
    }
    b[i] = ct + 1;
  }
  scanf("%s", s + 1);
  k = qr();
  solve();
  return 0;
}
