



"""simple docstring"""






from __future__ import annotations

import math
import random
from collections.abc import Collection
from typing import overload

class 	__SCREAMING_SNAKE_CASE     :


					'''simple docstring'''





					def __init__(	self							:  Any,  lowerCamelCase							:  Collection[float] | None = None					)-> None:
								if components is None:
											lowerCamelCase__		:		Optional[Any]		     =[]
								lowerCamelCase__		:		Optional[int]		     =list(lowerCamelCase					)



					def __len__(	self							:  Union[str, Any]					)-> int:
								return len(self.__components					)



					def __str__(	self							:  Dict					)-> str:
								return "(" + ",".join(map(lowerCamelCase,  self.__components					)					) + ")"



					def __add__(	self							:  Union[str, Any],  lowerCamelCase							:  Vector					)-> Vector:
								lowerCamelCase__		:		Optional[int]		     =len(self					)
								if size == len(lowerCamelCase					):
											lowerCamelCase__		:		Any		     =[self.__components[i] + other.component(lowerCamelCase					) for i in range(lowerCamelCase					)]
											return Vector(lowerCamelCase					)
								else:
											raise Exception('''must have the same size'''					)



					def __sub__(	self							:  int,  lowerCamelCase							:  Vector					)-> Vector:
								lowerCamelCase__		:		Optional[int]		     =len(self					)
								if size == len(lowerCamelCase					):
											lowerCamelCase__		:		Dict		     =[self.__components[i] - other.component(lowerCamelCase					) for i in range(lowerCamelCase					)]
											return Vector(lowerCamelCase					)
								else:  # error case
											raise Exception('''must have the same size'''					)



					@overload
					def __mul__(	self							:  Dict,  lowerCamelCase							:  float					)-> Vector:
								...



					@overload
					def __mul__(	self							:  List[Any],  lowerCamelCase							:  Vector					)-> float:
								...



					def __mul__(	self							:  Tuple,  lowerCamelCase							:  float | Vector					)-> float | Vector:
								if isinstance(lowerCamelCase,  (float, int)					):
											lowerCamelCase__		:		Optional[Any]		     =[c * other for c in self.__components]
											return Vector(lowerCamelCase					)
								elif isinstance(lowerCamelCase,  lowerCamelCase					) and len(self					) == len(lowerCamelCase					):
											lowerCamelCase__		:		str		     =len(self					)
											lowerCamelCase__		:		Optional[Any]		     =[self.__components[i] * other.component(lowerCamelCase					) for i in range(lowerCamelCase					)]
											return sum(lowerCamelCase					)
								else:  # error case
											raise Exception('''invalid operand!'''					)



					def 		snake_case	(	self							:  Dict					)-> Vector:
								return Vector(self.__components					)



					def 		snake_case	(	self							:  Optional[int],  lowerCamelCase							:  int					)-> float:
								if isinstance(lowerCamelCase,  lowerCamelCase					) and -len(self.__components					) <= i < len(self.__components					):
											return self.__components[i]
								else:
											raise Exception('''index out of range'''					)



					def 		snake_case	(	self							:  Optional[Any],  lowerCamelCase							:  int,  lowerCamelCase							:  float					)-> None:
								assert -len(self.__components					) <= pos < len(self.__components					)
								lowerCamelCase__		:		Union[str, Any]		     =value



					def 		snake_case	(	self							:  Any					)-> float:
								if len(self.__components					) == 0:
											raise Exception('''Vector is empty'''					)
								lowerCamelCase__		:		Union[str, Any]		     =[c**2 for c in self.__components]
								return math.sqrt(sum(lowerCamelCase					)					)




					def 		snake_case	(	self							:  Dict,  lowerCamelCase							:  Vector,  lowerCamelCase							:  bool = False					)-> float:
								lowerCamelCase__		:		List[Any]		     =self * other
								lowerCamelCase__		:		List[Any]		     =self.euclidean_length() * other.euclidean_length()
								if deg:
											return math.degrees(math.acos(num / den					)					)
								else:
											return math.acos(num / den					)






def 					snake_case__       (		__lowerCamelCase    :   int     ):
			"""simple docstring"""
			assert isinstance(__lowerCamelCase							,		__lowerCamelCase     )
			return Vector([0] * dimension     )






def 					snake_case__       (		__lowerCamelCase    :   int							,		__lowerCamelCase    :   int     ):
			"""simple docstring"""
			assert isinstance(__lowerCamelCase							,		__lowerCamelCase     ) and (isinstance(__lowerCamelCase							,		__lowerCamelCase     ))
			lowerCamelCase__		:		Optional[Any]		     =[0] * dimension
			lowerCamelCase__		:		Optional[Any]		     =1
			return Vector(__lowerCamelCase     )






def 					snake_case__       (		__lowerCamelCase    :   float							,		__lowerCamelCase    :   Vector							,		__lowerCamelCase    :   Vector     ):
			"""simple docstring"""
			assert (
			    isinstance(__lowerCamelCase							,		__lowerCamelCase     )
			    and isinstance(__lowerCamelCase							,		__lowerCamelCase     )
			    and (isinstance(__lowerCamelCase							,		(int, float)     ))
			)
			return x * scalar + y






def 					snake_case__       (		__lowerCamelCase    :   int							,		__lowerCamelCase    :   int							,		__lowerCamelCase    :   int     ):
			"""simple docstring"""
			random.seed(__lowerCamelCase     )
			lowerCamelCase__		:		Union[str, Any]		     =[random.randint(__lowerCamelCase							,		__lowerCamelCase     ) for _ in range(__lowerCamelCase     )]
			return Vector(__lowerCamelCase     )

class 	__SCREAMING_SNAKE_CASE     :


					'''simple docstring'''





					def __init__(	self							:  str,  lowerCamelCase							:  list[list[float]],  lowerCamelCase							:  int,  lowerCamelCase							:  int					)-> None:
								lowerCamelCase__		:		Any		     =matrix
								lowerCamelCase__		:		List[str]		     =w
								lowerCamelCase__		:		Dict		     =h



					def __str__(	self							:  str					)-> str:
								lowerCamelCase__		:		List[Any]		     =''''''
								for i in range(self.__height					):
											ans += "|"
											for j in range(self.__width					):
														if j < self.__width - 1:
																	ans += str(self.__matrix[i][j]					) + ","
														else:
																	ans += str(self.__matrix[i][j]					) + "|\n"
								return ans



					def __add__(	self							:  str,  lowerCamelCase							:  Matrix					)-> Matrix:
								if self.__width == other.width() and self.__height == other.height():
											lowerCamelCase__		:		Dict		     =[]
											for i in range(self.__height					):
														lowerCamelCase__		:		Dict		     =[
														    self.__matrix[i][j] + other.component(lowerCamelCase,  lowerCamelCase					)
														    for j in range(self.__width					)
														]
														matrix.append(lowerCamelCase					)
											return Matrix(lowerCamelCase,  self.__width,  self.__height					)
								else:
											raise Exception('''matrix must have the same dimension!'''					)



					def __sub__(	self							:  List[str],  lowerCamelCase							:  Matrix					)-> Matrix:
								if self.__width == other.width() and self.__height == other.height():
											lowerCamelCase__		:		int		     =[]
											for i in range(self.__height					):
														lowerCamelCase__		:		Union[str, Any]		     =[
														    self.__matrix[i][j] - other.component(lowerCamelCase,  lowerCamelCase					)
														    for j in range(self.__width					)
														]
														matrix.append(lowerCamelCase					)
											return Matrix(lowerCamelCase,  self.__width,  self.__height					)
								else:
											raise Exception('''matrices must have the same dimension!'''					)



					@overload
					def __mul__(	self							:  Dict,  lowerCamelCase							:  float					)-> Matrix:
								...



					@overload
					def __mul__(	self							:  Any,  lowerCamelCase							:  Vector					)-> Vector:
								...



					def __mul__(	self							:  Optional[int],  lowerCamelCase							:  float | Vector					)-> Vector | Matrix:
								if isinstance(lowerCamelCase,  lowerCamelCase					):  # matrix-vector
											if len(lowerCamelCase					) == self.__width:
														lowerCamelCase__		:		Tuple		     =zero_vector(self.__height					)
														for i in range(self.__height					):
																	lowerCamelCase__		:		Dict		     =[
																	    self.__matrix[i][j] * other.component(lowerCamelCase					)
																	    for j in range(self.__width					)
																	]
																	ans.change_component(lowerCamelCase,  sum(lowerCamelCase					)					)
														return ans
											else:
														raise Exception(
														    '''vector must have the same size as the '''
														    '''number of columns of the matrix!'''					)
								elif isinstance(lowerCamelCase,  (int, float)					):  # matrix-scalar
											lowerCamelCase__		:		Optional[Any]		     =[
											    [self.__matrix[i][j] * other for j in range(self.__width					)]
											    for i in range(self.__height					)
											]
											return Matrix(lowerCamelCase,  self.__width,  self.__height					)
								return None



					def 		snake_case	(	self							:  Tuple					)-> int:
								return self.__height



					def 		snake_case	(	self							:  List[Any]					)-> int:
								return self.__width



					def 		snake_case	(	self							:  Optional[int],  lowerCamelCase							:  int,  lowerCamelCase							:  int					)-> float:
								if 0 <= x < self.__height and 0 <= y < self.__width:
											return self.__matrix[x][y]
								else:
											raise Exception('''change_component: indices out of bounds'''					)



					def 		snake_case	(	self							:  List[str],  lowerCamelCase							:  int,  lowerCamelCase							:  int,  lowerCamelCase							:  float					)-> None:
								if 0 <= x < self.__height and 0 <= y < self.__width:
											lowerCamelCase__		:		str		     =value
								else:
											raise Exception('''change_component: indices out of bounds'''					)



					def 		snake_case	(	self							:  Optional[int],  lowerCamelCase							:  int,  lowerCamelCase							:  int					)-> float:
								if self.__height != self.__width:
											raise Exception('''Matrix is not square'''					)
								lowerCamelCase__		:		Optional[Any]		     =self.__matrix[:x] + self.__matrix[x + 1 :]
								for i in range(len(lowerCamelCase					)					):
											lowerCamelCase__		:		str		     =minor[i][:y] + minor[i][y + 1 :]
								return Matrix(lowerCamelCase,  self.__width - 1,  self.__height - 1					).determinant()



					def 		snake_case	(	self							:  int,  lowerCamelCase							:  int,  lowerCamelCase							:  int					)-> float:
								if self.__height != self.__width:
											raise Exception('''Matrix is not square'''					)
								if 0 <= x < self.__height and 0 <= y < self.__width:
											return (-1) ** (x + y) * self.minor(lowerCamelCase,  lowerCamelCase					)
								else:
											raise Exception('''Indices out of bounds'''					)




					def 		snake_case	(	self							:  str					)-> float:
								if self.__height != self.__width:
											raise Exception('''Matrix is not square'''					)
								if self.__height < 1:
											raise Exception('''Matrix has no element'''					)
								elif self.__height == 1:
											return self.__matrix[0][0]
								elif self.__height == 2:
											return (
											    self.__matrix[0][0] * self.__matrix[1][1]
											    - self.__matrix[0][1] * self.__matrix[1][0]
											)
								else:
											lowerCamelCase__		:		Dict		     =[
											    self.__matrix[0][y] * self.cofactor(0,  lowerCamelCase					) for y in range(self.__width					)
											]
											return sum(lowerCamelCase					)






def 					snake_case__       (		__lowerCamelCase    :   int     ):
			"""simple docstring"""
			lowerCamelCase__		:		list[list[float]]		     =[[0] * n for _ in range(__lowerCamelCase     )]
			return Matrix(__lowerCamelCase							,		__lowerCamelCase							,		__lowerCamelCase     )






def 					snake_case__       (		__lowerCamelCase    :   int							,		__lowerCamelCase    :   int							,		__lowerCamelCase    :   int							,		__lowerCamelCase    :   int     ):
			"""simple docstring"""
			random.seed(__lowerCamelCase     )
			lowerCamelCase__		:		list[list[float]]		     =[
			    [random.randint(__lowerCamelCase							,		__lowerCamelCase     ) for _ in range(__lowerCamelCase     )] for _ in range(__lowerCamelCase     )
			]
			return Matrix(__lowerCamelCase							,		__lowerCamelCase							,		__lowerCamelCase     )









"""simple docstring"""






from collections import defaultdict

class 	__SCREAMING_SNAKE_CASE     :


					'''simple docstring'''





					def __init__(	self							:  Union[str, Any],  lowerCamelCase							:  List[Any],  lowerCamelCase							:  List[str]					)-> Optional[int]:
								lowerCamelCase__		:		List[Any]		     =total  # total no of tasks (N)

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

								lowerCamelCase__		:		Any		     =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
								lowerCamelCase__		:		List[Any]		     =(1 << len(lowerCamelCase					)) - 1



					def 		snake_case	(	self							:  int,  lowerCamelCase							:  str,  lowerCamelCase							:  Any					)-> 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__		:		Optional[int]		     =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.
								lowerCamelCase__		:		int		     =total_ways_util

								return self.dp[mask][task_no]




					def 		snake_case	(	self							:  Dict,  lowerCamelCase							:  Dict					)-> int:
								# 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__":
		_lowercase			:			Tuple										=						5  # total no of tasks (the value of N)

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




