#include <bits/stdc++.h>
using namespace std;
string inp;
int dp[1001][1001][2];
int get(int pos, int rem, bool prefix) {
  if (pos == inp.size()) return rem == 0;
  if (rem < 0) return 0;
  int &ans = dp[pos][rem][prefix];
  if (ans == -1) {
    if (prefix) {
      if (inp[pos] == '0')
        ans = get(pos + 1, rem, true);
      else {
        ans = get(pos + 1, rem - 1, true);
        ans = (ans + get(pos + 1, rem, false)) % 1000000007;
      }
    } else {
      ans = (get(pos + 1, rem - 1, false) + get(pos + 1, rem, false)) %
            1000000007;
    }
  }
  return ans;
}
int dis[1001], k;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  memset(dp, -1, sizeof dp);
  dis[1] = 0;
  for (int i = 2; i <= 1000; i++) {
    dis[i] = dis[__builtin_popcount(i)] + 1;
  }
  cin >> inp >> k;
  int ans = 0;
  for (int i = 1; i <= 1000; i++) {
    if (dis[i] == k - 1) {
      ans = (ans + get(0, i, true)) % 1000000007;
    }
  }
  if (k == 1) ans--;
  if (k == 0) ans = 1;
  cout << ans << endl;
}
