#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
char str[maxn];
long long mul[maxn];
long long inv[maxn];
int dp[maxn];
int len, k;
void init() {
  mul[0] = 1;
  for (int i = 1; i < maxn; i++) mul[i] = (mul[i - 1] * i) % mod;
  inv[0] = inv[1] = 1;
  for (int i = 2; i < maxn; i++)
    inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
  for (int i = 1; i < maxn; i++) inv[i] = (inv[i - 1] * inv[i]) % mod;
}
long long C(int n, int m) { return mul[n] * inv[m] % mod * inv[n - m] % mod; }
int getNum(int x) {
  int res = 0;
  while (x) {
    res += x & 1;
    x >>= 1;
  }
  return res;
}
int call(int x) {
  int res = 0;
  for (int i = 0; i < len; i++)
    if (str[i] - '0') res = (res + C(len - i - 1, x--)) % mod;
  return (res + (x == 0)) % mod;
}
void solve() {
  len = strlen(str);
  if (k == 0)
    cout << 1 << endl;
  else if (k == 1)
    cout << len - 1 << endl;
  else {
    int ans = 0;
    for (int i = 2; i <= 1000; i++) {
      dp[i] = dp[getNum(i)] + 1;
      if (dp[i] == k - 1) ans = (ans + call(i)) % mod;
    }
    cout << ans << endl;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  init();
  cin >> str >> k;
  solve();
  return 0;
}
