#include <bits/stdc++.h>
using namespace std;
void fun() {}
long long int __gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return __gcd(b, a % b);
}
long long int memo[1002];
string s;
long long int k;
long long int len;
long long int dp[1001][2][1001];
long long int md = 1e9 + 7;
void precalc() {
  memo[0] = -4;
  memo[1] = 0;
  for (long long int i = 2; i <= 1001; i++) {
    long long int count = 0;
    long long int num = i;
    while (num) {
      if (num & 1) count++;
      num >>= 1;
    }
    memo[i] = memo[count] + 1;
    memo[i] %= md;
  }
}
long long int solve(long long int idx, long long int flag,
                    long long int count) {
  if (idx >= len) {
    if (k == memo[count] + 1) {
      return 1;
    } else
      return 0;
  }
  if (dp[idx][flag][count] != -1) {
    return dp[idx][flag][count];
  }
  long long int ans = 0;
  ans += solve(idx + 1, flag | ('0' < s[idx]), count);
  ans %= md;
  if (flag == 1 || s[idx] == '1') ans += solve(idx + 1, flag, count + 1);
  ans %= md;
  dp[idx][flag][count] = ans;
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  fun();
  memset(dp, -1, sizeof(dp));
  cin >> s;
  len = s.length();
  cin >> k;
  if (k == 0) {
    cout << 1 << "\n";
    return 0;
  }
  precalc();
  long long int ans = solve(0, 0, 0);
  if (k == 1) {
    ans--;
    ans += md;
    ans %= md;
  }
  cout << ans << "\n";
  return 0;
}
