#include <bits/stdc++.h>
using namespace std;
string s;
long long dp[1001][1001][2];
long long solve(long long x, long long k, bool ok) {
  if (x == -1) {
    if (k == 0) {
      return 1;
    }
    return 0;
  }
  if (~dp[x][k][ok]) {
    return dp[x][k][ok];
  }
  long long ans = 0;
  if (s[x] == '1') {
    ans = solve(x - 1, k, 1) % 1000000007;
    if (k - 1 >= 0) {
      ans = (ans + solve(x - 1, k - 1, ok)) % 1000000007;
    }
  } else {
    ans = solve(x - 1, k, ok) % 1000000007;
    if (ok == 1 && k - 1 >= 0) {
      ans = (ans + solve(x - 1, k - 1, 1)) % 1000000007;
    }
  }
  return dp[x][k][ok] = ans;
}
long long dp2[1001];
long long reduce(long long n) {
  if (n == 1) {
    return 0;
  }
  if (~dp2[n]) {
    return dp2[n];
  }
  long long cnt = 0;
  for (long long i = 30; i >= 0; i--) {
    if (n & (1 << i)) {
      cnt++;
    }
  }
  return dp2[n] = 1 + reduce(cnt);
}
long long k;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  memset(dp, -1, sizeof dp);
  memset(dp2, -1, sizeof dp2);
  cin >> s;
  reverse(s.begin(), s.end());
  cin >> k;
  long long ans = 0;
  long long c = 0;
  for (long long i = 0; i < s.size(); i++) {
    c += (s[i] - '0');
  }
  for (long long i = 1; i <= s.size(); i++) {
    if (reduce(i) + 1 == k && i != 1) {
      ans = (ans + solve(s.size() - 1, i, 0)) % 1000000007;
    } else if (i == 1 && k == 0) {
      ans = (ans + 1) % 1000000007;
    } else if (i == 1 && k > 0 && reduce(i) + 1 == k) {
      ans = (ans + solve(s.size() - 1, i, 0) - 1 + 1000000007) % 1000000007;
    }
  }
  cout << ans << endl;
}
