#include <bits/stdc++.h>
using namespace std;
string num;
int n, k, sz;
long long int pre[100005];
long long int dp[1015][1010][3];
int f(int u) {
  if (u == 0) return -1;
  if (pre[u]) return pre[u];
  int kp = u;
  int val = 0;
  while (u > 1) {
    u = __builtin_popcount(u);
    val++;
  }
  return pre[kp] = val;
}
long long int g(int in, int cnt, int con) {
  if (in == sz) {
    return f(cnt) == k - 1;
  }
  if (dp[in][cnt][con] != -1) return dp[in][cnt][con];
  long long int ans = 0;
  if (con == 0) {
    if (num[in] == '0') {
      ans = (ans + g(in + 1, cnt, 0)) % 1000000007;
    } else {
      ans = (ans + g(in + 1, cnt, 1)) % 1000000007;
      ans = (ans + g(in + 1, cnt + 1, 0)) % 1000000007;
    }
  } else {
    ans = (ans + g(in + 1, cnt, 1)) % 1000000007;
    ans = (ans + g(in + 1, cnt + 1, 1)) % 1000000007;
  }
  return dp[in][cnt][con] = ans;
}
int main() {
  for (int i = 1; i <= 1000; i++) f(i);
  cin >> num;
  scanf("%d", &k);
  sz = num.size();
  if (sz < 4) {
    long long int n = 0, ans = 0;
    for (int i = 0; i < sz; i++) n = n * 2 + num[i] - '0';
    for (int i = 1; i <= n; i++) ans += f(i) == k;
    cout << ans << endl;
    return 0;
  }
  memset(dp, -1, sizeof dp);
  printf("%d", g(0, 0, 0) + (k == 1 ? -1 : 0));
}
