





"""simple docstring"""






from math import pow

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,)		->       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

       _UpperCAmelCase     =     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
              _UpperCAmelCase    ,							_UpperCAmelCase     =     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.
              _UpperCAmelCase    ,							_UpperCAmelCase     =     backtrack(
                  SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE,current_number + 1,SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)
       return current_sum, solutions_count

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,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()













"""simple docstring"""






def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       int:






       """simple docstring"""




       return number | (1 << position)

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       int:






       """simple docstring"""




       return number & ~(1 << position)

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       int:






       """simple docstring"""




       return number ^ (1 << position)

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       bool:






       """simple docstring"""




       return ((number >> position) & 1) == 1

def       __lowerCamelCase    (       SCREAMING_SNAKE_CASE,SCREAMING_SNAKE_CASE							)		->       int:






       """simple docstring"""




       return int((number & (1 << position)) != 0							)


if __name__ == "__main__":
    import doctest

    doctest.testmod()






