


from __future__ import annotations

from functools import lru_cache
from math import ceil

snake_case      :   List[Any]							= 1_00

snake_case      :   Any							= set(range(3, NUM_PRIMES, 2))
primes.add(2)
snake_case      :   int

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 					SCREAMING_SNAKE_CASE			(  UpperCAmelCase__				):

				"""simple docstring"""






				if number_to_partition < 0:
								return set()
				elif number_to_partition == 0:
								return {1}

				_SCREAMING_SNAKE_CASE   =			set()
				_SCREAMING_SNAKE_CASE   =			42
				_SCREAMING_SNAKE_CASE   =			42

				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 					SCREAMING_SNAKE_CASE			(  UpperCAmelCase__ = 5000				):

				"""simple docstring"""






				for number_to_partition in range(1 ,UpperCAmelCase__				):
								if len(partition(UpperCAmelCase__				)				) > number_unique_partitions:
												return number_to_partition
				return None


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







def  SCREAMING_SNAKE_CASE				(      snake_case						,   snake_case						,   snake_case							)		->    int:

		def count_of_possible_combinations(snake_case							) -> int:
				if target < 0:
						return 0
				if target == 0:
						return 1
				return sum(count_of_possible_combinations(target - item							) for item in array							)

		return count_of_possible_combinations(snake_case							)



def  SCREAMING_SNAKE_CASE				(      snake_case						,   snake_case						,   snake_case							)		->    int:

		def count_of_possible_combinations_with_dp_array(
		    snake_case						,   snake_case							) -> int:
				if target < 0:
						return 0
				if target == 0:
						return 1
				if dp_array[target] != -1:
						return dp_array[target]
				__lowercase											=     sum(
				    count_of_possible_combinations_with_dp_array(target - item						,   snake_case							)
				    for item in array							)
				__lowercase											=     answer
				return answer

		__lowercase											=     [-1] * (target + 1)
		return count_of_possible_combinations_with_dp_array(snake_case						,   snake_case							)



def  SCREAMING_SNAKE_CASE				(      snake_case						,   snake_case						,   snake_case							)		->    int:
		__lowercase											=     [0] * (target + 1)
		__lowercase											=     1

		for i in range(1						,   target + 1							):
				for j in range(snake_case							):
						if i - array[j] >= 0:
								dp_array[i] += dp_array[i - array[j]]

		return dp_array[target]


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		SCREAMING_SNAKE_CASE_   :      Tuple			=   3
		SCREAMING_SNAKE_CASE_   :      Dict			=   5
		SCREAMING_SNAKE_CASE_   :      Any			=   [1, 2, 5]
		print(combination_sum_iv(n, array, target))




