


from __future__ import annotations

from functools import lru_cache
from math import ceil

lowercase_	   =     1_0_0

lowercase_	   =     set(range(3, NUM_PRIMES, 2))
primes.add(2)
lowercase_	   =     42

for prime in range(3, ceil(NUM_PRIMES**0.5), 2):
       if prime not in primes:
              continue
       primes.difference_update(set(range(prime * prime, NUM_PRIMES, prime)))
@lru_cache(maxsize=100						)
def 				UpperCamelCase__					(  SCREAMING_SNAKE_CASE__						):
 if number_to_partition < 0:
  return set()
 elif number_to_partition == 0:
  return {1}

 __lowerCamelCase		:							set[int]		 =						set()
 __lowerCamelCase		:							int
 __lowerCamelCase		:							int

 for prime in primes:
  if prime > number_to_partition:
   continue
  for sub in partition(number_to_partition - prime						):
   ret.add(sub * prime						)

 return ret
def 				UpperCamelCase__					(  SCREAMING_SNAKE_CASE__ = 5_000						):
 for number_to_partition in range(1      ,	SCREAMING_SNAKE_CASE__						):
  if len(partition(SCREAMING_SNAKE_CASE__						)						) > number_unique_partitions:
   return number_to_partition
 return None


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





from math import pow
def 				UpperCamelCase__					(  SCREAMING_SNAKE_CASE__      ,	SCREAMING_SNAKE_CASE__      ,	SCREAMING_SNAKE_CASE__      ,	SCREAMING_SNAKE_CASE__      ,	SCREAMING_SNAKE_CASE__      ,	):
 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(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		:							Optional[Any]		 =						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		:							Dict		 =						backtrack(
      SCREAMING_SNAKE_CASE__      ,	SCREAMING_SNAKE_CASE__      ,	current_number + 1      ,	SCREAMING_SNAKE_CASE__      ,	SCREAMING_SNAKE_CASE__						)
 return current_sum, solutions_count
def 				UpperCamelCase__					(  SCREAMING_SNAKE_CASE__      ,	SCREAMING_SNAKE_CASE__						):
 if not (1 <= needed_sum <= 1_000 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()

