



'''simple docstring'''





from math import pow
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase							,    UpperCamelCase							,    UpperCamelCase							,    UpperCamelCase							,    UpperCamelCase							,    ):



    """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__ :  Optional[int]							      =					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
        lowerCAmelCase__      ,   lowerCAmelCase__ :  Union[str, Any]							      =					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.
        lowerCAmelCase__      ,   lowerCAmelCase__ :  Tuple							      =					backtrack(
            UpperCamelCase							,    UpperCamelCase							,    current_number + 1							,    UpperCamelCase							,    UpperCamelCase			)
    return current_sum, solutions_count
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase							,    UpperCamelCase			):



    """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    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    lowerCAmelCase__ :  Tuple							      =					abs(UpperCamelCase			)
    lowerCAmelCase__ :  List[Any]							      =					0
    while n > 0:
        res += n % 10
        n //= 10
    return res
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    lowerCAmelCase__ :  Union[str, Any]							      =					abs(UpperCamelCase			)
    return n if n < 10 else n % 10 + sum_of_digits(n // 10			)
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    return sum(int(UpperCamelCase			) for c in str(abs(UpperCamelCase			)			)			)
def    _SCREAMING_SNAKE_CASE  (       ):



    """simple docstring"""





    from collections.abc import Callable
    from timeit import timeit

    def benchmark_a_function(UpperCamelCase							,    UpperCamelCase			) -> None:
        lowerCAmelCase__ :  str							      =					f"""{func.__name__}({value})"""
        lowerCAmelCase__ :  str							      =					timeit(f"""__main__.{call}"""							,    setup="""import __main__"""			)
        print(f"""{call:56} = {func(UpperCamelCase			)} -- {timing:.4f} seconds"""			)

    for value in (262144, 1125899906842624, 1267650600228229401496703205376):
        for func in (sum_of_digits, sum_of_digits_recursion, sum_of_digits_compact):
            benchmark_a_function(UpperCamelCase							,    UpperCamelCase			)
        print()


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 benchmark()


