def multiply(x, y, k):
    """multiply two integers x and y, where k >= 0 is a power of 2,
        and k is at least as large as the maximum number of bits in x or y"""
       
    if k == 1:
        return x * y
    
    k_over_two = k // 2 
        
    two_to_the_k_over_two = 1 << k_over_two # a single k-bit right shift

    xL, xR = x // two_to_the_k_over_two, x % two_to_the_k_over_two
    yL, yR = y // two_to_the_k_over_two, y % two_to_the_k_over_two
    # note that these two operations could be done by bit shifts and masking.
    
    p1 = multiply (xL, yL, k_over_two)
    p2 = multiply (xL, yR, k_over_two)
    p3 = multiply (xR, yL, k_over_two) 
    p4 = multiply (xR, yR, k_over_two)
    
    return (p1 << k) + ((p2 + p3) << k_over_two) + p4
    
print (multiply(3000, 40000, 16))