Find the number of ways that a given integer, $\mbox{X}$, can be expressed as the sum of the $N^{\mbox{th}}$ powers of unique, natural numbers. 

For example, if $X=13$ and $N=2$, we have to find all combinations of unique squares adding up to $13$.  The only solution is  $2^2+3^2$.  

Function Description

Complete the powerSum function in the editor below.  It should return an integer that represents the number of possible combinations.  

powerSum has the following parameter(s):  

X: the integer to sum to  
N: the integer power to raise numbers to  

Input Format

The first line contains an integer $\mbox{X}$. 

The second line contains an integer $N$.  

Constraints

$1\leq X\leq1000$   
$2\leq N\leq10$  

Output Format

Output a single integer, the number of possible combinations caclulated.   

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 squares. 

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.

Difficulty: MEDIUM
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
(num1, num2) = (int(input()), int(input()))

def power_sum(num, count, total, pair_count):
	powered_num = num ** num2
	if powered_num == total:
		return pair_count + 1
	if powered_num < total:
		return power_sum(num + 1, count - 1, total - powered_num, pair_count) + power_sum(num + 1, count, total, pair_count)
	return pair_count
limit = num1 ** (1 / float(num2))
print(power_sum(1, limit, num1, 0))


import sys
X = int(input())
N = int(input())

def rec(X, N, start):
	count = 0
	for i in range(start, X):
		ans = X - i ** N
		if ans == 0:
			count += 1
		if ans > 0:
			count += rec(ans, N, i + 1)
		if ans < 0:
			continue
	return count
print(rec(X, N, 1))


(x, n) = (int(input()), int(input()))

def find_comb(nr, power, candidates):
	if nr < 0 or nr % 1 != 0:
		return 0
	if nr == 0:
		return 1
	combs = 0
	for i in range(len(candidates)):
		candidate = candidates[i]
		combs += find_comb(nr - candidate ** power, power, candidates[i + 1:])
	return combs
print(find_comb(x, n, range(int(x ** (1 / n)), 0, -1)))


import math

def mycomb(pnums, n, tgtnum):
	if n == 1:
		for ele in pnums:
			if ele > tgtnum:
				break
			yield (ele,)
	else:
		for (i, a) in enumerate(pnums):
			if a <= tgtnum:
				for com in mycomb(pnums[i + 1:], n - 1, tgtnum - a):
					yield ((a,) + com)

def npsum(x, n):
	assert 0 <= x <= 1000 and 2 <= n <= 10
	c = 0
	r = math.floor(x ** (1 / n))
	natpow = [b ** n for b in list(range(1, r + 1))]
	for nchosen in range(1, r + 1):
		for com in mycomb(natpow, nchosen, x):
			if sum(com) == x:
				c += 1
	return c
x = int(input())
n = int(input())
print(npsum(x, n))


from functools import lru_cache

@lru_cache(maxsize=None)
def recursion(x, n, idx):
	if x == 0:
		return 1
	if x < 0:
		return 0
	if idx == 0:
		return 0
	return recursion(x - idx ** n, n, idx - 1) + recursion(x, n, idx - 1)
x = int(input())
n = int(input())
print(recursion(x, n, int(x ** (1 / n) + 1)))


from collections import Counter, defaultdict
import heapq

def readInts():
	return map(int, input().strip().split())

def the_power_sum():
	(x,) = readInts()
	(n,) = readInts()
	tots = defaultdict(int)
	tots[0] = 1
	for i in range(1, x + 1):
		add_v = i ** n
		for (v, c) in list(tots.items()):
			v2 = v + add_v
			if v2 > x:
				continue
			tots[v2] += c
	print(tots[x])
the_power_sum()


def k(d, i):
	if d == 0:
		return 1
	s = 0
	j = i
	while not pow(j, n) > d:
		s += k(d - pow(j, n), j + 1)
		j += 1
	return s
x = int(input().strip())
n = int(input().strip())
print(k(x, 1))


from math import floor
X = int(input().strip())
N = int(input().strip())
from math import floor

def powerSum(x, n, profile=False):
	result = []
	accsum = 0
	keys = []
	for i in range(1, floor(x ** (1.0 / n)) + 1):
		key = i ** n
		accsum += key
		keys.append((key, accsum))
	expanded = []
	while len(keys) > 0:
		(key, remain) = keys.pop()
		for (i, combination) in enumerate(expanded):
			if key in combination:
				continue
			else:
				new_comb = combination + [key]
				if sum(new_comb) == x:
					result.append(new_comb)
				elif sum(new_comb) < x and sum(combination + [remain]) >= x:
					expanded.append(new_comb)
		if key == x:
			result.append(key)
		elif remain >= x:
			expanded.append([key])
	return len(result)
print(powerSum(X, N))


def solve(sum, power, start):
	if sum == 0:
		return 1
	elif sum < 0:
		return 0
	num = 0
	current = sum
	while current > 0:
		current = sum - pow(start, power)
		start = start + 1
		num += solve(current, power, start)
	return num
power_sum = int(input())
power = int(input())
print('{}'.format(solve(power_sum, power, 1)))


def solve(x, i):
	if x < 0:
		return 0
	if x == 0:
		return 1
	if i >= len(powers):
		return 0
	if mem[i][x] > -1:
		return mem[i][x]
	if powers[i] > x:
		mem[i][x] = 0
		return 0
	if powers[i] == x:
		mem[i][x] = 1
		return 1
	r = 0
	r += solve(x - powers[i], i + 1)
	r += solve(x, i + 1)
	mem[i][x] = r
	return r
x = int(input())
n = int(input())
l = int(x ** (1 / n)) + 1
powers = [i ** n for i in range(1, l)]
mem = [[-1 for _ in range(x + 1)] for i in range(l)]
res = solve(x, 0)
print(res)


def f(x, l):
	if x == 0:
		return 1
	if len(l) < 1:
		return 0
	c = 0
	for i in range(len(l)):
		r = x - l[i]
		if r < 0:
			return c
		c += f(r, l[i + 1:])
	return c
(x, n) = (int(input().strip()), int(input().strip()))
mx = int(x ** (1 / n)) + 1
l = []
for i in range(1, mx, 1):
	l.append(i ** n)
c = f(x, l)
print(c)


def power_ways(x, number, p):
	if x == 0:
		return 1
	if x < 0 or number == 0:
		return 0
	ways = power_ways(x, number - 1, p)
	remaining = x - number ** p
	next_number = int(remaining ** (1 / p))
	if next_number >= number:
		next_number = number - 1
	ways += power_ways(remaining, next_number, p)
	return ways

def power_sum(x, p):
	return power_ways(x, int(x ** (1 / p)), p)
x = int(input().strip())
n = int(input().strip())
print(power_sum(x, n))


num = input()
k = int(input())
lis = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]
n = len(lis)

def func(i=0, sum1=0):
	if sum1 == int(num):
		return 1
	if i >= n:
		return 0
	if sum1 > int(num):
		return 0
	else:
		x = func(i + 1, sum1 + lis[i] ** k) + func(i + 1, sum1)
	return x
s = func()
print(s)


x = int(input().strip())
n = int(input().strip())
powers = []
maxSquare = x ** (1 / n)
for i in range(1, int(maxSquare) + 1):
	powers.append(i ** n)

def paths(number, array, index, total):
	if total == number:
		return 1
	if index >= len(array):
		return 0
	if total + array[index] > number:
		return 0
	elif total + array[index] == number:
		return 1
	path1 = paths(number, array, index + 1, total)
	path2 = paths(number, array, index + 1, total + array[index])
	return path1 + path2
print(paths(x, powers, 0, 0))


X = int(input())
N = int(input())

def power_sums(x, n, used):
	(ii, count) = (max(used) + 1, 0)
	while ii ** n < x:
		count += power_sums(x - ii ** n, n, used.union([ii]))
		ii += 1
	if ii ** n == x:
		return count + 1
	else:
		return count
print(power_sums(X, N, set([0])))


def solve(n, p, u):
	if n == 0:
		return 1
	if n < 0:
		return 0
	s = 0
	for i in range(u, 0, -1):
		s += solve(n - i ** p, p, i - 1)
	return s
N = int(input())
P = int(input())
print(solve(N, P, int(N ** (1 / P))))


import sys
import math
(x, n) = [int(line.strip()) for line in sys.stdin.readlines()]

def possible_addends(x, n):
	return tuple((i ** n for i in range(math.floor(x ** (1 / n)), 0, -1)))

def how_many_sums(x, poss, result):
	if x == 0:
		return result + 1
	if poss == [] or x < 0:
		return result
	(head, *tail) = poss
	return how_many_sums(x, tail, result) + how_many_sums(x - head, tail, result)
print(how_many_sums(x, possible_addends(x, n), 0))


import sys
x = int(input().strip())
n = int(input().strip())

def fun(a, min):
	if a == 0:
		return 1
	if min ** n > a:
		return 0
	count = 0
	current = min
	while a - current ** n >= 0:
		count += fun(a - current ** n, current + 1)
		current += 1
	return count
print(fun(x, 1))


from math import ceil

def num_ways(num, pow, largest_factor):
	if largest_factor == None:
		largest_factor = int(ceil(num ** 1 / pow))
	if num == 0:
		return 1
	if num < 0 or largest_factor == 0:
		return 0
	ways = 0
	ways += num_ways(num - largest_factor ** pow, pow, largest_factor - 1)
	ways += num_ways(num, pow, largest_factor - 1)
	return ways
num = int(input())
pow = int(input())
print(num_ways(num, pow, None))


def natural(x, n, ub, n_tuple=(0,), n_sum=0):
	count = 0
	if n_sum == x:
		count += 1
	elif n_sum < x:
		lb = n_tuple[-1] + 1
		for i in range(lb, ub):
			count += natural(x, n, ub, n_tuple + (i,), n_sum + i ** n)
	return count
x = int(input())
n = int(input())
ub = round(x ** (1 / n)) + 1
count = natural(x, n, ub)
print(count)


import math
x = int(input())
n = int(input())
maxx = math.ceil(math.pow(x, 1.0 / n))

def get_s(items):
	sum = 0
	for k in items:
		sum += k ** n
	return sum

def explore(cur, items, winners, level=0):
	s = get_s(items)
	adding = cur ** n
	if s + adding == x:
		items.append(cur)
		winners.append(items)
		return items
	if s + adding > x:
		return items
	if len(items) > 50:
		return items
	items.append(cur)
	for i in range(cur + 1, maxx):
		explore(i, items.copy(), winners, level + 1)
	return winners
c = 0
for j in range(1, 1 + maxx):
	tot = explore(j, [], [])
	c += len(tot)
print(c)


import math

def ways(value, power, start=1):
	limit = value ** (1.0 / power)
	limit = int(math.ceil(limit)) + 1
	n_ways = 0
	for i in range(start, limit):
		new_value = value - i ** power
		if new_value == 0:
			n_ways += 1
			continue
		if new_value < 0:
			break
		n_ways += ways(new_value, power, i + 1)
	return n_ways
value = int(input().strip())
power = int(input().strip())
result = ways(value, power)
print(result)


import sys
x = int(sys.stdin.readline())
n = int(sys.stdin.readline())
nums = int(x ** (1 / n))
nums = [a ** n for a in range(1, nums + 1)]

def sum_squares(x, nums, partial=[]):
	count = 0
	s = sum(partial)
	if s == x:
		count += 1
	if s >= x:
		return count
	for i in range(len(nums)):
		n = nums[i]
		remaining = nums[i + 1:]
		count += sum_squares(x, remaining, partial + [n])
	return count
print(sum_squares(x, nums))


X = int(input())
N = int(input())

def num_sum(x, n):

	def num_sum_helper(x, n, s):
		p = s ** n
		if p == x:
			return 1
		elif p > x:
			return 0
		else:
			return num_sum_helper(x - p, n, s + 1) + num_sum_helper(x, n, s + 1)
	if x == 1:
		return 1
	else:
		return num_sum_helper(x, n, 1)
print(num_sum(X, N))


tot = 0

def powersum(total, current, power, sofar):
	if total == 0:
		a = sofar.pop()
		sofar.append(a + 1)
		return
	elif total <= 0:
		return
	newnum = current ** power
	if newnum > total:
		return
	powersum(total, current + 1, power, sofar)
	powersum(total - newnum, current + 1, power, sofar)
num = int(input())
power = int(input())
b = [0]
powersum(num, 0, power, b)
print(b[0] // 2)


X = int(input())
N = int(input())
powers = []
n = 1
while True:
	power = n ** N
	if power > X:
		break
	n += 1
	powers.append(power)

def pwCount(val, ix):
	count = 0
	if val == 0:
		count = 1
	elif val > 0 and ix < len(powers):
		count = pwCount(val, ix + 1)
		count += pwCount(val - powers[ix], ix + 1)
	return count
print(pwCount(X, 0))


import math
i = int(input())
j = int(input())
k = int(i ** (1 / float(j)))
list1 = [x ** j for x in range(1, k + 1)]
counter = 0

def subsets(a):
	if a == []:
		return [[]]
	x = subsets(a[1:])
	x = [X for X in x if sum(X) <= i]
	iter_list = x + [[a[0]] + b for b in x]
	return iter_list
returnList = subsets(list1)
for x in returnList:
	if sum(x) == i:
		counter += 1
print(counter)


from math import floor
cache = {}

def rec(x, m):
	if x == 0:
		return 1
	if m == 0:
		return 0
	if x not in cache:
		cache[x] = {}
	if m not in cache[x]:
		cache[x][m] = rec(x - pow(m, n), m - 1) + rec(x, m - 1)
	return cache[x][m]
x = int(input())
n = int(input())
print(rec(x, floor(pow(x, 1.0 / n))))


powerMemo = {}

def power(num, power):
	return num ** power
memo = {}

def find(num, total, currentNum):
	count = 0
	if total == num:
		return 1
	if total > num:
		return 0
	for i in range(currentNum, root):
		if i in memo:
			count += find(num, total + memo[i], i + 1)
		else:
			memo[i] = power(i, powe)
			count += find(num, total + memo[i], i + 1)
	return count
num = int(input())
powe = int(input())
root = num ** (1 / powe)
root = int(root) + 1
print(find(num, 0, 1))


def power_counter(X, N, BadSet, Start):
	if X == 0:
		return [BadSet]
	else:
		i = Start + 1
		Checker = 0
		Candidates = []
		while i ** N <= X:
			if i not in BadSet:
				Candidates.append([X - i ** N, BadSet + [i], i])
				Checker = 1
			i += 1
		if Checker == 0:
			return []
		else:
			newList = []
			for i in Candidates:
				newList += power_counter(i[0], N, i[1], i[2])
		return newList
X = int(input())
N = int(input())
lookup = [-1] * 1000
BadSet = []
print(len(power_counter(X, N, [], 0)))


number = int(input())
power = int(input())

def f(i, number):
	if number == 0:
		return 1
	k = 0
	while i ** power <= number:
		k += f(i + 1, number - i ** power)
		i += 1
	return k
print(f(1, number))


import math

def find_power_sum(list, i, nth_power, number):
	if i < 0:
		return 0
	if math.pow(list[i], nth_power) == number:
		return 1 + find_power_sum(list, i - 1, nth_power, number)
	elif math.pow(list[i], nth_power) < number:
		return find_power_sum(list, i - 1, nth_power, number - math.pow(list[i], nth_power)) + find_power_sum(list, i - 1, nth_power, number)
	else:
		return find_power_sum(list, i - 1, nth_power, number)
number = int(input())
nth_power = int(input())
index = 2
foo = True
while foo:
	if math.log(number, index) <= nth_power:
		foo = False
	else:
		index += 1
list = []
for i in range(1, index + 1):
	list.append(i)
count = 0
i = len(list) - 1
while i > 0:
	if math.pow(list[i], nth_power) == number:
		count += 1
	elif math.pow(list[i], nth_power) < number:
		count += find_power_sum(list, i - 1, nth_power, number - math.pow(list[i], nth_power))
	list.pop(i)
	i -= 1
print(count)


import sys

def f(x, n, i):
	if x == 0:
		return 1
	if i ** n > x:
		return 0
	return f(x, n, i + 1) + f(x - i ** n, n, i + 1)
x = int(input().strip())
n = int(input().strip())
print(f(x, n, 1))


import math

def find_power_sum(list, i, nth_power, number):
	if i < 0:
		return 0
	if math.pow(list[i], nth_power) == number:
		return 1 + find_power_sum(list, i - 1, nth_power, number)
	elif math.pow(list[i], nth_power) < number:
		return find_power_sum(list, i - 1, nth_power, number - math.pow(list[i], nth_power)) + find_power_sum(list, i - 1, nth_power, number)
	else:
		return find_power_sum(list, i - 1, nth_power, number)
number = int(input().strip())
nth_power = int(input().strip())
index = 2
foo = True
while foo:
	if math.log(number, index) <= nth_power:
		foo = False
	else:
		index += 1
list = []
for i in range(1, index + 1):
	list.append(i)
count = 0
i = len(list) - 1
while i > 0:
	if math.pow(list[i], nth_power) == number:
		count += 1
	elif math.pow(list[i], nth_power) < number:
		count += find_power_sum(list, i - 1, nth_power, number - math.pow(list[i], nth_power))
	list.pop(i)
	i -= 1
print(count)


X = int(input())
N = int(input())
pow_list = []
i = 1
while i ** N <= X:
	pow_list.append(i ** N)
	i += 1
M = len(pow_list) - 1

def power_sum(x, m):
	if x == 0:
		return 1
	if x < 0 or m == -1:
		return 0
	ret = 0
	for i in range(m + 1):
		ret += power_sum(x - pow_list[i], i - 1)
	return ret
print(power_sum(X, M))


n = int(input())
power = int(input())

def recursion(sum, maxInt, toPower):
	if sum == 0:
		return 1
	elif sum < 0 or (sum > 0 and maxInt == 0):
		return 0
	else:
		return recursion(sum - maxInt ** toPower, maxInt - 1, toPower) + recursion(sum, maxInt - 1, toPower)
print(recursion(n, int(n ** (1 / power)), power))


def count_sums(target_sum, power_list, index):
	if target_sum == 0:
		return 1
	elif target_sum < 0:
		return 0
	elif index == len(power_list):
		return 0
	count = 0
	count += count_sums(target_sum, power_list, index + 1)
	count += count_sums(target_sum - power_list[index], power_list, index + 1)
	return count
from math import ceil
number = int(input())
power = int(input())
root_of_target = ceil(number ** (1 / float(power))) + 1
nth_powers = list(map(lambda x: x ** power, range(1, root_of_target)))
combinations = count_sums(number, nth_powers, 0)
print(combinations)


def count_sums(target_sum, power_list, index):
	if target_sum == 0:
		return 1
	elif target_sum < 0:
		return 0
	elif index == len(power_list):
		return 0
	count = 0
	count += count_sums(target_sum, power_list, index + 1)
	count += count_sums(target_sum - power_list[index], power_list, index + 1)
	return count
from math import ceil
number = int(input())
power = int(input())
root_of_target = ceil(number ** (1 / float(power))) + 1
nth_powers = list(map(lambda x: x ** power, range(1, root_of_target)))
combinations = count_sums(number, nth_powers, 0)
print(combinations)


__author__ = 'sidwagz'
X = int(input())
n = int(input())
A = []
i = 1
while i ** n <= X:
	A += [i ** n]
	i += 1
k = len(A)

def foo(i, num, ct):
	if num == 0:
		return 1
	elif num < 0:
		return 0
	else:
		for j in range(i, k):
			t = foo(j + 1, num - A[j], ct)
			ct['ct'] += t
		return 0
ct = {'ct': 0}
foo(0, X, ct)
print(ct['ct'])


x = int(input())
n = int(input())

def solve(powers, index, rem):
	if rem == 0:
		return 1
	elif rem < 0 or index == len(powers):
		return 0
	x = solve(powers, index + 1, rem - powers[index])
	y = solve(powers, index + 1, rem)
	return x + y
powers = list((i ** n for i in range(1, int(x ** (1 / n)) + 1)))
print(solve(powers, 0, x))


import math
(n, power) = [int(input()) for _ in range(2)]

def possibilities(numbers, objective):
	result = 0
	while len(numbers) > 0:
		i = numbers.pop()
		if i == objective:
			result += 1
			continue
		if i < objective:
			result += possibilities(list(numbers), objective - i)
	return result
numbers = list()
for i in range(1, math.floor(n ** (1.0 / power)) + 1):
	numbers.append(i ** power)
print(possibilities(numbers, n))


from math import sqrt

def bt(x, n, i, s):
	if s == x:
		return 1
	elif s > x or i > sqrt(x):
		return 0
	else:
		return bt(x, n, i + 1, s + i ** n) + bt(x, n, i + 1, s)
x = int(input())
n = int(input())
print(bt(x, n, 1, 0))


import math
(X, N) = (int(input()), int(input()))

def count(x, larger_than):
	if x == 0:
		return 1
	return sum((count(x - i ** N, i) for i in range(larger_than + 1, math.ceil(math.pow(x + 1, 1 / N)))))
print(count(X, 0))


def recursion(value, exp, mx):
	if value < 0 or (value > 0 and mx == 0):
		return 0
	if value == 0:
		return 1
	return recursion(value - mx ** exp, exp, mx - 1) + recursion(value, exp, mx - 1)
X = int(input().strip())
N = int(input().strip())
mx = int(X ** (1 / N))
ZZ = recursion(X, N, mx)
print(ZZ)


import math

def recur(finish, pw, mx, ii):
	if finish == 0:
		return 1
	if ii > mx or finish < 0:
		return 0
	return recur(finish - ii ** pw, pw, mx, ii + 1) + recur(finish, pw, mx, ii + 1)
n = int(input())
s = int(input())
flr = math.floor(n ** (1 / s))
print(recur(n, s, flr, 1))


number = int(input().strip())
power = int(input().strip())

def count_sums(total, current, power, n=1):
	current += n ** power
	if current == total:
		return 1
	if current > total:
		return 0
	sums = 0
	for i in range(n, int(total ** (1 / power))):
		sums += count_sums(total, current, power, i + 1)
	return sums
sums = 0
for i in range(0, int(number ** (1 / power))):
	sums += count_sums(number, 0, power, i + 1)
print(sums)


def power_sum(n, x, upper_limit, i):
	if n == 0:
		return 1
	if i > upper_limit or n < 0:
		return 0
	b = i
	return power_sum(n - int(pow(b, x)), x, upper_limit, i + 1) + power_sum(n, x, upper_limit, i + 1)
(n, x) = [int(input()) for _ in range(2)]
print(power_sum(n, x, int(pow(n, 1 / x)), 1))


X = int(input())
N = int(input())
pow = [i ** N for i in range(35)]

def getCount(total, i):
	if total == X:
		return 1
	if i > len(pow):
		return 0
	if pow[i] > X or total > X:
		return 0
	return getCount(total, i + 1) + getCount(total + pow[i], i + 1)
total = getCount(0, 1)
print(total)


m = int(input())
N = int(input())

def findout(n, k):
	if n == 0:
		return 1
	elif k == 0:
		return 0
	else:
		temp = 0
		for i in range(1, k + 1):
			if n - i ** N >= 0:
				temp += findout(n - i ** N, i - 1)
		return temp
print(findout(m, m))


x = int(input())
n = int(input())

def ways(x, factor=1):
	if x < factor ** n:
		return 0
	elif x == factor ** n:
		return 1
	else:
		return ways(x, factor + 1) + ways(x - factor ** n, factor + 1)
print(ways(x))


def power_sum_ways(X, N):
	max_int = int(pow(X, 1 / N)) + 1
	ways = power_sum_ways_recurse(X, N, max_int, False)
	return ways

def power_sum_ways_recurse(X, N, i, recursed=True):
	if not recursed:
		pass
	if X > 0 and i == 0 or X < 0:
		return 0
	if X == 0:
		return 1
	return power_sum_ways_recurse(X, N, i - 1) + power_sum_ways_recurse(X - pow(i, N), N, i - 1)
X = int(input().strip())
N = int(input().strip())
print(power_sum_ways(X, N))


nums = [i + 1 for i in range(33)]

def N(x, n, nums):
	p = x - pow(nums[0], n)
	if p > 0:
		t = nums[1:]
		return N(p, n, t) + N(x, n, t)
	elif p == 0:
		return 1
	else:
		return 0
x = int(input())
n = int(input())
print(N(x, n, nums))


m = int(input())
N = int(input())

def findout(n, k):
	if n == 0:
		return 1
	elif k == 0:
		return 0
	else:
		temp = 0
		for i in range(1, k + 1):
			if n - i ** N >= 0:
				temp += findout(n - i ** N, i - 1)
		return temp
print(findout(m, m))


n = int(input())
c = int(input())
x = 1
l = []
while x ** c <= n:
	l += [x ** c]
	x += 1

def f(l, n, c, j, u):
	if n < 0:
		return c
	if n == 0:
		return c + 1
	if n == 0:
		return c + 1
	for i in range(j, len(l)):
		c = f(l, n - l[i], c, i + 1, u + [l[i]])
	return c
print(f(l, n, 0, 0, []))


def findout(n, k):
	if n == 0:
		return 1
	elif k == 0:
		return 0
	else:
		temp = 0
		for i in range(1, k + 1):
			if n - i ** N >= 0:
				temp += findout(n - i ** N, i - 1)
		return temp
m = int(input())
N = int(input())
print(findout(m, m))


def findout(n, k):
	if n == 0:
		return 1
	elif k == 0:
		return 0
	else:
		temp = 0
		for i in range(1, k + 1):
			val = n - compo[i]
			if val >= 0:
				temp += findout(val, i - 1)
			else:
				break
		return temp
m = int(input())
N = int(input())
compo = [0, 1]
for i in range(2, m):
	pwr = i ** N
	if pwr > m:
		break
	else:
		compo.append(pwr)
compo.append(pwr)
print(findout(m, m))


import math

def power_sum(number, exponent, minimum):
	number_ways = 0
	current = minimum
	exp_current = math.pow(current, exponent)
	while exp_current <= number:
		if exp_current == number:
			number_ways += 1
			break
		number_ways += power_sum(number - exp_current, exponent, current + 1)
		current += 1
		exp_current = math.pow(current, exponent)
	return number_ways
x = int(input())
n = int(input())
ways = power_sum(x, n, 1)
print(ways)


from math import *

def get(r, s, n):
	if s ** n > r:
		return 0
	c = get(r, s + 1, n)
	a = r - s ** n
	if a == 0:
		c += 1
	else:
		c += get(a, s + 1, n)
	return c
x = int(input())
n = int(input())
print(get(x, 1, n))


from math import sqrt

class Solution(object):

	def power_sum(self, X, N):
		E = int(sqrt(X))
		nums = list(range(1, E + 1))

		def __dfs(index, target, path, result):
			if target < 0:
				return
			if target == 0:
				result.append(path)
			for i in range(index, E):
				__dfs(i + 1, target - pow(nums[i], N), path + [nums[i]], result)
		result = []
		__dfs(0, X, [], result)
		return len(result)
X = int(input())
N = int(input())
solution = Solution()
x = solution.power_sum(X, N)
print(x)


import sys

def power_sum(sum, power, max_candidate_int=-99):
	if sum == 0:
		return 1
	elif sum < 0:
		return 0
	if max_candidate_int == -99:
		for candidate in range(1, sum + 1):
			if candidate ** power > sum:
				break
			else:
				max_candidate_int = candidate
	else:
		if max_candidate_int ** power > sum:
			return power_sum(sum, power, max_candidate_int - 1)
		if max_candidate_int < 0:
			return 0
	return power_sum(sum - max_candidate_int ** power, power, max_candidate_int - 1) + power_sum(sum, power, max_candidate_int - 1)
sum = int(input())
power = int(input())
print(power_sum(sum, power))


import math
x = int(input())
n = int(input())

def solver(a, b, x):
	if a == 0:
		return 1
	if a < 0:
		return 0
	solutions = 0
	for i in range(b, 0, -1):
		solutions += solver(a - i ** n, i - 1, x + '-' + str(i ** n))
	return solutions
print(solver(x, int(math.pow(x, 1 / n)), str(x)))


def no_of_pos(number, max_sqrtn, power):
	if number < 0 or (number > 0 and max_sqrtn == 0):
		return 0
	elif number == 0:
		return 1
	else:
		return no_of_pos(number - max_sqrtn ** power, max_sqrtn - 1, power) + no_of_pos(number, max_sqrtn - 1, power)
x_integer = int(input().strip())
exponent = int(input().strip())
print(no_of_pos(x_integer, power=exponent, max_sqrtn=int(x_integer ** (1 / exponent))))


import math
n = int(input())
exp = int(input())
numbers = [x for x in range(n) if math.pow(x, exp) < n]

def power_sum(n, m):
	if n == 0:
		return 1
	if n < 0:
		return 0
	else:
		ways = 0
		for i in range(1, m + 1):
			ways += power_sum(n - i ** exp, i - 1)
	return ways
print(power_sum(n, n))


x = int(input().strip())
n = int(input().strip())
maxi = 1
while maxi ** n < x:
	maxi += 1

def recu(tot, rec):
	newtot = tot + rec ** n
	if newtot > x:
		return 0
	elif newtot == x:
		return 1
	else:
		return sum((recu(newtot, i) for i in range(rec + 1, maxi + 1)))
print(recu(0, 0))


import sys
x = int(input().strip())
n = int(input().strip())

def PowerSum(x, n, k):
	if x == 0:
		return 1
	elif k == 0:
		return 0
	else:
		temp = 0
		for i in range(1, k + 1):
			if x - i ** n >= 0:
				temp += PowerSum(x - i ** n, n, i - 1)
		return temp
print(PowerSum(x, n, x))


import sys

def thing(p, n, sum):
	if sum < 0:
		return 0
	if sum == 1:
		return 1
	if sum == 0:
		return 1
	if n == 1:
		return 0
	newsum = sum - n ** pow
	newroot = int(newsum ** (1 / pow))
	newn = newroot
	if newroot >= n:
		newn = n - 1
	return thing(p, newn, newsum) + thing(p, n - 1, sum)
sum = int(sys.stdin.readline())
pow = int(sys.stdin.readline())
n = int(sum ** (1 / pow))
print(thing(pow, n, sum))


from itertools import chain, combinations

def list_powerset(lst, target):
	result = [[]]
	for x in lst:
		result.extend([subset + [x] for subset in result if sum(subset) <= target])
	return result
target = int(input())
n = int(input())
nth_root = int(pow(target, 1 / n) + 1)
powers = [pow(i, n) for i in range(1, nth_root)]
print(sum((1 for subset in list_powerset(powers, target) if sum(subset) == target)))


from math import ceil

def numWays(t, ps, i):
	if t == 0:
		return 1
	elif t < 0 or i >= len(ps):
		return 0
	else:
		return numWays(t - ps[i], ps, i + 1) + numWays(t, ps, i + 1)
target = int(input().strip())
power = int(input().strip())
powers = [i ** power for i in range(1, 1 + ceil(target ** (1 / power))) if i ** power <= target]
print(numWays(target, powers, 0))


import math
import itertools
target_val = int(input())
exponent = int(input())
num_bases = 0
for i in range(1, math.ceil(math.pow(target_val, 1 / exponent)) + 1):
	num_bases = i
power_list = [i ** exponent for i in range(1, num_bases + 1)]

def sum_nums(num_list, curr_sum, curr_count):
	for (i, x) in enumerate(num_list):
		if curr_sum + x > target_val:
			return curr_count
		if curr_sum + x == target_val:
			return curr_count + 1
		curr_count = sum_nums(num_list[i + 1:], curr_sum + x, curr_count)
count = sum_nums(power_list, 0, 0)
print(count)


def sumCubes(x, n, factor):
	if pow(factor, n) == x:
		return 1
	elif pow(factor, n) > x:
		return 0
	else:
		return sumCubes(x, n, factor + 1) + sumCubes(x - pow(factor, n), n, factor + 1)
x = int(input().strip())
n = int(input().strip())
print(sumCubes(x, n, 1))


x = int(input())
n = int(input())

def power_sum(x, n, start):
	if abs(start - x ** (1 / n)) < 0.0001:
		return 1
	if start > x ** (1 / n):
		return 0
	return power_sum(x, n, start + 1) + power_sum(x - start ** n, n, start + 1)
print(power_sum(x, n, 1))


m = int(input())
N = int(input())

def findout(n, k):
	if n == 0:
		return 1
	elif k == 0:
		return 0
	else:
		temp = 0
		for i in range(1, k + 1):
			if n - i ** N >= 0:
				temp += findout(n - i ** N, i - 1)
		return temp
print(findout(m, m))


import math

def exists_sum_of_powers(power, start, end):
	powered_start = start ** power
	new_end = end - powered_start
	if new_end < 0:
		return 0
	if new_end == 0:
		return 1
	return exists_sum_of_powers(power, start + 1, end) + exists_sum_of_powers(power, start + 1, new_end)
number = int(input())
power = int(input())
print(exists_sum_of_powers(power, 1, number))


import math
import sys

def powSum(temp, N):
	result = 0
	for nmbr in temp:
		result += int(math.pow(nmbr, N))
	return result

def findAllDecompositions(X, N, upperBound, powSet, counter, result):
	if not powSet:
		result.append(counter)
		return
	newCounter = counter
	newPowSet = []
	for mmbr in powSet:
		indic = mmbr[-1]
		for nmbr in range(indic + 1, upperBound + 1):
			temp = []
			temp.extend(mmbr)
			temp.append(nmbr)
			tempSum = powSum(temp, N)
			if tempSum == X:
				newCounter += 1
			elif tempSum < X:
				newPowSet.append(temp)
	findAllDecompositions(X, N, upperBound, newPowSet, newCounter, result)

def numberOfAllDecompositions():
	inp = []
	for line in sys.stdin:
		inp.append(int(line))
	X = inp[0]
	N = inp[1]
	upperBound = math.floor(math.pow(X, 1 / N))
	powSet = []
	result = []
	if X == int(math.pow(upperBound, N)):
		counter = 1
	else:
		counter = 0
	for i in range(1, upperBound + 1):
		powSet.append([i])
	findAllDecompositions(X, N, upperBound, powSet, counter, result)
	print(result[0])
numberOfAllDecompositions()


x = int(input().strip())
n = int(input().strip())

def testFunction(start, n, goal):
	new_number = start ** n
	if new_number > goal:
		return 0
	elif new_number == goal:
		return 1
	else:
		return testFunction(start + 1, n, goal - new_number) + testFunction(start + 1, n, goal)
print(testFunction(1, n, x))


num = int(input())
power = int(input())

def num_ways(start, target, power):
	total = 0
	while start ** power <= target:
		if start ** power == target:
			return total + 1
		total += num_ways(start + 1, target - start ** power, power)
		start += 1
	return total
total = num_ways(1, num, power)
print(total)


import math

class Answer:
	max_pos = 0

def find_powers(num, p):
	ans = Answer()
	max_val = int(math.pow(num, 1.0 / p))
	find_pow_rec(num, p, max_val, ans)
	return ans.max_pos

def find_pow_rec(num, p, max_val, ans):
	if num == 0:
		ans.max_pos += 1
		return
	elif num < 0 or max_val == 0:
		return
	max_val = min([int(math.pow(num, 1.0 / p)), max_val])
	for i in range(max_val, 0, -1):
		nex = num - i ** p
		find_pow_rec(nex, p, i - 1, ans)
	return
num = int(input().strip())
p = int(input().strip())
print(find_powers(num, p))


x = int(input())
n = int(input())

def ways(x, n, nums):
	nums = [c for c in nums if c ** n <= x]
	if x == 0:
		return 1
	if x < 0 or len(nums) == 0:
		return 0
	k = nums[0]
	k = k ** n
	return ways(x - k, n, nums[1:]) + ways(x, n, nums[1:])
nums = list(range(1, x + 1))
print(ways(x, n, nums))


x = int(input().strip())
n = int(input().strip())

def sumsq(x, a, n):
	if (a ** n == x) | (x == 0):
		return 1
	elif a ** n > x:
		return 0
	else:
		total = 0
		aa = a
		while aa ** n <= x:
			total += sumsq(x - aa ** n, aa + 1, n)
			aa += 1
		return total
print(sumsq(x, 1, n))


def psum(x, k):
	kn = k ** N
	if kn > x:
		return 0
	if kn == x:
		return 1
	if x < 0:
		return 0
	if x == 0:
		return 1
	return psum(x, k + 1) + psum(x - kn, k + 1)
X = int(input().strip())
N = int(input().strip())
print(psum(X, 1))


x = int(input())
n = int(input())

def count(x, n, b):
	if x == 0:
		return 1
	if x < 0 or x < b ** n:
		return 0
	return count(x - b ** n, n, b + 1) + count(x, n, b + 1)
print(count(x, n, 1))


import sys, math
(m, N) = [int(i.strip()) for i in sys.stdin]

def powerSum(n, k):
	if n == 0:
		return 1
	elif k == 0:
		return 0
	else:
		temp = 0
		for i in range(1, k + 1):
			if n - i ** N >= 0:
				temp += powerSum(n - i ** N, i - 1)
		return temp
print(powerSum(m, m))


x = int(input())
n = int(input())

def number_of_sum(x, p, n):
	if pow(p, n) > x:
		return 0
	elif pow(p, n) == x:
		return 1
	else:
		return number_of_sum(x - pow(p, n), p + 1, n) + number_of_sum(x, p + 1, n)
print(number_of_sum(x, 1, n))


def rec(X, N, i):
	if X is 0:
		return 1
	temp = pow(i, N)
	if temp > X:
		return 0
	return rec(X, N, i + 1) + rec(X - temp, N, i + 1)
(X, N) = (int(input()), int(input()))
print(rec(X, N, 1))


def power_sum(Y, count, X, N):
	if count > X:
		return 0
	elif count == X:
		return 1
	elif Y == 1:
		if count + Y ** N == X:
			return 1
		else:
			return 0
	else:
		return power_sum(Y - 1, count + Y ** N, X, N) + power_sum(Y - 1, count, X, N)
X = input()
N = input()
X = int(X)
N = int(N)
Y = 1 + int(X ** (1 / N))
print(power_sum(Y, 0, X, N))


import sys

def sumNumHelper(number, maxInt, power):
	if maxInt == 0:
		return 0
	sumNum = 0
	sumNum += sumNumHelper(number, maxInt - 1, power)
	nextNum = number - maxInt ** power
	if nextNum == 0:
		sumNum += 1
	else:
		nextNumInt = maxInt - 1
		if nextNumInt ** power > nextNum:
			nextNumInt = int(nextNum ** (1 / power))
		sumNum += sumNumHelper(nextNum, nextNumInt, power)
	return sumNum

def sumNum(number, power):
	maxInt = int(number ** (1 / power))
	return sumNumHelper(number, maxInt, power)
number = int(input().strip())
power = int(input().strip())
result = sumNum(number, power)
print(result)


def find(pos, x, sum_x, n):
	count = 0
	if sum_x == x:
		return 1
	for i in range(pos + 1, round(pow(x, 1 / n)) + 1):
		if sum_x + pow(i, n) <= x:
			count += find(i, x, sum_x + pow(i, n), n)
	return count
x = int(input())
n = int(input())
print(find(0, x, 0, n))


X = int(input())
n = int(input())

class ST:

	def __init__(self, X, n):
		self.X = X
		self.n = n
		self.ct = 0
		self.hit = 0

	def __call__(self):
		self.f(self.X, 0)
		return self.ct

	def f(self, x, i):
		j = i
		if x == 0:
			self.hit = self.hit + 1
		if x <= 0:
			self.ct = self.ct + 1
			return False
		else:
			j = i + 1
			while self.f(x - j ** self.n, j):
				j = j + 1
			return True
st = ST(X, n)
st()
print(st.hit)


import sys

def getNumberOfWays(powernumberArray, currIndex, currSum, X):
	if len(powernumberArray) <= currIndex or currSum >= X:
		if currSum == X:
			return 1
		else:
			return 0
	return getNumberOfWays(powernumberArray, currIndex + 1, currSum + powernumberArray[currIndex], X) + getNumberOfWays(powernumberArray, currIndex + 1, currSum, X)
X = int(input().strip())
N = int(input().strip())
powerNumbers = []
currNumber = 1
power = 1
while power <= X:
	powerNumbers.append(power)
	currNumber += 1
	power = currNumber ** N
Nways = getNumberOfWays(powerNumbers, 0, 0, X)
print(Nways)


X = int(input())
N = int(input())
DP = [0] * (X + 1)
DP[0] = 1
for i in range(1, X):
	x = i ** N
	if x > X:
		break
	for j in range(X - x, -1, -1):
		DP[j + x] += DP[j]
print(DP[X])


def solve(x, n, i):
	if x == 0:
		return 1
	if x < 0:
		return 0
	s = 0
	max_i = int(x ** (1 / n)) + 1
	while i <= max_i:
		s += solve(x - i ** n, n, i + 1)
		i += 1
	return s

def main():
	x = int(input())
	n = int(input())
	print(solve(x, n, 1))
main()


from functools import lru_cache
x = int(input())
n = int(input())

@lru_cache(maxsize=None)
def findsum(v, u):
	if not v:
		return 1
	return sum((findsum(v - i ** n, i) for i in range(1, u)))
print(findsum(x, int(x ** (1 / n)) + 1))


x = int(input())
n = int(input())
dp = [1] + [0] * x
for i in range(1, int(pow(x, 1 / n)) + 1):
	u = i ** n
	for j in range(x, u - 1, -1):
		dp[j] += dp[j - u]
print(dp[-1])


from math import *

def powerSum(total, power, base, sum1):
	cur = pow(float(base), float(power))
	if sum1 + cur == total:
		return 1
	elif sum1 > total or cur > total:
		return 0
	else:
		return powerSum(total, power, base + 1, sum1 + cur) + powerSum(total, power, base + 1, sum1)
total = int(input().strip())
power = int(input().strip())
result = powerSum(total, power, 1, 0)
print(result)