
from collections import defaultdict
class       _lowerCAmelCase  :

 """simple docstring"""

 def __init__(						self			:			List[str]					, SCREAMING_SNAKE_CASE__			:			Any					, SCREAMING_SNAKE_CASE__			:			List[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(SCREAMING_SNAKE_CASE__   )   )
      ]

      UpperCamelCase						    =					defaultdict(SCREAMING_SNAKE_CASE__   )  # 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(SCREAMING_SNAKE_CASE__   )) - 1

 def      __lowerCAmelCase  (						self			:			List[Any]					, SCREAMING_SNAKE_CASE__			:			int					, SCREAMING_SNAKE_CASE__			:			Optional[int]   ):






      """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
      UpperCamelCase						    =					self.count_ways_until(SCREAMING_SNAKE_CASE__					, 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			:			List[str]					, SCREAMING_SNAKE_CASE__			:			int   ):






      """simple docstring"""



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

        # 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
     )
 )




def  __lowerCamelCase					( _lowercase			)       ->      str:
     return "".join(chr(ord(_lowercase			) - 32			) if 'a' <= char <= 'z' else char for char in word			)


if __name__ == "__main__":
 from doctest import testmod

 testmod()


