#include <bits/stdc++.h>
using namespace std;
namespace {
using Integer = long long;
template <class T, class S>
istream& operator>>(istream& is, pair<T, S>& p) {
  return is >> p.first >> p.second;
}
template <class T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (T& val : vec) is >> val;
  return is;
}
template <class T>
istream& operator,(istream& is, T& val) {
  return is >> val;
}
template <class T, class S>
ostream& operator<<(ostream& os, const pair<T, S>& p) {
  return os << p.first << " " << p.second;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  for (size_t i = 0; i < vec.size(); i++)
    os << vec[i] << (i == vec.size() - 1 ? "" : " ");
  return os;
}
template <class T>
ostream& operator,(ostream& os, const T& val) {
  return os << " " << val;
}
template <class H>
void print(const H& head) {
  cout << head;
}
template <class H, class... T>
void print(const H& head, const T&... tail) {
  cout << head << " ";
  print(tail...);
}
template <class... T>
void println(const T&... values) {
  print(values...);
  cout << endl;
}
template <class H>
void eprint(const H& head) {
  cerr << head;
}
template <class H, class... T>
void eprint(const H& head, const T&... tail) {
  cerr << head << " ";
  eprint(tail...);
}
template <class... T>
void eprintln(const T&... values) {
  eprint(values...);
  cerr << endl;
}
class range {
  Integer start_, end_, step_;

 public:
  struct range_iterator {
    Integer val, step_;
    range_iterator(Integer v, Integer step) : val(v), step_(step) {}
    Integer operator*() { return val; }
    void operator++() { val += step_; }
    bool operator!=(range_iterator& x) {
      return step_ > 0 ? val < x.val : val > x.val;
    }
  };
  range(Integer len) : start_(0), end_(len), step_(1) {}
  range(Integer start, Integer end) : start_(start), end_(end), step_(1) {}
  range(Integer start, Integer end, Integer step)
      : start_(start), end_(end), step_(step) {}
  range_iterator begin() { return range_iterator(start_, step_); }
  range_iterator end() { return range_iterator(end_, step_); }
};
inline string operator"" _s(const char* str, size_t size) {
  return move(string(str));
}
constexpr Integer my_pow(Integer x, Integer k, Integer z = 1) {
  return k == 0    ? z
         : k == 1  ? z * x
         : (k & 1) ? my_pow(x * x, k >> 1, z * x)
                   : my_pow(x * x, k >> 1, z);
}
constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z = 1) {
  return k == 0    ? z % M
         : k == 1  ? z * x % M
         : (k & 1) ? my_pow_mod(x * x % M, k >> 1, M, z * x % M)
                   : my_pow_mod(x * x % M, k >> 1, M, z);
}
constexpr unsigned long long operator"" _ten(unsigned long long value) {
  return my_pow(10, value);
}
inline int k_bit(Integer x, int k) { return (x >> k) & 1; }
mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(
               chrono::steady_clock::now().time_since_epoch())
               .count());
template <class T>
string join(const vector<T>& v, const string& sep) {
  stringstream ss;
  for (size_t i = 0; i < v.size(); i++) {
    if (i > 0) ss << sep;
    ss << v[i];
  }
  return ss.str();
}
inline string operator*(string s, int k) {
  string ret;
  while (k) {
    if (k & 1) ret += s;
    s += s;
    k >>= 1;
  }
  return ret;
}
}  // namespace
constexpr long long mod = 9_ten + 7;
long long check(string s, int k) {
  long long val = 0;
  for (int i = 0; i < s.size(); i++) {
    val = val * 2 + s[i] - '0';
  }
  long long ans = 0;
  for (int i = 1; i <= val; i++) {
    int tmp = i;
    int d = 0;
    while (tmp != 1) {
      tmp = __builtin_popcount(tmp);
      d++;
    }
    if (d == k) {
      ans++;
    }
  }
  return ans;
}
int main() {
  string s;
  cin >> s;
  int w;
  cin >> w;
  int n = s.size();
  vector<int> d(1001, -1);
  d[1] = 0;
  for (int i = 2; i <= 1000; i++) {
    int j = __builtin_popcount(i);
    d[i] = d[j] + 1;
  }
  vector<vector<long long>> dp(2, vector<long long>(n + 1, 0));
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    vector<vector<long long>> dp_(2, vector<long long>(n + 1, 0));
    int b = s[i] - '0';
    for (int k = 0; k < 2; k++) {
      for (int j = 0; j <= n; j++) {
        if (dp[k][j] == 0) continue;
        for (int x = 0; x <= 1; x++) {
          int j_ = j + x;
          int k_ = k | (b > x);
          if (k == 0 && b < x) continue;
          (dp_[k_][j_] += dp[k][j]) %= mod;
        }
      }
    }
    swap(dp, dp_);
  }
  long long ans = 0;
  if (w != 0) {
    for (int i = 0; i <= n; i++) {
      if (d[i] != w - 1) continue;
      for (int k = 0; k <= 1; k++) {
        (ans += dp[k][i]) %= mod;
      }
    }
    if (w == 1) {
      (ans += mod - 1) %= mod;
    }
  } else {
    ans = 1;
  }
  println(ans);
  return 0;
}
