Count K-Reducible Numbers Less Than N

Description

You are given a binary string s representing a number n in binary form, and an integer k.

An integer x is called k-reducible if performing the following operation at most k times reduces it to 1:

- Replace x with the count of set bits in its binary representation.

For example, 6 in binary is "110". One operation reduces it to 2 (two set bits). A second operation reduces it to 1 (one set bit).

Return the count of positive integers less than n that are k-reducible.

Since the answer may be too large, return it modulo 109 + 7.

Code

class Solution:
    def countKReducibleNumbers(self, s: str, k: int) -> int: