#include <bits/stdc++.h>
using namespace std;
const int N = 100001, M = 350;
mt19937 gen(time(NULL));
template <typename T = int>
inline T read() {
  T val = 0, sign = 1;
  char ch;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') sign = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) val = val * 10 + ch - '0';
  return sign * val;
}
int dp[1050];
int dp2[1050][1050][2];
int mod = 1e9 + 7;
void add(int &u, int v) {
  u += v;
  if (u >= mod) u -= mod;
}
void solve() {
  dp[1] = 0;
  for (int i = 2; i < 1050; i++) {
    int cnt = 0, j = i;
    while (j) {
      cnt += (j % 2);
      j /= 2;
    }
    dp[i] = dp[cnt] + 1;
  }
  string s;
  cin >> s;
  int k = read();
  if (!k) {
    puts("1");
    return;
  }
  if (k == 1 && s == "1") {
    puts("0");
    return;
  }
  dp2[0][0][1] = 1;
  for (int i = 0; i < s.length(); i++)
    for (int j = 0; j < 1050; j++) {
      add(dp2[i + 1][j + 1][0], dp2[i][j][0]);
      add(dp2[i + 1][j][0], dp2[i][j][0]);
      if (s[i] == '0') {
        add(dp2[i + 1][j][1], dp2[i][j][1]);
      } else {
        add(dp2[i + 1][j + 1][1], dp2[i][j][1]);
        add(dp2[i + 1][j][0], dp2[i][j][1]);
      }
    }
  int ans = 0;
  k--;
  for (int i = 1; i < 1050; i++)
    if (dp[i] == k) {
      add(ans, dp2[s.length()][i][0] + dp2[s.length()][i][1]);
    }
  if (k == 0) ans--;
  ans = (ans + mod) % mod;
  printf("%d\n", ans);
}
void precalc() {}
signed main() {
  int t = 1;
  precalc();
  while (t--) {
    clock_t z = clock();
    solve();
    fprintf(stderr, "Total Time: %.3f\n",
            (double)(clock() - z) / CLOCKS_PER_SEC),
        fflush(stderr);
  }
}
