#include <bits/stdc++.h>
using namespace std;
char s[1010];
int n, m, c[1010];
int num[1010], k, ans;
int f[1010][1010][2];
inline int add(int x, int y) {
  x += y;
  if (x >= 1000000007) x -= 1000000007;
  return x;
}
inline void init() {
  num[0] = 0;
  for (int i = 1; i <= 1005; i++) num[i] = num[i ^ (i & -i)] + 1;
  c[1] = 0, c[0] = 123456;
  for (int i = 2; i <= 1005; i++) {
    c[i] = c[num[i]] + 1;
  }
}
inline void solve() {
  n = strlen(s + 1);
  f[0][0][1] = 1;
  for (int i = 1; i <= n; i++)
    if (s[i] == '1') {
      f[i][0][0] = add(f[i - 1][0][0], f[i - 1][0][1]);
      f[i][0][1] = 0;
      for (int j = 1; j <= i; j++) {
        f[i][j][0] =
            add(add(f[i - 1][j][0], f[i - 1][j][1]), f[i - 1][j - 1][0]);
        f[i][j][1] = f[i - 1][j - 1][1];
      }
    } else {
      f[i][0][0] = f[i - 1][0][0];
      f[i][0][1] = f[i - 1][0][1];
      for (int j = 1; j <= i; j++) {
        f[i][j][0] = add(f[i - 1][j][0], f[i - 1][j - 1][0]);
        f[i][j][1] = f[i - 1][j][1];
      }
    }
  ans = 0;
  for (int i = 0; i <= n; i++)
    if (c[i] == k - 1) ans = add(ans, add(f[n][i][0], f[n][i][1]));
  if (k == 0)
    ans++;
  else if (k == 1)
    ans--;
}
int main() {
  init();
  scanf("%s", s + 1);
  scanf("%d", &k);
  solve();
  printf("%d\n", ans);
  return 0;
}
