## The Power Sum

Find the number of ways that a given integer, X, can be expressed as sum of the Nth powers of unique, natural numbers.

Input format:
The first line contains an integer X
The second line contains an integer N

Constraints:
1 <= X <= 1000
2 <= N <= 10

Output format:
Output a single integer, the answer to the problem explained above.

Sample Input 0

```10
2
```

Sample Output 0

```1
```

Explanation 0

If X = 10 and N = 2, we need to find the number of ways that 10 can be represented as the sum of squares of unique numbers.
10 = 1^2 + 3^2
This is the only way in which 10 can be expressed as the sum of unique square.

Sample Input 1

```100
2```

Sample Output 1

`3`

Explanation 1

100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2

Sample Input 2

```100
3```

Sample Output 2

`1`

Explanation 2

100 can be expressed as the sum of the cubes of 1,2,3,4.
(1 + 8 + 27 + 64) = 100. There is no other way to express 100 as the sum of cubes.

Approach 1:
With X = 10, and N = 2, this approach will generate sequences like:

[1, 4]
[1, 4, 9]
[1, 9]

[4, 9]

[9, 4]
and you can easily spot out the problem of this approach is it produces duplicated sequences. Here is the code:
```def powerSum1(X, N):
max_base = int(math.sqrt(X))
sequence = list()
ways = set()
base = 1
_recursive_sum1(X, N, base, max_base, sequence, ways)
return len(ways)

def _recursive_sum1(X, N, base, max_base, sequence, ways):
if sum(sequence) == X:
# if set(sequence) not in ways:
return False
elif sum(sequence) > X:
return False
else:
for i in range(base, max_base+1):
tmp_val = i**N
if tmp_val not in sequence:
sequence.append(tmp_val)
print(sequence)
if _recursive_sum1(X, N, base+1, max_base, sequence, ways):
return True
sequence.pop()
return False
```
If you remove the comment from the if statement, indent 1 tab to the right for the line above, it will work perfectly, but only for all possible small-enough numbers. Because it generates on possible sequences, sequences that are subsequently increment.
Approach 2:
This recursion type generate non-repeated sequences that are subsequently increment.
1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 6]
[1, 2, 3, 4, 7]
[1, 2, 3, 4, 8]
[1, 2, 3, 5]
[1, 2, 3, 5, 6]
[1, 2, 3, 5, 7]
[1, 2, 3, 6]
[1, 2, 3, 6, 7]
[1, 2, 3, 7]
[1, 2, 3, 8]
[1, 2, 3, 9]
[1, 2, 4]
```def powerSum(X, N):
sequence = list()
base = 1
look_up = *(101)
for i in range(1, 101):
look_up[i] = i**N
cur_sum = 0
ways = _recursive_sum(X, N, base, look_up, cur_sum, sequence)
return ways

def _recursive_sum(X, N, base, look_up, cur_sum, seq):
ways = 0
tmp_val = look_up[base]

while cur_sum + tmp_val < X:
seq.append(base)
print(seq)
ways += _recursive_sum(X, N, base+1, look_up, cur_sum+tmp_val, seq)
seq.pop()
base += 1
tmp_val = look_up[base]

if cur_sum + tmp_val == X:
ways += 1
seq.append(base)
seq.pop()
return ways
```