#include <bits/stdc++.h>
const int MOD = 1000000007;
int Count(int i) {
  int ret = 0;
  while (i) {
    ++ret;
    i -= i & (-i);
  }
  return ret;
}
int CNT[1100];
char In[2100];
int L, K;
int DPN[1100][2][1100];
void Input() {
  scanf("%s", In + 1);
  L = strlen(In + 1);
  scanf("%d", &K);
  int wi;
  for (wi = 2; wi <= 1000; ++wi) CNT[wi] = CNT[Count(wi)] + 1;
}
void MADD(int& a, int b) { a = (a + b) % MOD; }
void DPA() {
  int wi, wia, wib;
  DPN[L][0][0] = DPN[L][0][1] = 1;
  DPN[L][1][0] = 1;
  DPN[L][1][1] = (In[L] == '1');
  for (wi = L - 1; wi; --wi)
    for (wia = 0; wia <= 1000; ++wia) {
      MADD(DPN[wi][0][wia], DPN[wi + 1][0][wia]);
      if (wia) MADD(DPN[wi][0][wia], DPN[wi + 1][0][wia - 1]);
      if (In[wi] == '1') {
        DPN[wi][1][wia] = DPN[wi + 1][0][wia];
        if (wia) MADD(DPN[wi][1][wia], DPN[wi + 1][1][wia - 1]);
      } else
        DPN[wi][1][wia] = DPN[wi + 1][1][wia];
    }
}
int main() {
  Input();
  if (!K) {
    puts("1");
    return 0;
  }
  DPA();
  int wk;
  int Ans = 0;
  for (wk = 1; wk <= 1000; ++wk)
    if (CNT[wk] + 1 == K) MADD(Ans, DPN[1][1][wk]);
  if (K == 1) Ans = (Ans - 1 + MOD) % MOD;
  printf("%d\n", Ans);
  return 0;
}
