


from collections import defaultdict


class      __lowerCAmelCase  :






  """simple docstring"""





  def __init__(  self							:							Tuple     ,					_lowerCAmelCase							:							Union[str, Any]     ,					_lowerCAmelCase							:							str	) ->			Optional[int]:




     """simple docstring"""
     snake_case_            =       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_            =       [
         [-1 for i in range(total + 1	)] for j in range(2 ** len(_lowerCAmelCase	)	)
     ]

     snake_case_            =       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_            =       (1 << len(_lowerCAmelCase	)) - 1



  def        lowerCAmelCase__	(  self							:							Optional[int]     ,					_lowerCAmelCase							:							Optional[Any]     ,					_lowerCAmelCase							:							str	) ->			Tuple:




     """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
     snake_case_            =       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_            =       total_ways_util

     return self.dp[mask][task_no]



  def        lowerCAmelCase__	(  self							:							List[str]     ,					_lowerCAmelCase							:							Union[str, Any]	) ->			Tuple:




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

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








def       _lowerCAmelCase    (				lowerCAmelCase_				:List[str]		,    lowerCAmelCase_				:int				)->Optional[int]:
   '''simple docstring'''






   snake_case_            =       0
   while b > 0:
      if b & 1:
         res += a

      a += a
      b >>= 1

   return res



def       _lowerCAmelCase    (				lowerCAmelCase_				:int		,    lowerCAmelCase_				:List[str]		,    lowerCAmelCase_				:Dict				)->Dict:
   '''simple docstring'''






   snake_case_            =       0
   while b > 0:
      if b & 1:
         snake_case_            =       ((res % c) + (a % c)) % c

      a += a
      b >>= 1

   return res




