
"""simple docstring"""



from collections import defaultdict
class        _SCREAMING_SNAKE_CASE  :






				'''simple docstring'''



				def __init__(					self	:			List[Any]				,     UpperCAmelCase_	:			List[str]				,     UpperCAmelCase_	:			Optional[int]  )		->  str:







											"""simple docstring"""




											_lowerCAmelCase  	=			total  # total no of tasks (N)

											# DP table will have a dimension of (2^M)*N
											# initially all values are set to -1
											_lowerCAmelCase  	=			[
											    [-1 for i in range(total + 1  )] for j in range(2 ** len(UpperCAmelCase_  )  )
											]

											_lowerCAmelCase  	=			defaultdict(UpperCAmelCase_  )  # stores the list of persons for each task

											# final_mask is used to check if all persons are included by setting all bits
											# to 1
											_lowerCAmelCase  	=			(1 << len(UpperCAmelCase_  )) - 1


				def 				__lowerCamelCase	(					self	:			Dict				,     UpperCAmelCase_	:			Dict				,     UpperCAmelCase_	:			str  )		->  str:







											"""simple docstring"""




											if mask == self.final_mask:
																		return 1

											# if not everyone gets the task and no more tasks are available, return 0
											if task_no > self.total_tasks:
																		return 0

											# if case already considered
											if self.dp[mask][task_no] != -1:
																		return self.dp[mask][task_no]

											# Number of ways when we don't this task in the arrangement
											_lowerCAmelCase  	=			self.count_ways_until(UpperCAmelCase_				,     task_no + 1  )

											# now assign the tasks one by one to all possible persons and recursively
											# assign for the remaining tasks.
											if task_no in self.task:
																		for p in self.task[task_no]:
																									# if p is already given a task
																									if mask & (1 << p):
																																continue

																									# assign this task to p and change the mask value. And recursively
																									# assign tasks with the new mask value.
																									total_ways_util += self.count_ways_until(mask | (1 << p)				,     task_no + 1  )

        # save the value.
											_lowerCAmelCase  	=			total_ways_util

											return self.dp[mask][task_no]







				def 				__lowerCamelCase	(					self	:			List[Any]				,     UpperCAmelCase_	:			str  )		->  Dict:







											"""simple docstring"""




											for i in range(len(UpperCAmelCase_  )  ):
																		for j in task_performed[i]:
																									self.task[j].append(UpperCAmelCase_  )

        # call the function to fill the DP table, final answer is stored in dp[0][1]
											return self.count_ways_until(0				,     1  )


if __name__ == "__main__":
							_snake_case          =						5  # total no of tasks (the value of N)

							# the list of tasks that can be done by M persons.
							_snake_case          =						[[1, 3, 4], [1, 2, 5], [3, 4]]
							print(
							    AssignmentUsingBitmask(task_performed, total_tasks).count_no_of_ways(
							        task_performed
							    )
							)








"""simple docstring"""



def 	__snake_case  (    SCREAMING_SNAKE_CASE:					list[int]						):






							"""simple docstring"""



							_lowerCAmelCase  	=			[]
							if len(SCREAMING_SNAKE_CASE						) == 1:
														return [nums.copy()]
							for _ in range(len(SCREAMING_SNAKE_CASE						)						):
														_lowerCAmelCase  	=			nums.pop(0						)
														_lowerCAmelCase  	=			permute(SCREAMING_SNAKE_CASE						)
														for perm in permutations:
																					perm.append(SCREAMING_SNAKE_CASE						)
														result.extend(SCREAMING_SNAKE_CASE						)
														nums.append(SCREAMING_SNAKE_CASE						)
							return result






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					Any						):






							"""simple docstring"""



							def backtrack(SCREAMING_SNAKE_CASE:					Tuple						):
														if start == len(SCREAMING_SNAKE_CASE						) - 1:
																					output.append(nums[:]						)
														else:
																					for i in range(SCREAMING_SNAKE_CASE     ,  len(SCREAMING_SNAKE_CASE						)						):
																												_lowerCAmelCase	,		_lowerCAmelCase  	=			nums[i], nums[start]
																												backtrack(start + 1						)
																												_lowerCAmelCase	,		_lowerCAmelCase  	=			nums[i], nums[start]  # backtrack

							_lowerCAmelCase  	=			[]
							backtrack(0						)
							return output


if __name__ == "__main__":
	import doctest

	# use res to print the data in permute2 function
	_snake_case          =						permutea([1, 2, 3])
	print(res)
	doctest.testmod()






