#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;
char s[1005];
int k, cnt[1005];
long long dp[3][1005][1005][10];
long long dfs(long long pos, int pre, int num, bool flag) {
  if (pos < 0) return cnt[num] == k;
  if (!flag && ~dp[pre][pos][num][k]) return dp[pre][pos][num][k];
  int end = flag ? s[pos] : 1;
  long long ret = 0;
  for (int i = 0; i <= end; i++)
    ret = (ret + dfs(pos - 1, i, num + (i == 1), flag && i == end) % M) % M;
  if (!flag) dp[pre][pos][num][k] = ret;
  return ret;
}
int get(int x) {
  if (x == 1) return 0;
  int y = 0;
  for (; x; x >>= 1)
    if (x & 1) y++;
  return 1 + get(y);
}
int main() {
  memset(dp, -1, sizeof(dp));
  for (int i = 1; i < 1005; i++) cnt[i] = get(i) + 1;
  while (~scanf("%s%d", s, &k)) {
    int len = strlen(s);
    reverse(s, s + len);
    for (int i = 0; i < len; i++) s[i] -= '0';
    long long ans = dfs(len - 1, 0, 0, 1);
    ans = (ans % M + M) % M;
    if (k == 1 && ans) ans--;
    printf("%I64d\n", ans);
  }
  return 0;
}
