#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int f[1234], num[1010];
long long dp[1010][1010];
void init() {
  f[0] = -233;
  f[1] = 0;
  for (int i = 2; i <= 1000; i++) {
    int tx = i, k = 0;
    while (tx) {
      if (tx & 1) k++;
      tx /= 2;
    }
    f[i] = f[k] + 1;
  }
}
long long dfs(int cur, int state, bool fp, int k) {
  if (cur < 0) return (f[state] == k - 1);
  if (!fp && dp[cur][state] != -1) return dp[cur][state];
  int fpmax = fp ? num[cur] : 1;
  long long ret = 0;
  for (int i = 0; i <= fpmax; i++)
    ret += dfs(cur - 1, state + (i == 1), fp && i == fpmax, k), ret %= mod;
  if (!fp) dp[cur][state] = ret;
  return ret;
}
int t;
char s[1010];
int main() {
  scanf("%s", s);
  scanf("%d", &t);
  if (t == 0)
    puts("1");
  else {
    int len = strlen(s);
    init();
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < len; i++) num[len - 1 - i] = s[i] - '0';
    if (t != 1)
      cout << dfs(len - 1, 0, 1, t);
    else
      cout << dfs(len - 1, 0, 1, t) - 1;
    return 0;
  }
  return 0;
}
