#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
int n, k;
bool d[1001];
long long dp[1001][2][1001];
int cnt[10001];
long long DP(int i, bool f, int j) {
  if (i == n) return cnt[j] == k;
  if (dp[i][f][j] != -1) return dp[i][f][j];
  long long ret = 0;
  if (d[i] == 1)
    ret = (ret + DP(i + 1, f, j + 1)) % mod;
  else if (d[i] == 0 and f)
    ret = (ret + DP(i + 1, f, j + 1)) % mod;
  ret = (ret + DP(i + 1, f | (d[i] == 1), j)) % mod;
  return dp[i][f][j] = ret;
}
int main() {
  for (int i = 1; i <= 1000; i++) {
    cnt[i] = 1 + cnt[__builtin_popcount(i)];
  }
  string s;
  cin >> s;
  n = s.size();
  cin >> k;
  int i = 0;
  for (char c : s) d[i++] = c - '0';
  memset(dp, -1, sizeof dp);
  cout << DP(0, 0, 0) - (k == 1);
}
