#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const int INF = 0x3f3f3f3f, N = 2e6 + 5, MOD = 1e9 + 7;
char str[N];
int f[N];
long long c[1005][1005];
long long C(long long n, long long m) { return c[n][m]; }
int Solve() {
  int k;
  cin >> str >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  int len = strlen(str);
  f[1] = 0;
  for (int i = 2; i <= 1000; i++) f[i] = f[__builtin_popcount(i)] + 1;
  long long res = 0;
  if (k == 1) res--;
  for (int i = 1; i <= 1000; i++) {
    if (f[i] == k - 1) {
      int left = i;
      for (int j = 0; j < len && left; j++) {
        if (str[j] == '1') res = (res + C(len - 1 - j, left)) % MOD, left--;
      }
      if (!left) res++;
    }
  }
  cout << res << endl;
  return 0;
}
void Pre() {
  c[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; j++)
      c[i][j] = (0ll + c[i - 1][j - 1] + c[i - 1][j]) % MOD;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  Pre();
  while (Solve())
    ;
  return 0;
}
