#include <bits/stdc++.h>
using namespace std;
const int MXN = (int)1e6 + 10;
const int INF = (int)1e9 + 7;
const double EPS = (double)1e-9;
const double PI = (double)acos(-1.0);
string s;
int k;
int pre[1111];
int n;
int b[1111];
int dp[1111][1111][3];
inline void add(int &x, int y) {
  x += y;
  if (x >= INF) x -= INF;
}
int main() {
  cin >> s >> k;
  n = (int)s.size();
  if (!k) {
    cout << 1;
    return 0;
  }
  if (k == 1) {
    cout << n - 1;
    return 0;
  }
  if (k > 7) {
    cout << 0;
    return 0;
  }
  for (int i = 2; i <= 1010; ++i) {
    pre[i] = pre[(int)__builtin_popcount(i)] + 1;
  }
  for (int i = 0; i < n; ++i) {
    b[i] = s[i] - '0';
  }
  dp[0][1][1] = 1;
  dp[0][0][0] = 1;
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= n; ++j) {
      add(dp[i][j][0], dp[i - 1][j][0]);
      if (j) add(dp[i][j][0], dp[i - 1][j - 1][0]);
      if (b[i] == 1) {
        add(dp[i][j][0], dp[i - 1][j][1]);
        if (j) add(dp[i][j][1], dp[i - 1][j - 1][1]);
      } else {
        add(dp[i][j][1], dp[i - 1][j][1]);
      }
    }
  }
  int ans = 0;
  pre[0] = -INF;
  for (int j = 0; j <= n; ++j) {
    if (1 + pre[j] == k) {
      add(ans, dp[n - 1][j][0]);
      add(ans, dp[n - 1][j][1]);
    }
  }
  cout << ans;
  return 0;
}
