#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int MOD = (int)1e9 + 7;
int fact[maxn], invfact[maxn];
long long dp[maxn], res;
int add(int a, int b) {
  int c = a + b;
  if (c >= MOD) c -= MOD;
  if (c < 0) c += MOD;
  return c;
}
int mul(int a, int b) {
  int c = 1LL * a * b % MOD;
  return c;
}
int pwr(int a, int b) {
  if (!b) return 1;
  int res = pwr(a, b >> 1);
  res = mul(res, res);
  if (b & 1) res = mul(res, a);
  return res;
}
int inv(int p) { return pwr(p, MOD - 2); }
int C(int n, int k) {
  if (k > n) {
    return 0;
  }
  if (k == 0) {
    return 1;
  }
  int ans = fact[n];
  ans = mul(ans, invfact[k]);
  ans = mul(ans, invfact[n - k]);
  return ans;
}
int Count(int x) { return (int)__builtin_popcount(x); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fact[0] = 1;
  for (int i = 1; i < maxn; i++) fact[i] = mul(fact[i - 1], i);
  for (int i = 0; i < maxn; i++) invfact[i] = inv(fact[i]);
  dp[1] = 1;
  for (int i = 2; i < maxn; i++) {
    int tmp = Count(i);
    dp[i] = dp[tmp] + 1;
  }
  string s;
  int k;
  cin >> s >> k;
  int before = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '1') {
      for (int j = 0; j < s.size() - i; j++) {
        if (dp[j + before] == k) {
          res = add(res, C(s.size() - i - 1, j));
        }
      }
      before++;
    }
  }
  if (dp[before] == k) {
    res = add(res, 1);
  }
  if (k == 1) {
    res = add(res, -1);
  }
  if (k == 0) {
    res = 1;
  }
  cout << res;
  return 0;
}
