#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
const long long MOD = 1000000007;
const int N = 1e3 + 60;
string s;
int k;
int dp[100001];
int qtd_1 = 0;
long long comb[N][N];
long long suff[N];
long long ans;
int main() {
  cin >> s >> k;
  dp[0] = 0;
  dp[1] = 1;
  if (k == 0) {
    puts("1");
    return 0;
  }
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '1') qtd_1++;
  }
  for (int i = 2; i <= 10001; i++) {
    dp[i] = 1 + dp[__builtin_popcount(i)];
  }
  for (int i = 0; i < N; i++) {
    comb[i][0] = 1;
    comb[i][i] = 1;
    for (int j = 1; j < i; j++) {
      comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
      comb[i][j] %= MOD;
    }
  }
  for (int i = 1; i <= s.size(); i++) {
    if (dp[i] == k) {
      ans += comb[s.size()][i];
      ans -= comb[s.size() - 1][i - 1];
      int sum = 1;
      int qt = i - 1;
      for (int j = 1; j < s.size(); j++) {
        if (qt <= 0) break;
        if (s[j] == '1') {
          ans += comb[s.size() - j][qt];
          if (ans > MOD) ans -= MOD;
          if (qt - 1) {
            ans -= comb[s.size() - j - 1][qt - 1];
            if (ans < 0) ans += MOD;
          }
          ans %= MOD;
          qt--;
        }
      }
    }
  }
  printf("%lld\n", ans % MOD);
  return 0;
}
