





from collections import defaultdict

class 							__SCREAMING_SNAKE_CASE       :






							def __init__(    self	,			__lowerCAmelCase	,			__lowerCAmelCase	):
														UpperCamelCase__					  =      total  # total no of tasks (N)

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

														UpperCamelCase__					  =      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
														UpperCamelCase__					  =      (1 << len(_UpperCamelCase	)) - 1






							def 					_lowerCamelCase		(    self	,			__lowerCAmelCase	,			__lowerCAmelCase	):


														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
														UpperCamelCase__					  =      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.
														UpperCamelCase__					  =      total_ways_util

														return self.dp[mask][task_no]







							def 					_lowerCamelCase		(    self	,			__lowerCAmelCase	):


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

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







def 						lowerCamelCase__      ( __A    :int	,__A    :int		):


       """simple docstring"""




       if a < 0 or b < 0:
              raise ValueError("""the value of both inputs must be positive"""		)

       __snake_case       	=							str(bin(__A		)		)[2:]  # remove the leading "0b"
       __snake_case       	=							str(bin(__A		)		)[2:]  # remove the leading "0b"

       __snake_case       	=							max(len(__A		)	,len(__A		)		)

       return "0b" + "".join(
           str(int(char_a == """1""" and char_b == """1"""		)		)
           for char_a, char_b in zip(a_binary.zfill(__A		)	,b_binary.zfill(__A		)		)		)


if __name__ == "__main__":
    import doctest

    doctest.testmod()

