#include <bits/stdc++.h>
using namespace std;
const long long MXN = 1e3 + 10;
const long long MXM = 5e2 + 10;
const long long MX5 = 2e5 + 10;
const long long MX6 = 1e6 + 10;
const long long LOG = 20;
const long long INF = 8e18;
const double eps = 1e-9;
const long long MOD = 1e9 + 7;
long long power(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * power(a * a % md, b / 2, md) % md
                      : power(a * a % md, b / 2, md) % md));
}
long long bmm(long long a, long long b) {
  return (a % b == 0 ? b : bmm(b, a % b));
}
string base2(long long n) {
  string a = "";
  while (n >= 2) {
    a += (char)(n % 2 + '0');
    n /= 2;
  }
  a += (char)(n + '0');
  ;
  return a;
}
long long k, ans;
long long C[MXN][MXN], dp[MXN][MXN];
string s;
void init() {
  for (int i = 0; i < MXN; i++) {
    for (int j = 0; j <= i; j++) {
      if (j == 0 || i == j) {
        C[i][j] = 1;
      } else {
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
      }
    }
  }
  return;
}
long long Modify(long long x) {
  string second = base2(x);
  long long cnt = 0;
  for (int i = 0; i < second.size(); i++) {
    if (second[i] == '1') cnt++;
  }
  return cnt;
}
int main() {
  init();
  cin >> s >> k;
  reverse((s).begin(), (s).end());
  if (s[0] == '1') {
    dp[0][1] = 1;
  }
  dp[0][0] = 1;
  for (int i = 1; i < s.size(); i++) {
    dp[i][0] = 1;
    if (s[i] == '0') {
      for (int j = 1; j <= i + 1; j++) {
        dp[i][j] = dp[i - 1][j];
      }
    } else {
      for (int j = 1; j <= i + 1; j++) {
        dp[i][j] = (dp[i - 1][j - 1] + C[i][j]) % MOD;
      }
    }
  }
  for (int i = 1; i <= s.size(); i++) {
    long long cost = 1, Now = i;
    while (Now != 1) {
      Now = Modify(Now);
      cost++;
    }
    if (cost == k) {
      ans = (ans + dp[s.size() - 1][i]) % MOD;
    }
  }
  cout << (k == 0 ? 1 : ans - (k == 1));
  return 0;
}
