#include <bits/stdc++.h>
using namespace std;
int MOD = (int)1e9 + 7;
string s;
int C[1005][1005];
void preprocess() {
  int i, j;
  for (i = 0; i <= 1002; i++) {
    for (j = 0; j <= min(i, 1002); j++) {
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] % MOD + C[i - 1][j] % MOD;
      C[i][j] %= MOD;
    }
  }
}
long long solve(long long set, int pos) {
  if (set < 0) return 0;
  if (pos == s.size()) return (set == 0 ? 1 : 0);
  long long ans = 0;
  if (s[pos] == '1') ans += C[s.size() - pos - 1][set];
  ans += solve(set - s[pos] + '0', pos + 1) % MOD;
  ans %= MOD;
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int k;
  cin >> s >> k;
  if (k == 0) {
    cout << 1;
    return 0;
  }
  if (k == 1) {
    cout << s.size() - 1;
    return 0;
  }
  int dp[1005];
  dp[1] = 0;
  for (int i = 2; i <= 1000; i++) dp[i] = dp[__builtin_popcount(i)] + 1;
  preprocess();
  long long res = 0;
  for (int i = 2; i <= s.size(); i++) {
    if (dp[i] == k - 1) {
      res += solve(i, 0) % MOD;
      res %= MOD;
    }
  }
  cout << res;
}
