#include <bits/stdc++.h>
using namespace std;
int k;
string s;
long long dp[1010][1010][5];
long long check(long long sum) {
  if (sum == 1) return 0;
  if (sum == 0)
    return -34;
  else {
    long long num = 1;
    while (sum != 1) {
      num += sum % 2;
      sum /= 2;
    }
    return 1 + check(num);
  }
}
long long solve(long long sum, int x, int b, int ll1) {
  long long &res = dp[sum][x][b];
  if (x == s.size()) {
    if (sum == 1) {
      if (ll1 == x - 1) {
        return (0 == k);
      }
    }
  }
  if (res != -1) return res;
  if (x == s.size()) {
    return res = (check(sum) == k - 1);
  }
  if (b == 0) {
    if (s[x] == '0') {
      return res = solve(sum, x + 1, 0, ll1);
    } else {
      return res = (solve(sum + 1, x + 1, 0, x) + solve(sum, x + 1, 1, ll1)) %
                   1000000007;
    }
  } else {
    return res = (solve(sum + 1, x + 1, 1, x) + solve(sum, x + 1, 1, ll1)) %
                 1000000007;
  }
}
int main() {
  memset(dp, -1, sizeof dp);
  cin >> s;
  cin >> k;
  cout << solve(0, 0, 0, 0) << endl;
  return 0;
}
