#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  long long k;
  cin >> k;
  if ((s.length() == 1 && s[0] == '1' && k == 1) || k > 5) {
    cout << "0";
    return 0;
  }
  if (k == 0) {
    cout << "1";
    return 0;
  }
  long long dp[1004], i, j;
  vector<long long> lan;
  long long p = s.length(), f = 0;
  for (i = 0; i < p; i++) {
    if (s[i] == '1') f++;
    lan.push_back(s[i] - '0');
  }
  dp[1] = 0;
  for (i = 2; i <= 1003; i++) {
    dp[i] = 1;
    long long temp = i, l = 0;
    while (temp) {
      if (temp % 2) l++;
      temp /= 2;
    }
    dp[i] += dp[l];
  }
  long long dpr[1004][1004];
  for (i = 0; i <= 1003; i++)
    for (j = 0; j <= 1003; j++) dpr[i][j] = 0;
  dpr[1][1] = 1;
  dpr[1][0] = 1;
  for (i = 2; i <= 1003; i++) {
    dpr[i][1] = 1;
    dpr[i][0] = 1;
    for (j = 2; j <= i; j++)
      dpr[i][j] = (dpr[i - 1][j] + dpr[i - 1][j - 1]) % 1000000007;
  }
  for (i = 2; i <= 1003; i++)
    for (j = 1; j <= 1003; j++) dpr[i][j] += dpr[i - 1][j];
  dpr[0][0] = 1;
  long long ans = 0;
  if (1 + dp[f] == k) ans = 1;
  long long u = 0;
  for (i = 0; i < lan.size(); i++) {
    if (lan[i] == 1) {
      for (j = 0; j + u <= 1003; j++) {
        if (u + j != 0 && 1 + dp[u + j] == k) {
          ans = (ans + dpr[p - i - 1][j]) % 1000000007;
          if (i == 0 && k == 1) {
            ans = (ans + 1000000007 - 1) % 1000000007;
          }
        }
      }
      u++;
    }
  }
  cout << ans;
  return 0;
}
