

"""simple docstring"""
from collections import defaultdict

class       lowerCamelCase	:


  '''simple docstring'''







  def __init__(self							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

        UpperCAmelCase__			:							Dict							=    total  # total no of tasks (N)

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

        UpperCAmelCase__			:							str							=    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
        UpperCAmelCase__			:							List[str]							=    (1 << len(_lowerCamelCase	)) - 1



  def  _a      (self							,       _lowerCamelCase							,       _lowerCamelCase	):


        """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__			:							Dict							=    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.
        UpperCAmelCase__			:							Dict							=    total_ways_util

        return self.dp[mask][task_no]




  def  _a      (self							,       _lowerCamelCase	):


        """simple docstring"""

        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__":
    _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
        )
    )




"""simple docstring"""
from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


_A							=  {"""configuration_sew""": ["""SEW_PRETRAINED_CONFIG_ARCHIVE_MAP""", """SEWConfig"""]}

try:
    if not is_torch_available():
        raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
    pass
else:
    _A							=  [
        """SEW_PRETRAINED_MODEL_ARCHIVE_LIST""",
        """SEWForCTC""",
        """SEWForSequenceClassification""",
        """SEWModel""",
        """SEWPreTrainedModel""",
    ]

if TYPE_CHECKING:
    from .configuration_sew import SEW_PRETRAINED_CONFIG_ARCHIVE_MAP, SEWConfig

    try:
        if not is_torch_available():
            raise OptionalDependencyNotAvailable()
    except OptionalDependencyNotAvailable:
        pass
    else:
        from .modeling_sew import (
            SEW_PRETRAINED_MODEL_ARCHIVE_LIST,
            SEWForCTC,
            SEWForSequenceClassification,
            SEWModel,
            SEWPreTrainedModel,
        )


else:
    import sys

    _A							=  _LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)

