CF914C Travelling Salesman and Special Numbers

旅行推销员常常长时间旅行，因此他往往会觉得无聊。为了打发时间，他喜欢对数字进行一些操作。其中一个操作是，对一个正整数 $x$，将其变为 $x$ 的二进制表示中 $1$ 的个数。例如，对于数字 $13$，有 $13_{10}=1101_{2}$，所以它有 $3$ 个 $1$，$13$ 在一次操作后会变成 $3$。 他称一个数为特殊数，如果将其经过最少若干次上述操作后变为 $1$，所需操作次数恰好为 $k$。 他想知道，不超过 $n$ 的特殊数有多少个。请帮助旅行推销员，因为他即将到达目的地了！ 由于答案可能很大，请将答案对 $10^9+7$ 取模。

第一行包含整数 $n$（$1 \leq n < 2^{1000}$）。 第二行包含整数 $k$（$0 \leq k \leq 1000$）。 注意，$n$ 以二进制形式输入，且没有前导零。

输出一个整数，表示不超过 $n$ 的特殊数的数量，答案需对 $10^9+7$ 取模。

在第一个样例中，三个特殊数分别是 $3$、$5$ 和 $6$。这三个数经过一次操作都变成 $2$（因为 $3$、$5$ 和 $6$ 的二进制中都有两个 $1$），第二次操作变成 $1$（因为 $2$ 的二进制中只有一个 $1$）。 由 ChatGPT 5 翻译