#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
int d[1010];
char s[1010];
int ma_num, k;
int c[maxn][maxn];
void init() {
  for (int i = 2; i < 1010; i++) d[i] = d[__builtin_popcount(i)] + 1;
  for (int i = 0; i < maxn; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
}
int count(int x) {
  int sum = c[ma_num][x];
  int pre_1 = 0;
  for (int i = 0; i < ma_num; i++) {
    if (x - pre_1 == 0) break;
    if (s[i] == '0') {
      if (ma_num - i - 1 < x - pre_1 - 1) break;
      sum = (sum + mod - c[ma_num - i - 1][x - pre_1 - 1]) % mod;
    } else
      pre_1++;
  }
  return sum % mod;
}
int main() {
  scanf("%s%d", s, &k);
  if (k == 0) {
    printf("%d\n", 1);
    return 0;
  } else {
    ma_num = strlen(s);
    init();
    int sum = 0;
    for (int i = 1; i <= ma_num; i++) {
      if (d[i] == k - 1) {
        sum = (sum + count(i)) % mod;
      }
    }
    if (k == 1) sum = (sum + mod - 1) % mod;
    printf("%d\n", sum);
  }
  return 0;
}
