Count K-Reducible Numbers Less Than N
You are given a binary string s representing a number n in its binary form.
You are also given an integer k.
An integer x is called k-reducible if performing the following operation at most k times reduces it to 1:
- Replace
xwith the count of set bits in its binary representation.
Return an integer denoting the number of positive integers less than n that are k-reducible.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1
Input
s = "111", k = 1Output
3n = 7, and the 1-reducible integers less than 7 are 1, 2, and 4.
Example 2
Input
s = "1000", k = 2Output
6n = 8, and the 2-reducible integers less than 8 are 1, 2, 3, 4, 5, and 6.
Constraints
- 1 <= s.length <= 800
- s has no leading zeros.
- s consists only of the characters '0' and '1'.
- 1 <= k <= 5