#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN][2];
int Steps[MAXN];
int add(int a, int b) { return ((a + b) >= MOD ? a + b - MOD : a + b); }
void PreproccessSteps() {
  Steps[1] = 1;
  for (int i = (2); i < (1010); i++)
    Steps[i] = Steps[__builtin_popcount(i)] + 1;
}
int Ones(int N, string s) {
  int cnt = 0;
  for (int i = (1); i < (N); i++)
    if (s[i] == '1') cnt++;
  return cnt;
}
void FillDP(int N, string s) {
  for (int j = (0); j < (N + 1); j++) dp[0][j][0] = dp[0][j][1] = 1;
  for (int i = (1); i < (N + 1); i++)
    for (int j = (1); j < (N + 1); j++) {
      if (s[j - 1] == '1')
        dp[i][j][0] = add(dp[i - 1][j - 1][0], dp[i][j - 1][1]);
      if (s[j - 1] == '0') dp[i][j][0] = dp[i][j - 1][0];
      dp[i][j][1] = add(dp[i - 1][j - 1][1], dp[i][j - 1][1]);
    }
}
int main() {
  int N, k, sum = 0;
  string s;
  cin >> s >> k;
  reverse(s.begin(), s.end());
  PreproccessSteps();
  N = (int)s.size();
  FillDP(N, s);
  for (int i = (1); i < (N + 1); i++)
    if (Steps[i] == k) sum = add(sum, dp[i][N][0]);
  if (k == 1) {
    cout << dp[1][N][0] - 1;
    return 0;
  }
  if (!k) sum++;
  cout << sum;
  return 0;
}
