#include <bits/stdc++.h>
using namespace std;
const int p = 1000000007;
int n, k;
int Bit[1010];
int f[1010][1010], d[1010];
bool use[1010];
int dfs(int pos, int limit, int k) {
  if (!pos) return use[k];
  if (!limit && ~f[pos][k]) return f[pos][k];
  int up = limit ? d[pos] : 1, ans = 0;
  for (int i = 0; i <= up; ++i)
    ans = (ans + dfs(pos - 1, limit && i == d[pos], k + i)) % p;
  if (!limit) f[pos][k] = ans;
  return ans;
}
int main() {
  fill(f[0], f[0] + 1010 * 1010, -1);
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  char s[1010];
  cin >> s + 1 >> k;
  n = strlen(s + 1);
  if (!k) return cout << "1\n", 0;
  for (int i = 1; i <= n; ++i) d[i] = s[i] - '0';
  reverse(d + 1, d + n + 1);
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= 10; ++j)
      if (i >> j & 1) Bit[i]++;
  for (int i = 1; i <= n; ++i) {
    int x = i, s = 1;
    while (x != 1) x = Bit[x], ++s;
    use[i] = s == k;
  }
  cout << dfs(n, 1, 0) - (k == 1) << "\n";
  return 0;
}
