#include <bits/stdc++.h>
using namespace std;
const int MAXK = 1001, MOD = 1e9 + 7;
int bits = 0, k, memo[MAXK][MAXK][2];
char c = '0';
bool b[MAXK];
bool ok(int x) {
  if (x == 0) return k == 0;
  int cnt = 0;
  while (x != 1) x = __builtin_popcount(x), cnt++;
  return cnt == k - 1;
}
int dp(int i = 1, int cnt = 0, bool flg = false) {
  if (i == bits + 1) return ok(cnt);
  if (memo[i][cnt][flg] != -1) return memo[i][cnt][flg];
  if (flg)
    return memo[i][cnt][flg] =
               (0LL + dp(i + 1, cnt + 1, true) + dp(i + 1, cnt, true)) % MOD;
  else if (b[i] == 0)
    return memo[i][cnt][flg] = dp(i + 1, cnt, false);
  else
    return memo[i][cnt][flg] =
               (0LL + dp(i + 1, cnt + 1, false) + dp(i + 1, cnt, true)) % MOD;
}
int main() {
  memset(memo, -1, sizeof memo);
  while (true) {
    scanf("%c", &c);
    if (c == '\n') break;
    b[++bits] = c - '0';
  }
  scanf("%d", &k);
  printf("%d\n", dp() % MOD - (k == 1));
}
