





from typing import List

import numpy as np






def 			_SCREAMING_SNAKE_CASE						(     SCREAMING_SNAKE_CASE						:dict       )     ->       int:
 __lowerCAmelCase	:			List[Any]         =  {key: len(_lowerCAmelCase       ) for key, value in gen_kwargs.items() if isinstance(_lowerCAmelCase       ,       _lowerCAmelCase       )}
 if len(set(lists_lengths.values()       )       ) > 1:
  raise RuntimeError(
      (
          """Sharding is ambiguous for this dataset: """
          + """we found several data sources lists of different lengths, and we don't know over which list we should parallelize:\n"""
          + """\n""".join(F'''\t- key {key} has length {length}''' for key, length in lists_lengths.items()       )
          + """\nTo fix this, check the 'gen_kwargs' and make sure to use lists only for data sources, """
          + """and use tuples otherwise. In the end there should only be one single list, or several lists with the same length."""
      )       )
 __lowerCAmelCase	:			Union[str, Any]         =  max(lists_lengths.values()       ,       default=0       )
 return max(1       ,       _lowerCAmelCase       )






def 			_SCREAMING_SNAKE_CASE						(     SCREAMING_SNAKE_CASE						:int       ,       SCREAMING_SNAKE_CASE						:int       )     ->       List[range]:
 __lowerCAmelCase	:			str         =  []
 for group_idx in range(_lowerCAmelCase       ):
  __lowerCAmelCase	:			Tuple         =  num_shards // max_num_jobs + (group_idx < (num_shards % max_num_jobs))
  if num_shards_to_add == 0:
   break
  __lowerCAmelCase	:			int         =  shards_indices_per_group[-1].stop if shards_indices_per_group else 0
  __lowerCAmelCase	:			Optional[Any]         =  range(_lowerCAmelCase       ,       start + num_shards_to_add       )
  shards_indices_per_group.append(_lowerCAmelCase       )
 return shards_indices_per_group






def 			_SCREAMING_SNAKE_CASE						(     SCREAMING_SNAKE_CASE						:dict       ,       SCREAMING_SNAKE_CASE						:int       )     ->       List[dict]:
 __lowerCAmelCase	:			int         =  _number_of_shards_in_gen_kwargs(_lowerCAmelCase       )
 if num_shards == 1:
  return [dict(_lowerCAmelCase       )]
 else:
  __lowerCAmelCase	:			List[str]         =  _distribute_shards(num_shards=_lowerCAmelCase       ,       max_num_jobs=_lowerCAmelCase       )
  return [
      {
          key: [value[shard_idx] for shard_idx in shard_indices_per_group[group_idx]]
          if isinstance(_lowerCAmelCase       ,       _lowerCAmelCase       )
          else value
          for key, value in gen_kwargs.items()
      }
      for group_idx in range(len(_lowerCAmelCase       )       )
  ]






def 			_SCREAMING_SNAKE_CASE						(     SCREAMING_SNAKE_CASE						:List[dict]       )     ->       dict:
 return {
     key: [value for gen_kwargs in gen_kwargs_list for value in gen_kwargs[key]]
     if isinstance(gen_kwargs_list[0][key]       ,       _lowerCAmelCase       )
     else gen_kwargs_list[0][key]
     for key in gen_kwargs_list[0]
 }







def 			_SCREAMING_SNAKE_CASE						(     SCREAMING_SNAKE_CASE						:np.random.Generator       ,       SCREAMING_SNAKE_CASE						:dict       )     ->       dict:
 __lowerCAmelCase	:			Optional[Any]         =  {len(_lowerCAmelCase       ) for value in gen_kwargs.values() if isinstance(_lowerCAmelCase       ,       _lowerCAmelCase       )}
 __lowerCAmelCase	:			List[Any]         =  {}
 for size in list_sizes:
  __lowerCAmelCase	:			Optional[Any]         =  list(range(_lowerCAmelCase       )       )
  rng.shuffle(indices_per_size[size]       )
 # Now let's copy the gen_kwargs and shuffle the lists based on their sizes
 __lowerCAmelCase	:			str         =  dict(_lowerCAmelCase       )
 for key, value in shuffled_kwargs.items():
  if isinstance(_lowerCAmelCase       ,       _lowerCAmelCase       ):
   __lowerCAmelCase	:			List[Any]         =  [value[i] for i in indices_per_size[len(_lowerCAmelCase       )]]
 return shuffled_kwargs






from collections import defaultdict


class        __magic_name__	:





     """simple docstring"""



     def __init__(				self							:int      ,   snake_case							:Dict      ,   snake_case							:Optional[Any]	):





        '''simple docstring'''




        A_       :					Optional[int]        =      total  # total no of tasks (N)

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

        A_       :					Optional[int]        =      defaultdict(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
        A_       :					Dict        =      (1 << len(snake_case	)) - 1



     def     SCREAMING_SNAKE_CASE		(				self							:Union[str, Any]      ,   snake_case							:Union[str, Any]      ,   snake_case							:str	):





        '''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
        A_       :					Tuple        =      self.count_ways_until(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.
        A_       :					Any        =      total_ways_util

        return self.dp[mask][task_no]





     def     SCREAMING_SNAKE_CASE		(				self							:int      ,   snake_case							:List[str]	):





        '''simple docstring'''




        for i in range(len(snake_case	)	):
           for j in task_performed[i]:
              self.task[j].append(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__":
 _lowerCAmelCase				:   Dict						       =						5  # total no of tasks (the value of N)

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