#include <bits/stdc++.h>
using namespace std;
long long int C[1005][1005] = {0}, mod = 1e9 + 7;
void nCr() {
  C[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    C[i][0] = 1;
    for (int j = i; j > 0; j--) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
}
int main() {
  nCr();
  int a[2000] = {0}, b[2000] = {0};
  a[0] = 100000;
  for (int i = 2; i <= 1000; i++) {
    int d = i, cnt = 0;
    while (d > 0) {
      cnt += d % 2;
      d /= 2;
    }
    a[i] = a[cnt] + 1;
    b[a[i]]++;
  }
  string s;
  cin >> s;
  int k;
  cin >> k;
  if (k == 0) {
    cout << "1";
    return 0;
  }
  long long int ans = 0;
  int n = s.length();
  int temp = 0;
  if (n == 1 && k == 1) {
    cout << 0;
    return 0;
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') continue;
    for (int j = 0; j <= n - i - 1; j++) {
      if (a[j + temp] == k - 1) {
        ans = (ans + C[n - i - 1][j]) % mod;
        if (j == 1 && temp == 0) ans--;
      }
    }
    if (s[i] == '1') temp++;
  }
  if (a[temp] == k - 1) {
    ans = (ans + 1) % mod;
  }
  cout << ans;
  return 0;
}
