特殊二进制数 - 代码源竞赛平台

题目描述

蜗蜗在研究一种整数操作。对于一个正整数 $x$，一次操作会将它替换为其二进制表示中数字 $1$ 的个数。

蜗蜗会不断执行这一操作，直到整数第一次变成 $1$，并立即停止。如果一个整数恰好需要执行 $k$ 次操作，就称它为特殊数。整数 $1$ 本身需要执行 $0$ 次操作。

给定一个用二进制表示的正整数 $N$，请你求出 $1$ 到 $N$ 中有多少个特殊数，答案对 $10^9+7$ 取模。

输入格式

第一行包含一个不含前导零的二进制字符串，表示正整数 $N$。

第二行包含一个整数 $k$，表示要求的操作次数。

输出格式

输出一行一个整数，表示不超过 $N$ 的特殊正整数数量对 $10^9+7$ 取模的结果。

样例

101
1

2

样例解释

二进制数 $101$ 对应的十进制数为 $5$。

在 $1$ 到 $5$ 中，$2$ 和 $4$ 的二进制表示分别为 $10$ 和 $100$，它们都恰好经过一次操作变成 $1$。整数 $1$ 本身需要 $0$ 次操作，因此不计入答案。

数据范围

对于 100% 的数据，保证 $1\le N<2^{1000}$，$0\le k\le 1000$。

$N$ 的二进制表示长度为 $1$ 到 $1000$，且不含前导零。