

'''simple docstring'''

import argparse
import json

import torch
from huggingface_hub import hf_hub_download
from PIL import Image
from timm.models import create_model

from transformers import (
    BeitImageProcessor,
    DataaVecVisionConfig,
    DataaVecVisionForImageClassification,
    DataaVecVisionModel,
)




def  UpperCamelCase(	UpperCAmelCase_    ,			UpperCAmelCase_=False    ,			UpperCAmelCase_=False    ,			UpperCAmelCase_="data2vec."      ):
 UpperCAmelCase			:      int		   =					'backbone.' if is_semantic else ''

 UpperCAmelCase			:      Optional[Any]		   =					[]
 for i in range(config.num_hidden_layers      ):
  # encoder layers: output projection, 2 feedforward neural networks and 2 layernorms
  rename_keys.append(
      (F"""{prefix}blocks.{i}.norm1.weight""", F"""{hf_prefix}encoder.layer.{i}.layernorm_before.weight""")      )
  rename_keys.append((F"""{prefix}blocks.{i}.norm1.bias""", F"""{hf_prefix}encoder.layer.{i}.layernorm_before.bias""")      )
  rename_keys.append(
      (F"""{prefix}blocks.{i}.attn.proj.weight""", F"""{hf_prefix}encoder.layer.{i}.attention.output.dense.weight""")      )
  rename_keys.append(
      (F"""{prefix}blocks.{i}.attn.proj.bias""", F"""{hf_prefix}encoder.layer.{i}.attention.output.dense.bias""")      )
  rename_keys.append(
      (F"""{prefix}blocks.{i}.norm2.weight""", F"""{hf_prefix}encoder.layer.{i}.layernorm_after.weight""")      )
  rename_keys.append((F"""{prefix}blocks.{i}.norm2.bias""", F"""{hf_prefix}encoder.layer.{i}.layernorm_after.bias""")      )
  rename_keys.append(
      (F"""{prefix}blocks.{i}.mlp.fc1.weight""", F"""{hf_prefix}encoder.layer.{i}.intermediate.dense.weight""")      )
  rename_keys.append(
      (F"""{prefix}blocks.{i}.mlp.fc1.bias""", F"""{hf_prefix}encoder.layer.{i}.intermediate.dense.bias""")      )
  rename_keys.append((F"""{prefix}blocks.{i}.mlp.fc2.weight""", F"""{hf_prefix}encoder.layer.{i}.output.dense.weight""")      )
  rename_keys.append((F"""{prefix}blocks.{i}.mlp.fc2.bias""", F"""{hf_prefix}encoder.layer.{i}.output.dense.bias""")      )

 # projection layer + position embeddings
 rename_keys.extend(
     [
         (F"""{prefix}cls_token""", F"""{hf_prefix}embeddings.cls_token"""),
         (F"""{prefix}patch_embed.proj.weight""", F"""{hf_prefix}embeddings.patch_embeddings.projection.weight"""),
         (F"""{prefix}patch_embed.proj.bias""", F"""{hf_prefix}embeddings.patch_embeddings.projection.bias"""),
     ]      )

 if has_lm_head:
  # mask token + shared relative position bias + layernorm
  rename_keys.extend(
      [
          ('mask_token', F"""{hf_prefix}embeddings.mask_token"""),
          (
              'rel_pos_bias.relative_position_bias_table',
              F"""{hf_prefix}encoder.relative_position_bias.relative_position_bias_table""",
          ),
          (
              'rel_pos_bias.relative_position_index',
              F"""{hf_prefix}encoder.relative_position_bias.relative_position_index""",
          ),
          ('norm.weight', 'layernorm.weight'),
          ('norm.bias', 'layernorm.bias'),
      ]      )
 elif is_semantic:
  # semantic segmentation classification heads
  rename_keys.extend(
      [
          ('decode_head.conv_seg.weight', 'decode_head.classifier.weight'),
          ('decode_head.conv_seg.bias', 'decode_head.classifier.bias'),
          ('auxiliary_head.conv_seg.weight', 'auxiliary_head.classifier.weight'),
          ('auxiliary_head.conv_seg.bias', 'auxiliary_head.classifier.bias'),
      ]      )
 else:
  # layernorm + classification head
  rename_keys.extend(
      [
          ('fc_norm.weight', F"""{hf_prefix}pooler.layernorm.weight"""),
          ('fc_norm.bias', F"""{hf_prefix}pooler.layernorm.bias"""),
          ('head.weight', 'classifier.weight'),
          ('head.bias', 'classifier.bias'),
      ]      )

 return rename_keys




def  UpperCamelCase(	UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_=False    ,			UpperCAmelCase_=False    ,			UpperCAmelCase_="data2vec_vision."      ):
 for i in range(config.num_hidden_layers      ):
  UpperCAmelCase			:      str		   =					'backbone.' if is_semantic else ''
  # queries, keys and values
  UpperCAmelCase			:      Optional[Any]		   =					state_dict.pop(F"""{prefix}blocks.{i}.attn.qkv.weight"""      )
  UpperCAmelCase			:      List[str]		   =					state_dict.pop(F"""{prefix}blocks.{i}.attn.q_bias"""      )
  UpperCAmelCase			:      List[Any]		   =					state_dict.pop(F"""{prefix}blocks.{i}.attn.v_bias"""      )

  UpperCAmelCase			:      Tuple		   =					in_proj_weight[
      : config.hidden_size, :
  ]
  UpperCAmelCase			:      Tuple		   =					q_bias
  UpperCAmelCase			:      Optional[int]		   =					in_proj_weight[
      config.hidden_size : config.hidden_size * 2, :
  ]
  UpperCAmelCase			:      Union[str, Any]		   =					in_proj_weight[
      -config.hidden_size :, :
  ]
  UpperCAmelCase			:      Any		   =					v_bias

  # gamma_1 and gamma_2
  # we call them lambda because otherwise they are renamed when using .from_pretrained
  UpperCAmelCase			:      str		   =					state_dict.pop(F"""{prefix}blocks.{i}.gamma_1"""      )
  UpperCAmelCase			:      int		   =					state_dict.pop(F"""{prefix}blocks.{i}.gamma_2"""      )

  UpperCAmelCase			:      Union[str, Any]		   =					gamma_a
  UpperCAmelCase			:      Optional[int]		   =					gamma_a

  # relative_position bias table + index
  if not has_lm_head:
   # each layer has its own relative position bias
   UpperCAmelCase			:      Tuple		   =					state_dict.pop(F"""{prefix}blocks.{i}.attn.relative_position_bias_table"""      )
   UpperCAmelCase			:      Any		   =					state_dict.pop(F"""{prefix}blocks.{i}.attn.relative_position_index"""      )

   UpperCAmelCase			:      str		   =					table
   UpperCAmelCase			:      str		   =					index




def  UpperCamelCase(	):
 UpperCAmelCase			:      Optional[Any]		   =					argparse.ArgumentParser(
     'Convert Data2VecVision to HF for image classification and pretraining'    ,			add_help=UpperCAmelCase_      )
 parser.add_argument('--hf_checkpoint_name'    ,			type=UpperCAmelCase_      )
 parser.add_argument('--input_size'    ,			default=2_24    ,			type=UpperCAmelCase_    ,			help='images input size'      )
 parser.add_argument('--beit_checkpoint'    ,			default=''    ,			help='beit checkpoint'      )

 return parser.parse_args()




def  UpperCamelCase(	UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_      ):
 def load_state_dict(UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_=""    ,			UpperCAmelCase_="relative_position_index"      ):
  UpperCAmelCase			:      Optional[Any]		   =					[]
  UpperCAmelCase			:      Any		   =					[]
  UpperCAmelCase			:      List[Any]		   =					[]
  # copy state_dict so _load_from_state_dict can modify it
  UpperCAmelCase			:      int		   =					getattr(UpperCAmelCase_    ,			'_metadata'    ,			UpperCAmelCase_      )
  UpperCAmelCase			:      int		   =					state_dict.copy()
  if metadata is not None:
   UpperCAmelCase			:      str		   =					metadata

  def load(UpperCAmelCase_    ,			UpperCAmelCase_=""      ):
   UpperCAmelCase			:      Any		   =					{} if metadata is None else metadata.get(prefix[:-1]    ,			{}      )
   module._load_from_state_dict(
       UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_      )
   for name, child in module._modules.items():
    if child is not None:
     load(UpperCAmelCase_    ,			prefix + name + '.'      )

  load(UpperCAmelCase_    ,			prefix=UpperCAmelCase_      )

  UpperCAmelCase			:      str		   =					[]
  UpperCAmelCase			:      Dict		   =					[]
  for key in missing_keys:
   UpperCAmelCase			:      List[Any]		   =					True
   for ignore_key in ignore_missing.split('|'      ):
    if ignore_key in key:
     UpperCAmelCase			:      Dict		   =					False
     break
   if keep_flag:
    warn_missing_keys.append(UpperCAmelCase_      )
   else:
    ignore_missing_keys.append(UpperCAmelCase_      )

  UpperCAmelCase			:      Optional[Any]		   =					warn_missing_keys

  if len(UpperCAmelCase_      ) > 0:
   print(
       'Weights of {} not initialized from pretrained model: {}'.format(
           model.__class__.__name__    ,			UpperCAmelCase_      )      )
  if len(UpperCAmelCase_      ) > 0:
   print('Weights from pretrained model not used in {}: {}'.format(model.__class__.__name__    ,			UpperCAmelCase_      )      )
  if len(UpperCAmelCase_      ) > 0:
   print(
       'Ignored weights of {} not initialized from pretrained model: {}'.format(
           model.__class__.__name__    ,			UpperCAmelCase_      )      )
  if len(UpperCAmelCase_      ) > 0:
   print('\n'.join(UpperCAmelCase_      )      )

 UpperCAmelCase			:      List[Any]		   =					{
     'pretrained': False,
     'use_shared_rel_pos_bias': True,
     'use_abs_pos_emb': False,
     'init_values': 0.1,
 }

 if is_finetuned:
  model_kwargs.update(
      {
          'num_classes': 10_00,
          'use_mean_pooling': True,
          'init_scale': 0.001,
          'use_rel_pos_bias': True,
      }      )

 UpperCAmelCase			:      int		   =					create_model(
     'beit_large_patch16_224' if is_large else 'beit_base_patch16_224'    ,			**UpperCAmelCase_    ,			)
 UpperCAmelCase			:      str		   =					model.patch_embed.patch_size
 UpperCAmelCase			:      Tuple		   =					(args.input_size // patch_size[0], args.input_size // patch_size[1])
 UpperCAmelCase			:      Optional[Any]		   =					torch.load(args.beit_checkpoint    ,			map_location='cpu'      )

 print(F"""Load ckpt from {args.beit_checkpoint}"""      )
 UpperCAmelCase			:      str		   =					None
 for model_key in ("model", "module"):
  if model_key in checkpoint:
   UpperCAmelCase			:      List[str]		   =					checkpoint[model_key]
   print(F"""Load state_dict by model_key = {model_key}"""      )
   break

 UpperCAmelCase			:      List[Any]		   =					list(checkpoint_model.keys()      )
 for key in all_keys:
  if "relative_position_index" in key:
   checkpoint_model.pop(UpperCAmelCase_      )

  if "relative_position_bias_table" in key:
   UpperCAmelCase			:      Optional[int]		   =					checkpoint_model[key]
   UpperCAmelCase   ,					UpperCAmelCase			:      Dict		   =					rel_pos_bias.size()
   UpperCAmelCase   ,					UpperCAmelCase			:      Optional[Any]		   =					model.state_dict()[key].size()
   UpperCAmelCase			:      Any		   =					model.patch_embed.patch_shape
   if dst_patch_shape[0] != dst_patch_shape[1]:
    raise NotImplementedError()

 load_state_dict(UpperCAmelCase_    ,			UpperCAmelCase_    ,			prefix=''      )

 return model




def  UpperCamelCase(	):
 UpperCAmelCase			:      Dict		   =					get_args()

 UpperCAmelCase			:      str		   =					'ft1k' in args.hf_checkpoint_name
 UpperCAmelCase			:      Union[str, Any]		   =					'large' in args.hf_checkpoint_name

 if is_finetuned:
  # To convert Beit's data2vec_vision to HF you need to copy
  # https://github.com/facebookresearch/data2vec_vision/blob/main/beit/modeling_finetune.py
  # into this folder.
  import modeling_finetune  # noqa: F401
 else:
  # To convert Beit's data2vec_vision to HF you need to copy
  # https://github.com/facebookresearch/data2vec_vision/blob/main/beit/modeling_cyclical.py
  # into this folder
  # IMPORTANT: Note that for now we've only converted the down-stream
  # model and not the full pretrained model. This means for the integration
  # test you need to add a `return x` after the following line:
  # https://github.com/facebookresearch/data2vec_vision/blob/af9a36349aaed59ae66e69b5dabeef2d62fdc5da/beit/modeling_cyclical.py#L197
  # to make the integration test pass.
  import modeling_cyclical  # noqa: F401

 # 1. Create model config
 UpperCAmelCase			:      Tuple		   =					DataaVecVisionConfig()
 if is_finetuned:
  UpperCAmelCase			:      int		   =					True
  UpperCAmelCase			:      Any		   =					False
  UpperCAmelCase			:      Tuple		   =					True
  UpperCAmelCase			:      List[str]		   =					10_00

  UpperCAmelCase			:      Tuple		   =					'huggingface/label-files'
  UpperCAmelCase			:      Any		   =					'imagenet-1k-id2label.json'
  UpperCAmelCase			:      Tuple		   =					json.load(open(hf_hub_download(UpperCAmelCase_    ,			UpperCAmelCase_    ,			repo_type='dataset'      )    ,			'r'      )      )
  UpperCAmelCase			:      Any		   =					{int(UpperCAmelCase_      ): v for k, v in idalabel.items()}
  UpperCAmelCase			:      int		   =					idalabel
  UpperCAmelCase			:      List[Any]		   =					{v: k for k, v in idalabel.items()}
 else:
  UpperCAmelCase			:      str		   =					False
  UpperCAmelCase			:      List[str]		   =					True
  UpperCAmelCase			:      Tuple		   =					False

 if is_large:
  UpperCAmelCase			:      int		   =					10_24
  UpperCAmelCase			:      Optional[Any]		   =					40_96
  UpperCAmelCase			:      List[Any]		   =					24
  UpperCAmelCase			:      List[Any]		   =					16

 # 2. Load Beit model
 UpperCAmelCase			:      List[str]		   =					load_beit_model(UpperCAmelCase_    ,			UpperCAmelCase_    ,			UpperCAmelCase_      )
 orig_model.eval()

 # 3. Forward Beit model
 UpperCAmelCase			:      List[str]		   =					BeitImageProcessor(size=config.image_size    ,			do_center_crop=UpperCAmelCase_      )
 UpperCAmelCase			:      Tuple		   =					Image.open('../../../../tests/fixtures/tests_samples/COCO/000000039769.png'      )
 UpperCAmelCase			:      Optional[int]		   =					image_processor(images=UpperCAmelCase_    ,			return_tensors='pt'      )
 UpperCAmelCase			:      int		   =					encoding['pixel_values']

 UpperCAmelCase			:      Tuple		   =					(pixel_values,) if is_finetuned else (pixel_values, None)
 with torch.no_grad():
  UpperCAmelCase			:      List[str]		   =					orig_model(*UpperCAmelCase_      )

 # 4. Load HF Data2VecVision model
 if is_finetuned:
  UpperCAmelCase			:      str		   =					DataaVecVisionForImageClassification(UpperCAmelCase_      )
  hf_model.eval()
  UpperCAmelCase			:      Any		   =					False
  UpperCAmelCase			:      List[str]		   =					'data2vec_vision.'
 else:
  UpperCAmelCase			:      List[Any]		   =					DataaVecVisionModel(UpperCAmelCase_      )
  hf_model.eval()
  UpperCAmelCase			:      List[Any]		   =					True
  UpperCAmelCase			:      str		   =					''

 UpperCAmelCase			:      Any		   =					create_rename_keys(UpperCAmelCase_    ,			hf_prefix=UpperCAmelCase_    ,			has_lm_head=UpperCAmelCase_      )
 UpperCAmelCase			:      str		   =					orig_model.state_dict()
 for src, dest in rename_keys:
  UpperCAmelCase			:      Optional[int]		   =					state_dict.pop(UpperCAmelCase_      )
  UpperCAmelCase			:      Dict		   =					val

 read_in_q_k_v(UpperCAmelCase_    ,			UpperCAmelCase_    ,			hf_prefix=UpperCAmelCase_    ,			has_lm_head=UpperCAmelCase_      )
 UpperCAmelCase   ,					UpperCAmelCase			:      Optional[Any]		   =					hf_model.load_state_dict(UpperCAmelCase_    ,			strict=UpperCAmelCase_      )
 print('HF missing'    ,			UpperCAmelCase_      )
 print('HF unexpected_keys'    ,			UpperCAmelCase_      )

 # 5. Forward HF Data2VecVision model
 with torch.no_grad():
  UpperCAmelCase			:      Optional[int]		   =					hf_model(UpperCAmelCase_      )

 UpperCAmelCase			:      List[str]		   =					hf_model_output.logits if is_finetuned else hf_model_output.last_hidden_state

 # 6. Compare
 UpperCAmelCase			:      str		   =					torch.max(torch.abs(hf_output - orig_model_output      )      ).item()

 print(F"""max_absolute_diff = {max_absolute_diff}"""      )
 UpperCAmelCase			:      str		   =					torch.allclose(UpperCAmelCase_    ,			UpperCAmelCase_    ,			atol=1E-3      )
 print('Do both models output the same tensors?'    ,			'🔥' if success else '💩'      )
 if not success:
  raise Exception('Something went wRoNg'      )

 # 7. Save
 print(F"""Saving to {args.hf_checkpoint_name}"""      )
 hf_model.save_pretrained(args.hf_checkpoint_name      )
 image_processor.save_pretrained(args.hf_checkpoint_name      )


if __name__ == "__main__":
 main()
 # Run the following to convert checkpoints
 #  python ./convert_data2vec_vision_original_pytorch_checkpoint_to_pytorch.py \
 #          --beit_checkpoint ./pretrained_base.pt \
 #          --hf_checkpoint_name "./data2vec-vision-base"
 #  python ./convert_data2vec_vision_original_pytorch_checkpoint_to_pytorch.py \
 #          --beit_checkpoint ./finetuned_base.pt \
 #          --hf_checkpoint_name "./data2vec-vision-base-ft1k"
 #  python ./convert_data2vec_vision_original_pytorch_checkpoint_to_pytorch.py \
 #          --beit_checkpoint ./pretrained_large.pt \
 #          --hf_checkpoint_name "./data2vec-vision-large"
 #  python ./convert_data2vec_vision_original_pytorch_checkpoint_to_pytorch.py \
 #          --beit_checkpoint ./finetuned_large.pt \
 #          --hf_checkpoint_name "./data2vec-vision-large-ft1k"







'''simple docstring'''

def  UpperCamelCase(	UpperCAmelCase_ = 1_00      ):
 UpperCAmelCase			:      Optional[Any]		   =					[[0 for _ in range(UpperCAmelCase_      )] for _ in range(m + 1      )]
 for i in range(m + 1      ):
  UpperCAmelCase			:      Optional[int]		   =					1

 for n in range(m + 1      ):
  for k in range(1    ,			UpperCAmelCase_      ):
   memo[n][k] += memo[n][k - 1]
   if n > k:
    memo[n][k] += memo[n - k - 1][k]

 return memo[m][m - 1] - 1


if __name__ == "__main__":
 print(solution(int(input("Enter a number: ").strip())))




