"""simple docstring"""







from collections import defaultdict



class  _lowerCamelCase			:







				def __init__( self    :       Optional[Any]			,					lowerCamelCase_    :       Tuple			,					lowerCamelCase_    :       int						):

					"""simple docstring"""






					_lowercase :    str							=							total  # total no of tasks (N)

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

					_lowercase :    Tuple							=							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
					_lowercase :    Optional[int]							=							(1 << len(lowerCamelCase_						)) - 1







				def 							__UpperCAmelCase					( self    :       List[Any]			,					lowerCamelCase_    :       Union[str, Any]			,					lowerCamelCase_    :       List[Any]						):

					"""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
					_lowercase :    Union[str, Any]							=							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.
					_lowercase :    List[Any]							=							total_ways_util

					return self.dp[mask][task_no]







				def 							__UpperCAmelCase					( self    :       Tuple			,					lowerCamelCase_    :       str						):

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

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




"""simple docstring"""







def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    str							=							[0 for i in range(len(__UpperCAmelCase			)			)]

	# initialize interval's left pointer and right pointer
	_lowercase				,      _lowercase :    str							=							0, 0

	for i in range(1     ,len(__UpperCAmelCase			)			):
		# case when current index is inside the interval
		if i <= right_pointer:
			_lowercase :    Union[str, Any]							=							min(right_pointer - i + 1     ,z_result[i - left_pointer]			)
			_lowercase :    Any							=							min_edge

		while go_next(__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):
			z_result[i] += 1

		# if new index's result gives us more right interval,
		# we've to update left_pointer and right_pointer
		if i + z_result[i] - 1 > right_pointer:
			_lowercase				,      _lowercase :    Optional[int]							=							i, i + z_result[i] - 1

	return z_result


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	return i + z_result[i] < len(__UpperCAmelCase			) and s[z_result[i]] == s[i + z_result[i]]


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Union[str, Any]							=							0
	# concatenate 'pattern' and 'input_str' and call z_function
	# with concatenated string
	_lowercase :    List[str]							=							z_function(pattern + input_str			)

	for val in z_result:
		# if value is greater then length of the pattern string
		# that means this index is starting position of substring
		# which is equal to pattern string
		if val >= len(__UpperCAmelCase			):
			answer += 1

	return answer


if __name__ == "__main__":
						import doctest

						doctest.testmod()



