#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e3 + 5, mod = 1e9 + 7;
int Get(int n) {
  if (n == 1) return 0;
  return Get(__builtin_popcount(n)) + 1;
}
int dp[mxN][mxN];
int dp2[mxN][mxN][2];
int main() {
  ios ::sync_with_stdio(false), cin.tie(nullptr);
  string n;
  int k;
  cin >> n >> k;
  if (!k) {
    cout << 1;
    return 0;
  }
  int len = n.size();
  int ans = 0;
  dp[1][1] = 1;
  for (int i = 2; i < len; ++i) {
    for (int j = 1; j < i; ++j) {
      dp[i][j + 1] += dp[i - 1][j], dp[i][j + 1] %= mod;
      dp[i][j] += dp[i - 1][j], dp[i][j] %= mod;
    }
  }
  for (int i = 1; i < len; ++i) {
    for (int j = 1; j <= i; ++j) {
      if (Get(j) + !(j == 1 && i == 1) == k) ans = (ans + dp[i][j]) % mod;
    }
  }
  dp2[1][1][1] = 1;
  for (int i = 2; i <= len; ++i) {
    for (int j = 1; j < i; ++j) {
      dp2[i][j + 1][0] += dp2[i - 1][j][0];
      dp2[i][j + 1][0] %= mod;
      if (n[i - 1] == '1') dp2[i][j + 1][1] += dp2[i - 1][j][1];
      dp2[i][j + 1][1] %= mod;
      dp2[i][j][0] += dp2[i - 1][j][0];
      dp2[i][j][0] %= mod;
      if (n[i - 1] != '0')
        dp2[i][j][0] += dp2[i - 1][j][1], dp2[i][j][0] %= mod;
      else
        dp2[i][j][1] += dp2[i - 1][j][1], dp2[i][j][1] %= mod;
    }
  }
  for (int j = 1; j <= len; ++j) {
    if (Get(j) + !(j == 1 && len == 1) == k) {
      ans = (ans + dp2[len][j][0]) % mod;
      ans = (ans + dp2[len][j][1]) % mod;
    }
  }
  cout << ans;
  return 0;
}
