





'''simple docstring'''


from math import pow


def 						__a(SCREAMING_SNAKE_CASE_	:       int		,							SCREAMING_SNAKE_CASE_	:       int		,							SCREAMING_SNAKE_CASE_	:       int		,							SCREAMING_SNAKE_CASE_	:       int		,							SCREAMING_SNAKE_CASE_	:       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

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


def 						__a(SCREAMING_SNAKE_CASE_	:       int		,							SCREAMING_SNAKE_CASE_	:       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(SCREAMING_SNAKE_CASE_		,							SCREAMING_SNAKE_CASE_		,							1		,							0		,							0     )[1]  # Return the solutions_count


if __name__ == "__main__":
       import doctest

       doctest.testmod()








def        __UpperCAmelCase						(							lowerCamelCase_ :     str  )       ->  bool:







			"""simple docstring"""





			SCREAMING_SNAKE_CASE_   : Any					  =      0
			for ch in input_str:
						SCREAMING_SNAKE_CASE_   : Union[str, Any]					  =      ord(lowerCamelCase_  )
						SCREAMING_SNAKE_CASE_   : Tuple					  =      pow(2  ,							lowerCamelCase_  )

						# If we already turned on bit for current character's unicode
						if bitmap >> ch_unicode & 1 == 1:
									return False
						bitmap |= ch_bit_index_on
			return True


if __name__ == "__main__":
						import doctest

						doctest.testmod()



