Untitled

def Decryptions(N: str, K: int) -> int:
    MOD = 10**9 + 7
    max_val = int(N, 2)
    steps_to_one = [-1] * (max_val + 1)
    
    from collections import deque
    
    def compute_steps_to_one():
        queue = deque([1])
        steps_to_one[1] = 0
        while queue:
            num = queue.popleft()
            steps = steps_to_one[num]
            next_num = bin(num).count('1')
            if next_num < len(steps_to_one) and steps_to_one[next_num] == -1:
                steps_to_one[next_num] = steps + 1
                queue.append(next_num)
    
    compute_steps_to_one()
    
    count = sum(1 for i in range(max_val + 1) if steps_to_one[i] == K) % MOD
    
    return count

N = input("Enter a binary string: ")
K = int(input("Enter the number of steps: "))
print(Decryptions(N, K))