Recursion Power Sum

def powerSum(X, N, num=1):
power = num ** N

if power > X:
    return 0  # too big, can't continue
elif power == X:
    return 1  # exact match found
else:
    # either include this number or skip it
    return powerSum(X - power, N, num + 1) + powerSum(X, N, num + 1)