


"""simple docstring"""


from math import pow







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__ ,			UpperCamelCase__ ,			UpperCamelCase__ ,			UpperCamelCase__ ,			)      ->		tuple[int, int]:







		"""simple docstring"""





		if current_sum == needed_sum:
				# If the sum of the powers is equal to needed_sum, then we have a solution.
				solutions_count += 1
				return current_sum, solutions_count

		A					       = int(pow(UpperCamelCase__ ,			UpperCamelCase__	)	)
		if current_sum + i_to_n <= needed_sum:
				# If the sum of the powers is less than needed_sum, then continue adding powers.
				current_sum += i_to_n
				A       , A					       = backtrack(
				    UpperCamelCase__ ,			UpperCamelCase__ ,			current_number + 1 ,			UpperCamelCase__ ,			UpperCamelCase__	)
				current_sum -= i_to_n
		if i_to_n < needed_sum:
				# If the power of i is less than needed_sum, then try with the next power.
				A       , A					       = backtrack(
				    UpperCamelCase__ ,			UpperCamelCase__ ,			current_number + 1 ,			UpperCamelCase__ ,			UpperCamelCase__	)
		return current_sum, solutions_count







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		int:







		"""simple docstring"""





		if not (1 <= needed_sum <= 1000 and 2 <= power <= 10):
				raise ValueError(
				    'Invalid input\n'
				    'needed_sum must be between 1 and 1000, power between 2 and 10.'	)

		return backtrack(UpperCamelCase__ ,			UpperCamelCase__ ,			1 ,			0 ,			0	)[1]  # Return the solutions_count


if __name__ == "__main__":
	import doctest

	doctest.testmod()









"""simple docstring"""


def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__ = " "	)      ->		list:







		"""simple docstring"""





		A					       = []

		A					       = 0
		for index, char in enumerate(UpperCamelCase__	):
				if char == separator:
						split_words.append(string[last_index:index]	)
						A					       = index + 1
				elif index + 1 == len(UpperCamelCase__	):
						split_words.append(string[last_index : index + 1]	)
		return split_words


if __name__ == "__main__":
	from doctest import testmod

	testmod()





