"""simple docstring"""




from collections import defaultdict

class    a_   :




					def __init__(						self    :  Tuple	,    snake_case__    :  Any	,    snake_case__    :  Union[str, Any]  ):
							lowerCAmelCase__   = total  # total no of tasks (N)

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

							lowerCAmelCase__   = 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
							lowerCAmelCase__   = (1 << len(snake_case__  )) - 1




					def     _SCREAMING_SNAKE_CASE    (						self    :  Dict	,    snake_case__    :  List[str]	,    snake_case__    :  Optional[Any]  ):
							# 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
							lowerCAmelCase__   = 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.
							lowerCAmelCase__   = total_ways_util

							return self.dp[mask][task_no]




					def     _SCREAMING_SNAKE_CASE    (						self    :  Any	,    snake_case__    :  List[str]  ):
							# Store the list of persons for each task
							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     :				List[Any]    				=    5  # total no of tasks (the value of N)

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





"""simple docstring"""




import json
import os
import unittest

from transformers import MgpstrTokenizer
from transformers.models.mgp_str.tokenization_mgp_str import VOCAB_FILES_NAMES
from transformers.testing_utils import require_tokenizers

from ...test_tokenization_common import TokenizerTesterMixin

@require_tokenizers
class    a_   (  __UpperCamelCase			,		unittest.TestCase      ):
					UpperCamelCase_			:						Optional[int]      =     MgpstrTokenizer
					UpperCamelCase_			:						Optional[int]      =     False
					UpperCamelCase_			:						Tuple      =     {}
					UpperCamelCase_			:						List[str]      =     False




					def     _SCREAMING_SNAKE_CASE    (						self    :  Dict  ):
							super().setUp()

							# fmt: off
							lowerCAmelCase__   = ["""[GO]""", """[s]""", """0""", """1""", """2""", """3""", """4""", """5""", """6""", """7""", """8""", """9""", """a""", """b""", """c""", """d""", """e""", """f""", """g""", """h""", """i""", """j""", """k""", """l""", """m""", """n""", """o""", """p""", """q""", """r""", """s""", """t""", """u""", """v""", """w""", """x""", """y""", """z"""]
							# fmt: on
							lowerCAmelCase__   = dict(zip(snake_case__	,    range(len(snake_case__  )  )  )  )

							lowerCAmelCase__   = os.path.join(self.tmpdirname	,    VOCAB_FILES_NAMES["""vocab_file"""]  )
							with open(self.vocab_file	,    """w"""	,    encoding="""utf-8"""  ) as fp:
									fp.write(json.dumps(snake_case__  ) + """\n"""  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  int	,    **snake_case__    :  Tuple  ):
							return MgpstrTokenizer.from_pretrained(self.tmpdirname	,    **snake_case__  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  List[str]	,    snake_case__    :  Dict  ):
							lowerCAmelCase__   = """tester"""
							lowerCAmelCase__   = """tester"""
							return input_text, output_text




					@unittest.skip("""MGP-STR always lower cases letters."""  )
					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]  ):
							pass




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]  ):
							lowerCAmelCase__   = self.get_tokenizers(do_lower_case=snake_case__  )
							for tokenizer in tokenizers:
									with self.subTest(F"""{tokenizer.__class__.__name__}"""  ):
											lowerCAmelCase__   = """[SPECIAL_TOKEN]"""

											tokenizer.add_special_tokens({"""cls_token""": special_token}  )
											lowerCAmelCase__   = tokenizer.encode([special_token]	,    add_special_tokens=snake_case__  )
											self.assertEqual(len(snake_case__  )	,    1  )

											lowerCAmelCase__   = tokenizer.decode(snake_case__	,    skip_special_tokens=snake_case__  )
											self.assertTrue(special_token not in decoded  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  List[str]  ):
							lowerCAmelCase__   = self.get_tokenizers()
							for tokenizer in tokenizers:
									with self.subTest(F"""{tokenizer.__class__.__name__}"""  ):
											lowerCAmelCase__ ,       lowerCAmelCase__   = self.get_input_output_texts(snake_case__  )

											lowerCAmelCase__   = tokenizer.tokenize(snake_case__  )
											lowerCAmelCase__   = tokenizer.convert_tokens_to_ids(snake_case__  )
											lowerCAmelCase__   = tokenizer.encode(snake_case__	,    add_special_tokens=snake_case__  )
											self.assertListEqual(snake_case__	,    snake_case__  )

											lowerCAmelCase__   = tokenizer.convert_ids_to_tokens(snake_case__  )
											self.assertNotEqual(len(snake_case__  )	,    0  )
											lowerCAmelCase__   = tokenizer.decode(snake_case__  )
											self.assertIsInstance(snake_case__	,    snake_case__  )

											self.assertEqual(text_a.replace(""" """	,    """"""  )	,    snake_case__  )




					@unittest.skip("""MGP-STR tokenizer only handles one sequence."""  )
					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[Any]  ):
							pass




					@unittest.skip("""inputs cannot be pretokenized in MgpstrTokenizer"""  )
					def     _SCREAMING_SNAKE_CASE    (						self    :  List[Any]  ):
							pass




