#include <bits/stdc++.h>
using namespace std;
string n;
int k, num = 0;
long long dp[1001] = {0};
long long comb[1002][1002];
long long ones(long long n) {
  long long num = 0LL;
  while (n) {
    if (n & 1) num++;
    n >>= 1;
  }
  return num;
}
long long solve(long long num) {
  long long res = 0LL;
  long long s = n.size();
  for (int i = 0; i < s; i++) {
    if (n[i] == '1') {
      res += comb[s - i - 1][num];
      num--;
      res %= 1000000007;
    }
    if (num < 0) break;
  }
  return res + ((num == 0) ? 1 : 0);
}
int main() {
  cin >> n >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  long long num = 0;
  for (int i = 0; i < n.size(); i++)
    if (n[i] == '1') num++;
  dp[1] = 0;
  long long s = n.size();
  for (int i = 2; i <= s; i++) {
    long long res = ones(i);
    dp[i] = dp[res] + 1;
  }
  comb[0][0] = 1;
  for (int i = 1; i < 1001; i++) {
    comb[i][0] = 1;
    comb[i][1] = i;
    comb[i][i] = 1;
  }
  for (int i = 2; i <= s; i++) {
    for (int j = 1; j <= i; j++) {
      comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % 1000000007;
    }
  }
  long long out = 0LL;
  for (int i = 1; i <= s; i++) {
    if (dp[i] == k - 1) {
      out += solve(i);
    }
    out %= 1000000007;
  }
  cout << ((k == 1) ? out - 1 : out) << endl;
  return 0;
}
