#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e3 + 1, mod = 1000000007, bit = 30;
long long int dp[N] = {0}, ncr[N][N];
void pre() {
  ncr[0][0] = 1;
  ncr[1][0] = ncr[1][1] = 1;
  for (long long int i = 2; i < N; i++) {
    ncr[i][0] = ncr[i][i] = 1;
    for (long long int j = 1; j < i; j++) {
      ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % mod;
    }
  }
}
long long int solve(string &s, long long int k) {
  long long int ans = 0, i, n = s.length(), curr = k;
  for (i = 0; i < n; i++) {
    if (curr == 0) {
      ans++;
      break;
    }
    if (s[i] == '1') {
      ans += ncr[n - i - 1][curr];
      ans %= mod;
      curr--;
    }
  }
  if (i == n && curr == 0) {
    ans++;
  }
  ans %= mod;
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long int pro = 1, temp, t, i, j, l, r, n, m, mid, z, k, x, y, rem,
                carry = 0, ind, ans = 0, mx = -LONG_LONG_MAX,
                mn = LONG_LONG_MAX, cnt = 0, curr = 0, prev, next, sum = 0,
                flag = 1, i1 = -1, i2 = -1;
  pre();
  dp[0] = 0;
  dp[1] = 0;
  string s;
  cin >> s;
  cin >> k;
  for (i = 2; i < N; i++) {
    dp[i] = 1 + dp[__builtin_popcount(i)];
  }
  mx = 5;
  vector<long long int> adj[mx + 1];
  for (i = 1; i < N; i++) {
    dp[i]++;
    adj[dp[i]].push_back(i);
  }
  if (k > mx) {
    return cout << 0, 0;
  }
  for (auto it : adj[k]) {
    if (it > s.length()) {
      break;
    }
    ans = (ans + solve(s, it)) % mod;
  }
  if (k == 1 && s[0] == '1') {
    ans += mod - 1;
    ans %= mod;
  }
  if (k == 0 && s[0] == '1') {
    ans++;
    ans %= mod;
  }
  cout << ans << '\n';
  return 0;
}
