



"""simple docstring"""
from math import pow


def 	_SCREAMING_SNAKE_CASE  (__lowerCAmelCase       ,     __lowerCAmelCase       ,     __lowerCAmelCase       ,     __lowerCAmelCase       ,     __lowerCAmelCase       ,     )       ->  Optional[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

  lowercase_	    =       int(pow(__lowerCAmelCase       ,     __lowerCAmelCase							)							)
  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
    lowercase_	    =       backtrack(
        __lowerCAmelCase       ,     __lowerCAmelCase       ,     current_number + 1       ,     __lowerCAmelCase       ,     __lowerCAmelCase							)
    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.
    lowercase_	    =       backtrack(
        __lowerCAmelCase       ,     __lowerCAmelCase       ,     current_number + 1       ,     __lowerCAmelCase       ,     __lowerCAmelCase							)
  return current_sum, solutions_count


def 	_SCREAMING_SNAKE_CASE  (__lowerCAmelCase       ,     __lowerCAmelCase							)       ->  int:







  '''simple docstring'''


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

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


if __name__ == "__main__":
       import doctest

       doctest.testmod()


'''simple docstring'''

from math import pow
def 			__UpperCamelCase       (   UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     ):
 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

 lowercase__				:    Optional[Any]  =					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
  lowercase__ ,							lowercase__				:    Dict  =					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.
  lowercase__ ,							lowercase__				:    str  =					backtrack(
      UpperCAmelCase		,     UpperCAmelCase		,     current_number + 1		,     UpperCAmelCase		,     UpperCAmelCase     )
 return current_sum, solutions_count
def 			__UpperCamelCase       (   UpperCAmelCase		,     UpperCAmelCase     ):
 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()

