



"""simple docstring"""






import argparse
import json
import pickle
from pathlib import Path

import requests
import torch
from huggingface_hub import hf_hub_download
from PIL import Image

from transformers import MaskFormerConfig, MaskFormerForInstanceSegmentation, MaskFormerImageProcessor, SwinConfig
from transformers.utils import logging


logging.set_verbosity_info()
_lowercase			:			Optional[int]										=      logging.get_logger(__name__)






def 					snake_case__       (		__lowerCamelCase    :   str     ):
			"""simple docstring"""
			lowerCamelCase__		:		List[str]		     =SwinConfig.from_pretrained(
			    '''microsoft/swin-tiny-patch4-window7-224'''							,		out_features=['''stage1''', '''stage2''', '''stage3''', '''stage4''']     )
			lowerCamelCase__		:		List[str]		     =MaskFormerConfig(backbone_config=__lowerCamelCase     )

			lowerCamelCase__		:		int		     ="huggingface/label-files"
			if "ade20k-full" in model_name:
						# this should be ok
						lowerCamelCase__		:		Any		     =847
						lowerCamelCase__		:		Union[str, Any]		     ="maskformer-ade20k-full-id2label.json"
			elif "ade" in model_name:
						# this should be ok
						lowerCamelCase__		:		Union[str, Any]		     =150
						lowerCamelCase__		:		Union[str, Any]		     ="ade20k-id2label.json"
			elif "coco-stuff" in model_name:
						# this should be ok
						lowerCamelCase__		:		List[Any]		     =171
						lowerCamelCase__		:		Any		     ="maskformer-coco-stuff-id2label.json"
			elif "coco" in model_name:
						# TODO
						lowerCamelCase__		:		Tuple		     =133
						lowerCamelCase__		:		Any		     ="coco-panoptic-id2label.json"
			elif "cityscapes" in model_name:
						# this should be ok
						lowerCamelCase__		:		int		     =19
						lowerCamelCase__		:		str		     ="cityscapes-id2label.json"
			elif "vistas" in model_name:
						# this should be ok
						lowerCamelCase__		:		str		     =65
						lowerCamelCase__		:		Dict		     ="mapillary-vistas-id2label.json"

			lowerCamelCase__		:		str		     =json.load(open(hf_hub_download(__lowerCamelCase							,		__lowerCamelCase							,		repo_type='''dataset'''     )							,		'''r'''     )     )
			lowerCamelCase__		:		int		     ={int(__lowerCamelCase     ): v for k, v in idalabel.items()}

			return config






def 					snake_case__       (		__lowerCamelCase    :   Tuple     ):
			"""simple docstring"""
			lowerCamelCase__		:		Union[str, Any]		     =[]
			# stem
			# fmt: off
			rename_keys.append(('''backbone.patch_embed.proj.weight''', '''model.pixel_level_module.encoder.model.embeddings.patch_embeddings.projection.weight''')     )
			rename_keys.append(('''backbone.patch_embed.proj.bias''', '''model.pixel_level_module.encoder.model.embeddings.patch_embeddings.projection.bias''')     )
			rename_keys.append(('''backbone.patch_embed.norm.weight''', '''model.pixel_level_module.encoder.model.embeddings.norm.weight''')     )
			rename_keys.append(('''backbone.patch_embed.norm.bias''', '''model.pixel_level_module.encoder.model.embeddings.norm.bias''')     )
			# stages
			for i in range(len(config.backbone_config.depths     )     ):
						for j in range(config.backbone_config.depths[i]     ):
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.norm1.weight''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_before.weight''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.norm1.bias''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_before.bias''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.attn.relative_position_bias_table''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.self.relative_position_bias_table''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.attn.relative_position_index''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.self.relative_position_index''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.attn.proj.weight''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.output.dense.weight''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.attn.proj.bias''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.attention.output.dense.bias''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.norm2.weight''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_after.weight''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.norm2.bias''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.layernorm_after.bias''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.mlp.fc1.weight''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.intermediate.dense.weight''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.mlp.fc1.bias''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.intermediate.dense.bias''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.mlp.fc2.weight''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.output.dense.weight''')     )
									rename_keys.append((f'''backbone.layers.{i}.blocks.{j}.mlp.fc2.bias''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.blocks.{j}.output.dense.bias''')     )

						if i < 3:
									rename_keys.append((f'''backbone.layers.{i}.downsample.reduction.weight''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.downsample.reduction.weight''')     )
									rename_keys.append((f'''backbone.layers.{i}.downsample.norm.weight''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.downsample.norm.weight''')     )
									rename_keys.append((f'''backbone.layers.{i}.downsample.norm.bias''', f'''model.pixel_level_module.encoder.model.encoder.layers.{i}.downsample.norm.bias''')     )
						rename_keys.append((f'''backbone.norm{i}.weight''', f'''model.pixel_level_module.encoder.hidden_states_norms.{i}.weight''')     )
						rename_keys.append((f'''backbone.norm{i}.bias''', f'''model.pixel_level_module.encoder.hidden_states_norms.{i}.bias''')     )

			# FPN
			rename_keys.append(('''sem_seg_head.layer_4.weight''', '''model.pixel_level_module.decoder.fpn.stem.0.weight''')     )
			rename_keys.append(('''sem_seg_head.layer_4.norm.weight''', '''model.pixel_level_module.decoder.fpn.stem.1.weight''')     )
			rename_keys.append(('''sem_seg_head.layer_4.norm.bias''', '''model.pixel_level_module.decoder.fpn.stem.1.bias''')     )
			for source_index, target_index in zip(range(3							,		0							,		-1     )							,		range(0							,		3     )     ):
						rename_keys.append((f'''sem_seg_head.adapter_{source_index}.weight''', f'''model.pixel_level_module.decoder.fpn.layers.{target_index}.proj.0.weight''')     )
						rename_keys.append((f'''sem_seg_head.adapter_{source_index}.norm.weight''', f'''model.pixel_level_module.decoder.fpn.layers.{target_index}.proj.1.weight''')     )
						rename_keys.append((f'''sem_seg_head.adapter_{source_index}.norm.bias''', f'''model.pixel_level_module.decoder.fpn.layers.{target_index}.proj.1.bias''')     )
						rename_keys.append((f'''sem_seg_head.layer_{source_index}.weight''', f'''model.pixel_level_module.decoder.fpn.layers.{target_index}.block.0.weight''')     )
						rename_keys.append((f'''sem_seg_head.layer_{source_index}.norm.weight''', f'''model.pixel_level_module.decoder.fpn.layers.{target_index}.block.1.weight''')     )
						rename_keys.append((f'''sem_seg_head.layer_{source_index}.norm.bias''', f'''model.pixel_level_module.decoder.fpn.layers.{target_index}.block.1.bias''')     )
			rename_keys.append(('''sem_seg_head.mask_features.weight''', '''model.pixel_level_module.decoder.mask_projection.weight''')     )
			rename_keys.append(('''sem_seg_head.mask_features.bias''', '''model.pixel_level_module.decoder.mask_projection.bias''')     )

			# Transformer decoder
			for idx in range(config.decoder_config.decoder_layers     ):
						# self-attention out projection
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.out_proj.weight''', f'''model.transformer_module.decoder.layers.{idx}.self_attn.out_proj.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.out_proj.bias''', f'''model.transformer_module.decoder.layers.{idx}.self_attn.out_proj.bias''')     )
						# cross-attention out projection
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.out_proj.weight''', f'''model.transformer_module.decoder.layers.{idx}.encoder_attn.out_proj.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.out_proj.bias''', f'''model.transformer_module.decoder.layers.{idx}.encoder_attn.out_proj.bias''')     )
						# MLP 1
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear1.weight''', f'''model.transformer_module.decoder.layers.{idx}.fc1.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear1.bias''', f'''model.transformer_module.decoder.layers.{idx}.fc1.bias''')     )
						# MLP 2
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear2.weight''', f'''model.transformer_module.decoder.layers.{idx}.fc2.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.linear2.bias''', f'''model.transformer_module.decoder.layers.{idx}.fc2.bias''')     )
						# layernorm 1 (self-attention layernorm)
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm1.weight''', f'''model.transformer_module.decoder.layers.{idx}.self_attn_layer_norm.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm1.bias''', f'''model.transformer_module.decoder.layers.{idx}.self_attn_layer_norm.bias''')     )
						# layernorm 2 (cross-attention layernorm)
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm2.weight''', f'''model.transformer_module.decoder.layers.{idx}.encoder_attn_layer_norm.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm2.bias''', f'''model.transformer_module.decoder.layers.{idx}.encoder_attn_layer_norm.bias''')     )
						# layernorm 3 (final layernorm)
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm3.weight''', f'''model.transformer_module.decoder.layers.{idx}.final_layer_norm.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.norm3.bias''', f'''model.transformer_module.decoder.layers.{idx}.final_layer_norm.bias''')     )

			rename_keys.append(('''sem_seg_head.predictor.transformer.decoder.norm.weight''', '''model.transformer_module.decoder.layernorm.weight''')     )
			rename_keys.append(('''sem_seg_head.predictor.transformer.decoder.norm.bias''', '''model.transformer_module.decoder.layernorm.bias''')     )

			# heads on top
			rename_keys.append(('''sem_seg_head.predictor.query_embed.weight''', '''model.transformer_module.queries_embedder.weight''')     )

			rename_keys.append(('''sem_seg_head.predictor.input_proj.weight''', '''model.transformer_module.input_projection.weight''')     )
			rename_keys.append(('''sem_seg_head.predictor.input_proj.bias''', '''model.transformer_module.input_projection.bias''')     )

			rename_keys.append(('''sem_seg_head.predictor.class_embed.weight''', '''class_predictor.weight''')     )
			rename_keys.append(('''sem_seg_head.predictor.class_embed.bias''', '''class_predictor.bias''')     )

			for i in range(3     ):
						rename_keys.append((f'''sem_seg_head.predictor.mask_embed.layers.{i}.weight''', f'''mask_embedder.{i}.0.weight''')     )
						rename_keys.append((f'''sem_seg_head.predictor.mask_embed.layers.{i}.bias''', f'''mask_embedder.{i}.0.bias''')     )
			# fmt: on

			return rename_keys






def 					snake_case__       (		__lowerCamelCase    :   List[Any]							,		__lowerCamelCase    :   int							,		__lowerCamelCase    :   Optional[Any]     ):
			"""simple docstring"""
			lowerCamelCase__		:		int		     =dct.pop(__lowerCamelCase     )
			lowerCamelCase__		:		int		     =val






def 					snake_case__       (		__lowerCamelCase    :   Union[str, Any]							,		__lowerCamelCase    :   Dict     ):
			"""simple docstring"""
			lowerCamelCase__		:		Optional[int]		     =[int(backbone_config.embed_dim * 2**i     ) for i in range(len(backbone_config.depths     )     )]
			for i in range(len(backbone_config.depths     )     ):
						lowerCamelCase__		:		str		     =num_features[i]
						for j in range(backbone_config.depths[i]     ):
									# fmt: off
									# read in weights + bias of input projection layer (in original implementation, this is a single matrix + bias)
									lowerCamelCase__		:		Union[str, Any]		     =state_dict.pop(f'''backbone.layers.{i}.blocks.{j}.attn.qkv.weight'''     )
									lowerCamelCase__		:		Optional[Any]		     =state_dict.pop(f'''backbone.layers.{i}.blocks.{j}.attn.qkv.bias'''     )
									# next, add query, keys and values (in that order) to the state dict
									lowerCamelCase__		:		Union[str, Any]		     =in_proj_weight[:dim, :]
									lowerCamelCase__		:		List[Any]		     =in_proj_bias[: dim]
									lowerCamelCase__		:		Tuple		     =in_proj_weight[
									    dim : dim * 2, :
									]
									lowerCamelCase__		:		Dict		     =in_proj_bias[
									    dim : dim * 2
									]
									lowerCamelCase__		:		List[str]		     =in_proj_weight[
									    -dim :, :
									]
									lowerCamelCase__		:		List[Any]		     =in_proj_bias[-dim :]
									# fmt: on






def 					snake_case__       (		__lowerCamelCase    :   Any							,		__lowerCamelCase    :   Tuple     ):
			"""simple docstring"""
			# fmt: off
			lowerCamelCase__		:		int		     =config.decoder_config.hidden_size
			for idx in range(config.decoder_config.decoder_layers     ):
						# read in weights + bias of self-attention input projection layer (in the original implementation, this is a single matrix + bias)
						lowerCamelCase__		:		int		     =state_dict.pop(f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.in_proj_weight'''     )
						lowerCamelCase__		:		Union[str, Any]		     =state_dict.pop(f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.self_attn.in_proj_bias'''     )
						# next, add query, keys and values (in that order) to the state dict
						lowerCamelCase__		:		str		     =in_proj_weight[: hidden_size, :]
						lowerCamelCase__		:		Dict		     =in_proj_bias[:config.hidden_size]
						lowerCamelCase__		:		Dict		     =in_proj_weight[hidden_size : hidden_size * 2, :]
						lowerCamelCase__		:		Dict		     =in_proj_bias[hidden_size : hidden_size * 2]
						lowerCamelCase__		:		List[Any]		     =in_proj_weight[-hidden_size :, :]
						lowerCamelCase__		:		int		     =in_proj_bias[-hidden_size :]
						# read in weights + bias of cross-attention input projection layer (in the original implementation, this is a single matrix + bias)
						lowerCamelCase__		:		List[str]		     =state_dict.pop(f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.in_proj_weight'''     )
						lowerCamelCase__		:		Any		     =state_dict.pop(f'''sem_seg_head.predictor.transformer.decoder.layers.{idx}.multihead_attn.in_proj_bias'''     )
						# next, add query, keys and values (in that order) to the state dict
						lowerCamelCase__		:		Union[str, Any]		     =in_proj_weight[: hidden_size, :]
						lowerCamelCase__		:		List[str]		     =in_proj_bias[:config.hidden_size]
						lowerCamelCase__		:		Union[str, Any]		     =in_proj_weight[hidden_size : hidden_size * 2, :]
						lowerCamelCase__		:		List[str]		     =in_proj_bias[hidden_size : hidden_size * 2]
						lowerCamelCase__		:		List[Any]		     =in_proj_weight[-hidden_size :, :]
						lowerCamelCase__		:		List[Any]		     =in_proj_bias[-hidden_size :]
			# fmt: on






def 					snake_case__       (		):
			"""simple docstring"""
			lowerCamelCase__		:		List[str]		     ="http://images.cocodataset.org/val2017/000000039769.jpg"
			lowerCamelCase__		:		Tuple		     =Image.open(requests.get(__lowerCamelCase							,		stream=__lowerCamelCase     ).raw     )
			return im






@torch.no_grad()
def 					snake_case__       (		__lowerCamelCase    :   str							,		__lowerCamelCase    :   str							,		__lowerCamelCase    :   str							,		__lowerCamelCase    :   bool = False     ):
			"""simple docstring"""
			lowerCamelCase__		:		int		     =get_maskformer_config(__lowerCamelCase     )

			# load original state_dict
			with open(__lowerCamelCase							,		'''rb'''     ) as f:
						lowerCamelCase__		:		Union[str, Any]		     =pickle.load(__lowerCamelCase     )
			lowerCamelCase__		:		Union[str, Any]		     =data["model"]

			# for name, param in state_dict.items():
			#     print(name, param.shape)

			# rename keys
			lowerCamelCase__		:		Optional[int]		     =create_rename_keys(__lowerCamelCase     )
			for src, dest in rename_keys:
						rename_key(__lowerCamelCase							,		__lowerCamelCase							,		__lowerCamelCase     )
			read_in_swin_q_k_v(__lowerCamelCase							,		config.backbone_config     )
			read_in_decoder_q_k_v(__lowerCamelCase							,		__lowerCamelCase     )

			# update to torch tensors
			for key, value in state_dict.items():
						lowerCamelCase__		:		Dict		     =torch.from_numpy(__lowerCamelCase     )

			# load 🤗 model
			lowerCamelCase__		:		List[Any]		     =MaskFormerForInstanceSegmentation(__lowerCamelCase     )
			model.eval()

			for name, param in model.named_parameters():
						print(__lowerCamelCase							,		param.shape     )

			lowerCamelCase__		:		str		     =model.load_state_dict(__lowerCamelCase							,		strict=__lowerCamelCase     )
			assert missing_keys == [
			    "model.pixel_level_module.encoder.model.layernorm.weight",
			    "model.pixel_level_module.encoder.model.layernorm.bias",
			]
			assert len(__lowerCamelCase     ) == 0, f'''Unexpected keys: {unexpected_keys}'''

			# verify results
			lowerCamelCase__		:		Any		     =prepare_img()
			if "vistas" in model_name:
						lowerCamelCase__		:		int		     =65
			elif "cityscapes" in model_name:
						lowerCamelCase__		:		int		     =65535
			else:
						lowerCamelCase__		:		str		     =255
			lowerCamelCase__		:		Dict		     =True if "ade" in model_name else False
			lowerCamelCase__		:		Any		     =MaskFormerImageProcessor(ignore_index=__lowerCamelCase							,		reduce_labels=__lowerCamelCase     )

			lowerCamelCase__		:		List[Any]		     =image_processor(__lowerCamelCase							,		return_tensors='''pt'''     )

			lowerCamelCase__		:		Any		     =model(**__lowerCamelCase     )

			print('''Logits:'''							,		outputs.class_queries_logits[0, :3, :3]     )

			if model_name == "maskformer-swin-tiny-ade":
						lowerCamelCase__		:		List[str]		     =torch.tensor(
						    [[3.63_53, -4.47_70, -2.60_65], [0.50_81, -4.23_94, -3.53_43], [2.19_09, -5.03_53, -1.93_23]]     )
			assert torch.allclose(outputs.class_queries_logits[0, :3, :3]							,		__lowerCamelCase							,		atol=1e-4     )
			print('''Looks ok!'''     )

			if pytorch_dump_folder_path is not None:
						print(f'''Saving model and image processor to {pytorch_dump_folder_path}'''     )
						Path(__lowerCamelCase     ).mkdir(exist_ok=__lowerCamelCase     )
						model.save_pretrained(__lowerCamelCase     )
						image_processor.save_pretrained(__lowerCamelCase     )

			if push_to_hub:
						print('''Pushing model and image processor to the hub...'''     )
						model.push_to_hub(f'''nielsr/{model_name}'''     )
						image_processor.push_to_hub(f'''nielsr/{model_name}'''     )


if __name__ == "__main__":
		_lowercase			:			Optional[Any]										=      argparse.ArgumentParser()
		# Required parameters
		parser.add_argument(
		    "--model_name",
		    default="maskformer-swin-tiny-ade",
		    type=str,
		    help=("Name of the MaskFormer model you\'d like to convert",),
		)
		parser.add_argument(
		    "--checkpoint_path",
		    default="/Users/nielsrogge/Documents/MaskFormer_checkpoints/MaskFormer-Swin-tiny-ADE20k/model.pkl",
		    type=str,
		    help="Path to the original state dict (.pth file).",
		)
		parser.add_argument(
		    "--pytorch_dump_folder_path", default=None, type=str, help="Path to the output PyTorch model directory."
		)
		parser.add_argument(
		    "--push_to_hub", action="store_true", help="Whether or not to push the converted model to the 🤗 hub."
		)

		_lowercase			:			List[Any]										=      parser.parse_args()
		convert_maskformer_checkpoint(
		    args.model_name, args.checkpoint_path, args.pytorch_dump_folder_path, args.push_to_hub
		)









"""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
		    )
		)




