#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)5e3 + 10;
const int MOD = (int)1e9 + 7;
long long dp[1111][1111];
int num[1111], k;
int mark[1111];
long long dfs(int pos, int x, int flag) {
  if (pos == 0) return mark[x] == k - 1 && (x != 0);
  if (dp[pos][x] != -1 && !flag) {
    return dp[pos][x];
  }
  long long ans = 0;
  int ed = flag ? num[pos] : 1;
  for (int i = 0; i <= ed; i++) {
    ans += dfs(pos - 1, x + i, flag && i == ed);
    ans %= MOD;
  }
  if (!flag) dp[pos][x] = ans;
  return ans;
}
char str[1111];
long long solve() {
  memset(dp, -1, sizeof(dp));
  int len = 0, l = strlen(str + 1);
  for (int i = l; i >= 1; i--) {
    num[++len] = str[i] - '0';
  }
  if (k == 0) return 1;
  if (k == 1) return len - 1;
  return dfs(len, 0, 1);
}
int work(int x) {
  int re = 0;
  while (x) {
    re++;
    x -= x & (-x);
  }
  return re;
}
void init() {
  mark[1] = 0;
  for (int i = 2; i <= 1000; i++) mark[i] = mark[work(i)] + 1;
}
int main() {
  init();
  scanf("%s", str + 1);
  scanf("%d", &k);
  printf("%lld\n", solve());
  return 0;
}
