#include <bits/stdc++.h>
using namespace std;
string s;
int k;
int dp[1009];
int y[1009][1009];
int l;
int m = 1000000007;
int cnt = 0;
long long Find(int x) {
  long long ret = 0;
  if (cnt >= x) ret++;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '1') {
      int n = (s.size() - i - 1);
      if (n == x)
        ret += 1;
      else if (n > x)
        ret = (ret + y[n][x]) % m;
      x--;
      if (x == 0) {
        return ret;
      }
    }
  }
  return ret;
}
int main() {
  cin >> s;
  cin >> k;
  if (k == 0) {
    cout << 1 << endl;
    exit(0);
  }
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '1') {
      l = i;
      cnt++;
    }
  }
  y[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    y[i][0] = 1;
    for (int j = i; j >= 1; j--) {
      y[i][j] = (y[i - 1][j - 1] + y[i - 1][j]) % m;
    }
  }
  for (int i = 2; i <= 1000; i++) {
    int num = 0;
    for (int j = 0; j < 32; j++) {
      if ((i & (1 << j)) > 0) num++;
    }
    dp[i] = dp[num] + 1;
  }
  int ans = 0;
  for (int i = 1; i <= 1000; i++) {
    if (dp[i] == k - 1) {
      if (i == 1)
        ans = (ans + Find(i) - 1) % m;
      else
        ans = (ans + Find(i)) % m;
    }
  }
  cout << ans << endl;
}
