#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int sz = 1e5 + 10;
const ll mod = 1e9 + 7;
ll dp[sz];
ll k, ans, mx;
string n;
vector<int> digit;
int lim;
ll dp2[3][3][1005][1005];
int kk;
ll rec(bool start, bool small, int pos, int koita) {
  if (koita < 0) return 0;
  if (pos == lim) return koita == 0;
  ll& ret = dp2[start][small][pos][koita];
  if (~ret) return ret;
  int sesh = small ? 1 : digit[pos];
  ret = 0;
  if (!start) {
    for (int i = 0; i <= sesh; i++) {
      ret =
          (ret + rec(false, small || i < digit[pos], pos + 1, koita - i)) % mod;
    }
  } else {
    for (int i = 1; i <= sesh; i++) {
      ret =
          (ret + rec(false, small || i < digit[pos], pos + 1, koita - i)) % mod;
    }
    ret = (ret + rec(true, true, pos + 1, kk)) % mod;
  }
  return ret %= mod;
}
ll calc() { return rec(true, false, 0, kk); }
int main() {
  for (int i = 2; i < 1005; i++) {
    int x = __builtin_popcount(i);
    dp[i] = dp[x] + 1;
    mx = max(mx, dp[i]);
  }
  while (cin >> n >> k) {
    reverse(n.begin(), n.end());
    digit.clear();
    for (const char& c : n) digit.push_back(c - '0');
    lim = (int)n.size();
    reverse(digit.begin(), digit.end());
    memset(dp2, -1, sizeof dp2);
    if (k == 0)
      ans = 1ll;
    else if (k == 1) {
      kk = 1;
      ans = (calc() - 1ll + mod) % mod;
    } else {
      ans = 0ll;
      for (int i = 1; i <= 1000; i++) {
        if (dp[i] == k - 1) {
          kk = i;
          ans = (calc() + ans) % mod;
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
