Untitled

def Decryptions(N: str, K: int) -> int:
    MOD = 10**9 + 7
    max_val = int(N, 2)
    dp = [[0] * (K + 1) for _ in range(max_val + 1)]
    
    dp[1][0] = 1
    
    for i in range(1, max_val + 1):
        for j in range(K):
            next_num = bin(i).count('1')
            if next_num <= max_val:
                dp[next_num][j + 1] += dp[i][j]
                dp[next_num][j + 1] %= MOD
    
    count = sum(dp[i][K] for i in range(max_val + 1)) % MOD
    
    return count

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