


"""simple docstring"""


def 			__snake_case							( UpperCamelCase__			,      UpperCamelCase__			,      UpperCamelCase__						)   ->		int:







		"""simple docstring"""





		def count_of_possible_combinations(UpperCamelCase__						) -> 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(_A						)







def 			__snake_case							( UpperCamelCase__			,      UpperCamelCase__			,      UpperCamelCase__						)   ->		int:







		"""simple docstring"""





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

		A       							=			[-1] * (target + 1)
		return count_of_possible_combinations_with_dp_array(_A			,      _A						)







def 			__snake_case							( UpperCamelCase__			,      UpperCamelCase__			,      UpperCamelCase__						)   ->		int:







		"""simple docstring"""





		A       							=			[0] * (target + 1)
		A       							=			1

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

		return dp_array[target]


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	UpperCamelCase    :					int							   =   3
	UpperCamelCase    :					Union[str, Any]							   =   5
	UpperCamelCase    :					Tuple							   =   [1, 2, 5]
	print(combination_sum_iv(n, array, target))






'''simple docstring'''




from functools import lru_cache






@lru_cache
def 							snake_case__				(     _A:   int					)       ->      int:

		'''simple docstring'''


		if num < 0:
				raise ValueError("""Number should not be negative."""					)

		return 1 if num in (0, 1) else num * factorial(num - 1					)


if __name__ == "__main__":
						import doctest

						doctest.testmod()




