#include <bits/stdc++.h>
using namespace std;
int dp[1001];
int ncr[1001][1001];
void compNCR() {
  for (int i = 0; i < 1001; i++) {
    ncr[i][0] = 1;
  }
  for (int i = 1; i < 1001; i++) {
    for (int j = 1; j < 1001; j++) {
      ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % 1000000007;
    }
  }
}
int countOnes(int x) { return ((x > 0) ? (1 + countOnes(x - 1 & x)) : 0); }
int main() {
  string n;
  int k;
  cin >> n >> k;
  if (k == 0) {
    cout << 1;
    return 0;
  }
  compNCR();
  dp[1] = 0;
  for (int i = 2; i < 1001; i++) {
    dp[i] = 1 + dp[countOnes(i)];
  }
  int ans = 0, nOnes;
  for (int i = 1; i < 1001; i++) {
    if (dp[i] == k - 1) {
      nOnes = 0;
      for (int j = 0; j < n.size() && i >= nOnes; j++) {
        if (n[j] == '1') {
          if (k == 1 && nOnes == 0 && i == 1) ans--;
          ans = (ans + ncr[n.size() - 1 - j][i - nOnes]) % 1000000007;
          nOnes++;
        }
      }
    }
  }
  nOnes = 0;
  for (int i = 0; i < n.size(); i++) {
    if (n[i] == '1') {
      nOnes++;
    }
  }
  if (dp[nOnes] == k - 1) {
    ans = (ans + 1) % 1000000007;
  }
  cout << ans;
}
