def h(i,S,X,N):
    e=0
    for j in range(i+1,int(X**1/N)+1):
        if S+j**N<X:
            e=e+h(j,S+j**N,X,N)
        elif S+j**N==X:
            e+=1
        else:
            continue
    return e



def powerSum(X, N):
    a=0
    for i in range(1,int(X**1/N)+1):
        S=i**N
        if S < X:
            a += h(i, S, X, N)
        elif S == X:
            a += 1
    return a