Untitled

MOD = 10**9 + 7

def count_set_bits(x):
    return bin(x).count('1')

def Decryptions(N, K):
    limit = int(N, 2)
    
    if K == 0:
        return 1 if limit >= 0 else 0
    
    max_value = limit + 1
    dp = [[0] * (K + 1) for _ in range(max_value)]
    
    dp[0][0] = 1  # Initialize starting condition
    
    for steps in range(K):
        for num in range(max_value):
            if dp[num][steps]:
                next_num = count_set_bits(num)
                if next_num < max_value:
                    dp[next_num][steps + 1] += dp[num][steps]
                    dp[next_num][steps + 1] %= MOD
    
    count = 0
    for num in range(limit + 1):
        count += dp[num][K]
        count %= MOD
    
    return count

# Get user inputs
N = input("Enter a binary string: ")
K = int(input("Enter the number of steps: "))

# Print the result
print("Result:", Decryptions(N, K))