#include <bits/stdc++.h>
using namespace std;
const int max_N = 1000 + 10;
const long long mod = 1e9 + 7;
long long c[max_N][max_N], dp[max_N], ans;
int main() {
  ios::sync_with_stdio(false);
  int k;
  string b;
  cin >> b >> k;
  dp[0] = -10;
  for (int i = 2; i <= 1000; i++) {
    int t = __builtin_popcount(i);
    dp[i] = dp[t] + 1;
  }
  int sz = (int)b.size(), cnt(0);
  c[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
  }
  for (int i = 0; i < sz; i++) {
    if (b[i] == '0') continue;
    for (int j = 0; j < sz - i; j++) {
      if (dp[j + cnt] == k - 1) {
        ans += c[sz - i - 1][j];
        ans %= mod;
      }
    }
    cnt++;
  }
  if (dp[cnt] == k - 1) ans = (ans + 1) % mod;
  if (!k) ans = 1;
  if (k == 1) ans = sz - 1;
  cout << (long long)ans << endl;
  return 0;
}
