


from collections import defaultdict

class     a		:




							"""simple docstring"""


							def __init__(							self	:  str   ,     lowerCamelCase	:  Optional[int]   ,     lowerCamelCase	:  Any    )     ->   str:
														__snake_case		:      Union[str, Any]										=       total  # total no of tasks (N)

														# DP table will have a dimension of (2^M)*N
														# initially all values are set to -1
														__snake_case		:      Union[str, Any]										=       [
														    [-1 for i in range(total + 1    )] for j in range(2 ** len(lowerCamelCase    )    )
														]

														__snake_case		:      Optional[Any]										=       defaultdict(lowerCamelCase    )  # 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
														__snake_case		:      List[str]										=       (1 << len(lowerCamelCase    )) - 1

							def    __snake_case (							self	:  int   ,     lowerCamelCase	:  Dict   ,     lowerCamelCase	:  Tuple    )     ->   str:
														# if mask == self.finalmask all persons are distributed tasks, return 1
														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
														__snake_case		:      List[str]										=       self.count_ways_until(lowerCamelCase   ,     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.
														__snake_case		:      Dict										=       total_ways_util

														return self.dp[mask][task_no]






							def    __snake_case (							self	:  Dict   ,     lowerCamelCase	:  Union[str, Any]    )     ->   Tuple:
														# Store the list of persons for each task
														for i in range(len(lowerCamelCase    )    ):
																					for j in task_performed[i]:
																												self.task[j].append(lowerCamelCase    )

        # 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					:		Dict      =    5  # total no of tasks (the value of N)

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





def     lowerCAmelCase_					( __lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase     ):
							if index == r:
														for j in range(__lowerCamelCase     ):
																					print(data[j]							,     end=" "     )
														print(" "     )
														return
							#  When no more elements are there to put in data[]
							if i >= n:
														return
							# current is included, put next at next location
							__snake_case		:      Union[str, Any]										=       arr[i]
							combination_util(__lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     index + 1							,     __lowerCamelCase							,     i + 1     )
							# current is excluded, replace it with
							# next (Note that i+1 is passed, but
							# index is not changed)
							combination_util(__lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     i + 1     )
							# The main function that prints all combinations
							# of size r in arr[] of size n. This function
							# mainly uses combinationUtil()







def     lowerCAmelCase_					( __lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase     ):
							# A temporary array to store all combination one by one
							__snake_case		:      Union[str, Any]										=       [0] * r
							# Print all combination using temporary array 'data[]'
							combination_util(__lowerCamelCase							,     __lowerCamelCase							,     __lowerCamelCase							,     0							,     __lowerCamelCase							,     0     )


if __name__ == "__main__":
			# Driver code to check the function above
			_snake_case					:		List[str]      =    [10, 20, 30, 40, 50]
			print_combination(arr, len(arr), 3)
			# This code is contributed by Ambuj sahu

