#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
char a[N];
const int mod = 1e9 + 7;
long long C[N][N];
void init2() {
  for (int i = 0; i < N; i++) {
    C[i][0] = 1;
    C[i][i] = 1;
  }
  for (int i = 1; i < N; i++) {
    for (int j = 1; j < i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
}
int dat[N][N];
int main() {
  while (scanf("%s", a + 1) != EOF) {
    init2();
    int len = strlen(a + 1);
    for (int i = 1; i <= 1000; i++) dat[i][0] = 0;
    for (int i = 2; i <= len; i++) {
      int sum = 0, x = i, cnt = 1;
      while (x != 1) {
        cnt++;
        sum = 0;
        while (x) {
          if (x & 1) sum++;
          x /= 2;
        }
        x = sum;
      }
      dat[cnt][++dat[cnt][0]] = i;
    }
    int n;
    scanf("%d", &n);
    if (n == 0) {
      printf("1\n");
      return 0;
    }
    if (n == 1) {
      printf("%d\n", len - 1);
      return 0;
    }
    if (!dat[n][0]) {
      printf("0\n");
    } else {
      int ans = 0;
      int cnt = 0;
      for (int i = 1; i <= len; i++) {
        if (a[i] == '1') {
          for (int j = 1; j <= dat[n][0]; j++) {
            ans += C[len - i][dat[n][j] - cnt];
            ans %= mod;
          }
          cnt++;
        }
      }
      for (int i = 1; i <= dat[n][0]; i++)
        if (dat[n][i] == cnt) ans++;
      ans %= mod;
      printf("%d\n", ans);
    }
  }
}
