给你一个 二进制 字符串 s，它表示数字 n 的二进制形式。

同时，另给你一个整数 k。

如果整数 x 可以通过最多 k 次下述操作约简到 1 ，则将整数 x 称为 k-可约简 整数：

• 将 x 替换为其二进制表示中的置位数（即值为 1 的位）。

例如，数字 6 的二进制表示是 "110"。一次操作后，它变为 2（因为 "110" 中有两个置位）。再对 2（二进制为 "10"）进行操作后，它变为 1（因为 "10" 中有一个置位）。

返回小于 n 的正整数中有多少个是 k-可约简 整数。

由于答案可能很大，返回结果需要对 109 + 7 取余。

二进制中的置位是指二进制表示中值为 1 的位。

示例 1：

示例 2：

示例 3：

提示：

• 1 <= s.length <= 800
• s 中没有前导零。
• s 仅由字符 '0' 和 '1' 组成。
• 1 <= k <= 5