#include <bits/stdc++.h>
using namespace std;
string s;
map<int, int> dp;
int k;
int n;
int dp1[1001][1001][2];
int go(int t) {
  if (t == 1) return 0;
  int cnt = 0;
  while (t) {
    cnt += (t % 2);
    t /= 2;
  }
  return go(cnt) + 1;
}
int solve(int i, int pre, int q) {
  if (i >= n) {
    return dp[pre] == k;
  }
  if (dp1[i][pre][q] != -1) return dp1[i][pre][q];
  if (q) {
    return dp1[i][pre][1] =
               ((solve(i + 1, pre + 1, 1) % (long long)1000000007) +
                (solve(i + 1, pre, 1) % (long long)1000000007)) %
               (long long)1000000007;
  }
  if (s[i] == '1') {
    return dp1[i][pre][0] =
               ((solve(i + 1, pre + 1, 0) % (long long)1000000007) +
                (solve(i + 1, pre, 1) % (long long)1000000007)) %
               (long long)1000000007;
  }
  return dp1[i][pre][0] = solve(i + 1, pre, 0) % (long long)1000000007;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s >> k;
  n = s.size();
  memset(dp1, -1, sizeof(dp1));
  dp[1] = 1;
  dp[0] = 0;
  for (int i = 2; i <= 1000; i++) {
    dp[i] = go(i) + 1;
  }
  cout << solve(0, 0, 0) - (k == 1 ? 1 : 0);
  return 0;
}
