#include <bits/stdc++.h>
using namespace std;
long long const p = 1e9 + 7;
long long n, k, digit[1005], need[1005], f[1005][1005];
char s[1005];
inline long long count(long long x) {
  long long res = 0;
  for (long long i = 0; i <= 10; i++)
    if (x & (1 << i)) res++;
  return res;
}
long long dfs(long long pos, long long sum, bool down) {
  if (pos == -1) return need[sum] == k;
  if (down && ~f[pos][sum]) return f[pos][sum];
  long long end = down ? 1 : digit[pos], res = 0;
  for (long long i = 0; i <= end; i++)
    res = (res + dfs(pos - 1, sum + (i == 1), down || i != end)) % p;
  if (down) f[pos][sum] = res;
  return res;
}
inline long long calc() {
  memset(f, -1, sizeof(f));
  return dfs(n - 1, 0, false);
}
signed main() {
  need[1] = 1;
  for (long long i = 2; i <= 1000; i++) {
    long long num = count(i);
    need[i] = need[num] + 1;
  }
  gets(s);
  n = strlen(s);
  for (long long i = 0; i < n; i++) digit[n - i - 1] = (s[i] ^ 48);
  scanf("%lld", &k);
  long long ans = calc();
  if (k == 1) ans = (ans - 1 + p) % p;
  printf("%lld\n", ans);
  return 0;
}
