





from __future__ import annotations





def 					lowerCAmelCase_			(	__a		)					->		bool:







  """simple docstring"""





  lowerCamelCase__:				str        =str(__lowerCAmelCase		)
  return len(__lowerCAmelCase		) == 9 and set(__lowerCAmelCase		) == set("123456789"		)





def 					lowerCAmelCase_			(	)					->		int | None:







  """simple docstring"""





  for base_num in range(9999     ,   4999     ,   -1		):
    lowerCamelCase__:				Optional[int]        =100002 * base_num
    if is_9_pandigital(__lowerCAmelCase		):
      return candidate

  for base_num in range(333     ,   99     ,   -1		):
    lowerCamelCase__:				List[str]        =1002003 * base_num
    if is_9_pandigital(__lowerCAmelCase		):
      return candidate

  return None


if __name__ == "__main__":
   print(f'{solution() = }')








from math import pow





def 					lowerCAmelCase_			(	__a     ,   __a     ,   __a     ,   __a     ,   __a     ,   )					->		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

  lowerCamelCase__:				Optional[Any]        =int(pow(__a     ,   __a		)		)
  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__:				int        =backtrack(
        __a     ,   __a     ,   current_number + 1     ,   __a     ,   __a		)
    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__:				Dict        =backtrack(
        __a     ,   __a     ,   current_number + 1     ,   __a     ,   __a		)
  return current_sum, solutions_count





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


if __name__ == "__main__":
     import doctest

     doctest.testmod()

