#include <bits/stdc++.h>
using namespace std;
template <typename T>
void dbg(T a) {}
template <typename T, typename... Arg>
void dbg(T a, Arg... arg) {}
const int maxn = (1e3) + 7;
const int inf = (1e9) + 7;
const long long LLinf = (1e18) + 7;
const long double eps = 1e-9;
const long long mod = 1e9 + 7;
long long res = 0LL;
int k;
vector<int> V;
int odl[maxn];
long long net[maxn][maxn];
void licz(int x) {
  int roz = (int)V.size();
  for (auto s : V) {
    roz--;
    if (roz + 1 < x) continue;
    if (x < 0) continue;
    if (s == 0)
      continue;
    else {
      res += net[roz][x];
      res %= mod;
      x--;
    }
  }
  if (roz == 0 && x == 0) res++;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  long long curr = 0LL;
  if ((int)s.size() < 20) {
    for (auto v : s) {
      curr *= 2LL;
      curr += v - '0';
    }
  } else
    curr = 100000LL;
  for (int i = 0; i < 1005; i++) net[i][0] = net[i][i] = 1;
  for (int i = 1; i < 1005; i++)
    for (int j = 1; j <= i; j++) {
      net[i][j] = (net[i - 1][j - 1] + net[i - 1][j]) % mod;
    }
  for (auto v : s)
    if (v == '0')
      V.push_back(0);
    else
      V.push_back(1);
  cin >> k;
  odl[1] = 0;
  for (int i = 2; i <= 1005; i++) {
    int ile = 0;
    for (int j = 0; j < 20; j++)
      if (((1 << j) & i)) ile++;
    odl[i] = 1 + odl[ile];
  }
  if (curr < 1005) {
    int res = 0;
    for (int i = 1; i <= curr; i++)
      if (odl[i] == k) res++;
    cout << res;
    return 0;
  }
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  if (k == 1) {
    cout << (int)V.size() - 1;
    return 0;
  }
  for (int i = 1; i <= min(curr, (long long)1005); i++) {
    if (odl[i] + 1 == k) licz(i);
  }
  res = (res % mod + mod) % mod;
  cout << res;
  return 0;
}
