#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const long long MOD = 1e9 + 7;
long long C[1001][1001];
long long cnt[1001];
void pre() {
  C[0][0] = 1;
  C[1][0] = C[1][1] = 1;
  for (int i = 2; i < 1001; i++) {
    C[i][0] = 1;
    for (int j = 1; j < 1001; j++)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
}
int k;
char str[1005];
int main() {
  scanf("%s%d", str, &k);
  pre();
  int n = strlen(str);
  int pre = 0;
  for (int i = 0; i < n; i++) {
    if (str[i] == '0') continue;
    int len = n - i - 1;
    for (int j = 0; j <= len; j++)
      cnt[j + pre] = (cnt[j + pre] + C[len][j]) % MOD;
    pre++;
  }
  cnt[pre] = (cnt[pre] + 1) % MOD;
  if (k == 0) {
    puts("1");
    exit(0);
  } else if (k == 1) {
    cout << cnt[1] - 1 << endl;
    exit(0);
  }
  k--;
  long long ans = 0;
  for (int i = 2; i <= 1000; i++) {
    int v = i, t;
    for (t = 1; t <= k; t++) {
      v = __builtin_popcount(v);
      if (v == 1) break;
    }
    if (t == k && v == 1) {
      ans = (ans + cnt[i]) % MOD;
    }
  }
  cout << ans << endl;
}
