
"""simple docstring"""





from importlib import import_module

from .logging import get_logger


_a														=		get_logger(__name__)






class     _UpperCAmelCase:



		def __init__(					self				,		__a				,		__a=None)       ->       str:






							'''simple docstring'''
							_UpperCamelCase							 =  attrs or []
							if module is not None:
												for key in module.__dict__:
																	if key in attrs or not key.startswith('''__'''):
																						setattr(self				,		__a				,		getattr(__a				,		__a))
							_UpperCamelCase							 =  module._original_module if isinstance(__a				,		_PatchedModuleObj) else module






class     _UpperCAmelCase:
		lowercase__						=      []



		def __init__(					self				,		__a				,		__a				,		__a				,		__a=None)       ->       Dict:






							'''simple docstring'''
							_UpperCamelCase							 =  obj
							_UpperCamelCase							 =  target
							_UpperCamelCase							 =  new
							_UpperCamelCase							 =  target.split('''.''')[0]
							_UpperCamelCase							 =  {}
							_UpperCamelCase							 =  attrs or []



		def __enter__(					self)       ->       Tuple:






							'''simple docstring'''
							*_UpperCamelCase ,  _UpperCamelCase							 =  self.target.split('''.''')

							# Patch modules:
							# it's used to patch attributes of submodules like "os.path.join";
							# in this case we need to patch "os" and "os.path"

							for i in range(len(__a)):
												try:
																	_UpperCamelCase							 =  import_module('''.'''.join(submodules[: i + 1]))
												except ModuleNotFoundError:
																	continue
												# We iterate over all the globals in self.obj in case we find "os" or "os.path"
												for attr in self.obj.__dir__():
																	_UpperCamelCase							 =  getattr(self.obj				,		__a)
																	# We don't check for the name of the global, but rather if its value *is* "os" or "os.path".
																	# This allows to patch renamed modules like "from os import path as ospath".
																	if obj_attr is submodule or (
																	    (isinstance(__a				,		_PatchedModuleObj) and obj_attr._original_module is submodule)
																	):
																						_UpperCamelCase							 =  obj_attr
																						# patch at top level
																						setattr(self.obj				,		__a				,		_PatchedModuleObj(__a				,		attrs=self.attrs))
																						_UpperCamelCase							 =  getattr(self.obj				,		__a)
																						# construct lower levels patches
																						for key in submodules[i + 1 :]:
																											setattr(__a				,		__a				,		_PatchedModuleObj(getattr(__a				,		__a				,		__a)				,		attrs=self.attrs))
																											_UpperCamelCase							 =  getattr(__a				,		__a)
																						# finally set the target attribute
																						setattr(__a				,		__a				,		self.new)

        # Patch attribute itself:
        # it's used for builtins like "open",
        # and also to patch "os.path.join" we may also need to patch "join"
        # itself if it was imported as "from os.path import join".

							if submodules:  # if it's an attribute of a submodule like "os.path.join"
												try:
																	_UpperCamelCase							 =  getattr(import_module('''.'''.join(__a))				,		__a)
												except (AttributeError, ModuleNotFoundError):
																	return
												# We iterate over all the globals in self.obj in case we find "os.path.join"
												for attr in self.obj.__dir__():
																	# We don't check for the name of the global, but rather if its value *is* "os.path.join".
																	# This allows to patch renamed attributes like "from os.path import join as pjoin".
																	if getattr(self.obj				,		__a) is attr_value:
																						_UpperCamelCase							 =  getattr(self.obj				,		__a)
																						setattr(self.obj				,		__a				,		self.new)
							elif target_attr in globals()["__builtins__"]:  # if it'a s builtin like "open"
												_UpperCamelCase							 =  globals()['''__builtins__'''][target_attr]
												setattr(self.obj				,		__a				,		self.new)
							else:
												raise RuntimeError(F'''Tried to patch attribute {target_attr} instead of a submodule.''')



		def __exit__(					self				,		*__a)       ->       List[str]:






							'''simple docstring'''
							for attr in list(self.original):
												setattr(self.obj				,		__a				,		self.original.pop(__a))



		def 						UpperCAmelCase							(					self)       ->       Optional[Any]:






							'''simple docstring'''
							self.__enter__()
							self._active_patches.append(self)




		def 						UpperCAmelCase							(					self)       ->       Union[str, Any]:






							'''simple docstring'''
							try:
												self._active_patches.remove(self)
							except ValueError:
												# If the patch hasn't been started this will fail
												return None

							return self.__exit__()








"""simple docstring"""





from collections import defaultdict






class     _UpperCAmelCase:



		def __init__(					self				,		__a				,		__a)       ->       Union[str, Any]:






							'''simple docstring'''
							_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(__a))
							]

							_UpperCamelCase							 =  defaultdict(__a)  # 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(__a)) - 1



		def 						UpperCAmelCase							(					self				,		__a				,		__a)       ->       Dict:






							'''simple docstring'''
							# 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
							_UpperCamelCase							 =  self.count_ways_until(__a				,		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 						UpperCAmelCase							(					self				,		__a)       ->       int:






							'''simple docstring'''
							# Store the list of persons for each task
							for i in range(len(__a)):
												for j in task_performed[i]:
																	self.task[j].append(__a)

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

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






