
import inspect
import unittest
import warnings
from typing import List

from transformers import EfficientFormerConfig
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
				import torch

				from transformers import (
				    MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
				    MODEL_MAPPING,
				    EfficientFormerForImageClassification,
				    EfficientFormerForImageClassificationWithTeacher,
				    EfficientFormerModel,
				)
				from transformers.models.efficientformer.modeling_efficientformer import (
				    EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
				)


if is_vision_available():
				from PIL import Image

				from transformers import EfficientFormerImageProcessor






class 							SCREAMING_SNAKE_CASE__     :

							"""simple docstring"""






							def __init__(	self  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_ = 13  ,						SCREAMING_SNAKE_CASE_ = 64  ,						SCREAMING_SNAKE_CASE_ = 2  ,						SCREAMING_SNAKE_CASE_ = 3  ,						SCREAMING_SNAKE_CASE_ = 3  ,						SCREAMING_SNAKE_CASE_ = True  ,						SCREAMING_SNAKE_CASE_ = True  ,						SCREAMING_SNAKE_CASE_ = 128  ,						SCREAMING_SNAKE_CASE_=[16, 32, 64, 128]  ,						SCREAMING_SNAKE_CASE_ = 7  ,						SCREAMING_SNAKE_CASE_ = 4  ,						SCREAMING_SNAKE_CASE_ = 37  ,						SCREAMING_SNAKE_CASE_ = "gelu"  ,						SCREAMING_SNAKE_CASE_ = 0.1  ,						SCREAMING_SNAKE_CASE_ = 0.1  ,						SCREAMING_SNAKE_CASE_ = 10  ,						SCREAMING_SNAKE_CASE_ = 0.0_2  ,						SCREAMING_SNAKE_CASE_ = 2  ,						SCREAMING_SNAKE_CASE_ = 1  ,						SCREAMING_SNAKE_CASE_ = 128  ,						SCREAMING_SNAKE_CASE_ = [2, 2, 2, 2]  ,						SCREAMING_SNAKE_CASE_ = 2  ,						SCREAMING_SNAKE_CASE_ = 2  ,						)-> Any:





													'''simple docstring'''






													__UpperCamelCase  	=      parent
													__UpperCamelCase  	=      batch_size
													__UpperCamelCase  	=      image_size
													__UpperCamelCase  	=      patch_size
													__UpperCamelCase  	=      num_channels
													__UpperCamelCase  	=      is_training
													__UpperCamelCase  	=      use_labels
													__UpperCamelCase  	=      hidden_size
													__UpperCamelCase  	=      num_hidden_layers
													__UpperCamelCase  	=      num_attention_heads
													__UpperCamelCase  	=      intermediate_size
													__UpperCamelCase  	=      hidden_act
													__UpperCamelCase  	=      hidden_dropout_prob
													__UpperCamelCase  	=      attention_probs_dropout_prob
													__UpperCamelCase  	=      type_sequence_label_size
													__UpperCamelCase  	=      initializer_range
													__UpperCamelCase  	=      encoder_stride
													__UpperCamelCase  	=      num_attention_outputs
													__UpperCamelCase  	=      embed_dim
													__UpperCamelCase  	=      embed_dim + 1
													__UpperCamelCase  	=      resolution
													__UpperCamelCase  	=      depths
													__UpperCamelCase  	=      hidden_sizes
													__UpperCamelCase  	=      dim
													__UpperCamelCase  	=      mlp_expansion_ratio



							def      A__		(	self      )-> str:





													'''simple docstring'''






													__UpperCamelCase  	=      floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]      )

													__UpperCamelCase  	=      None
													if self.use_labels:
																			__UpperCamelCase  	=      ids_tensor([self.batch_size]  ,						self.type_sequence_label_size      )

													__UpperCamelCase  	=      self.get_config()
													return config, pixel_values, labels



							def      A__		(	self      )-> Dict:





													'''simple docstring'''






													return EfficientFormerConfig(
													    image_size=self.image_size  ,						patch_size=self.patch_size  ,						num_channels=self.num_channels  ,						hidden_size=self.hidden_size  ,						num_hidden_layers=self.num_hidden_layers  ,						num_attention_heads=self.num_attention_heads  ,						intermediate_size=self.intermediate_size  ,						hidden_act=self.hidden_act  ,						hidden_dropout_prob=self.hidden_dropout_prob  ,						attention_probs_dropout_prob=self.attention_probs_dropout_prob  ,						is_decoder=SCREAMING_SNAKE_CASE_  ,						initializer_range=self.initializer_range  ,						encoder_stride=self.encoder_stride  ,						resolution=self.resolution  ,						depths=self.depths  ,						hidden_sizes=self.hidden_sizes  ,						dim=self.dim  ,						mlp_expansion_ratio=self.mlp_expansion_ratio  ,						)



							def      A__		(	self  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      )-> Union[str, Any]:





													'''simple docstring'''






													__UpperCamelCase  	=      EfficientFormerModel(config=SCREAMING_SNAKE_CASE_      )
													model.to(SCREAMING_SNAKE_CASE_      )
													model.eval()
													__UpperCamelCase  	=      model(SCREAMING_SNAKE_CASE_      )
													self.parent.assertEqual(result.last_hidden_state.shape  ,						(self.batch_size, self.seq_length, self.hidden_size)      )



							def      A__		(	self  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      )-> List[Any]:





													'''simple docstring'''






													__UpperCamelCase  	=      self.type_sequence_label_size
													__UpperCamelCase  	=      EfficientFormerForImageClassification(SCREAMING_SNAKE_CASE_      )
													model.to(SCREAMING_SNAKE_CASE_      )
													model.eval()
													__UpperCamelCase  	=      model(SCREAMING_SNAKE_CASE_  ,						labels=SCREAMING_SNAKE_CASE_      )
													self.parent.assertEqual(result.logits.shape  ,						(self.batch_size, self.type_sequence_label_size)      )

													# test greyscale images
													__UpperCamelCase  	=      1
													__UpperCamelCase  	=      EfficientFormerForImageClassification(SCREAMING_SNAKE_CASE_      )
													model.to(SCREAMING_SNAKE_CASE_      )
													model.eval()

													__UpperCamelCase  	=      floats_tensor([self.batch_size, 1, self.image_size, self.image_size]      )
													__UpperCamelCase  	=      model(SCREAMING_SNAKE_CASE_      )
													self.parent.assertEqual(result.logits.shape  ,						(self.batch_size, self.type_sequence_label_size)      )



							def      A__		(	self      )-> Tuple:





													'''simple docstring'''






													__UpperCamelCase  	=      self.prepare_config_and_inputs()
													(
													    (
													    __UpperCamelCase
													)	,				(
													    __UpperCamelCase
													)	,				(
													    __UpperCamelCase
													)	,				
													)  	=      config_and_inputs
													__UpperCamelCase  	=      {'''pixel_values''': pixel_values}
													return config, inputs_dict






@require_torch
class 							SCREAMING_SNAKE_CASE__     (				SCREAMING_SNAKE_CASE_ ,		SCREAMING_SNAKE_CASE_ ,		unittest.TestCase     ):

							"""simple docstring"""






							_snake_case  		=	(
							    (
							        EfficientFormerModel,
							        EfficientFormerForImageClassificationWithTeacher,
							        EfficientFormerForImageClassification,
							    )
							    if is_torch_available()
							    else ()
							)
							_snake_case  		=	(
							    {
							        'feature-extraction': EfficientFormerModel,
							        'image-classification': (
							            EfficientFormerForImageClassification,
							            EfficientFormerForImageClassificationWithTeacher,
							        ),
							    }
							    if is_torch_available()
							    else {}
							)
							_snake_case  		=	False

							_snake_case  		=	False
							_snake_case  		=	False
							_snake_case  		=	False



							def      A__		(	self      )-> Tuple:





													'''simple docstring'''






													__UpperCamelCase  	=      EfficientFormerModelTester(self      )
													__UpperCamelCase  	=      ConfigTester(
													    self  ,						config_class=SCREAMING_SNAKE_CASE_  ,						has_text_modality=SCREAMING_SNAKE_CASE_  ,						hidden_size=37      )



							def      A__		(	self      )-> Dict:





													'''simple docstring'''






													self.config_tester.run_common_tests()



							@unittest.skip(reason='''EfficientFormer does not use inputs_embeds'''      )
							def      A__		(	self      )-> List[Any]:





													'''simple docstring'''






													pass



							@unittest.skip(reason='''EfficientFormer does not support input and output embeddings'''      )
							def      A__		(	self      )-> int:





													'''simple docstring'''






													pass



							def      A__		(	self      )-> int:





													'''simple docstring'''






													__UpperCamelCase	,				__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs_for_common()

													for model_class in self.all_model_classes:
																			__UpperCamelCase  	=      model_class(SCREAMING_SNAKE_CASE_      )
																			__UpperCamelCase  	=      inspect.signature(model.forward      )
																			# signature.parameters is an OrderedDict => so arg_names order is deterministic
																			__UpperCamelCase  	=      [*signature.parameters.keys()]

																			__UpperCamelCase  	=      ['''pixel_values''']
																			self.assertListEqual(arg_names[:1]  ,						SCREAMING_SNAKE_CASE_      )



							def      A__		(	self      )-> Optional[Any]:





													'''simple docstring'''






													def check_hidden_states_output(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      ):
																			__UpperCamelCase  	=      model_class(SCREAMING_SNAKE_CASE_      )
																			model.to(SCREAMING_SNAKE_CASE_      )
																			model.eval()

																			with torch.no_grad():
																									__UpperCamelCase  	=      model(**self._prepare_for_class(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      )      )

																			__UpperCamelCase  	=      outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

																			__UpperCamelCase  	=      getattr(
																			    self.model_tester  ,						'''expected_num_hidden_layers'''  ,						self.model_tester.num_hidden_layers + 1      )
																			self.assertEqual(len(SCREAMING_SNAKE_CASE_      )  ,						SCREAMING_SNAKE_CASE_      )

																			if hasattr(self.model_tester  ,						'''encoder_seq_length'''      ):
																									__UpperCamelCase  	=      self.model_tester.encoder_seq_length
																									if hasattr(self.model_tester  ,						'''chunk_length'''      ) and self.model_tester.chunk_length > 1:
																															__UpperCamelCase  	=      seq_length * self.model_tester.chunk_length
																			else:
																									__UpperCamelCase  	=      self.model_tester.seq_length

																			self.assertListEqual(
																			    list(hidden_states[-1].shape[-2:]      )  ,						[seq_length, self.model_tester.hidden_size]  ,						)

																			if config.is_encoder_decoder:
																									__UpperCamelCase  	=      outputs.decoder_hidden_states

																									self.assertIsInstance(SCREAMING_SNAKE_CASE_  ,						(list, tuple)      )
																									self.assertEqual(len(SCREAMING_SNAKE_CASE_      )  ,						SCREAMING_SNAKE_CASE_      )
																									__UpperCamelCase  	=      getattr(self.model_tester  ,						'''seq_length'''  ,						SCREAMING_SNAKE_CASE_      )
																									__UpperCamelCase  	=      getattr(self.model_tester  ,						'''decoder_seq_length'''  ,						SCREAMING_SNAKE_CASE_      )

																									self.assertListEqual(
																									    list(hidden_states[-1].shape[-2:]      )  ,						[decoder_seq_length, self.model_tester.hidden_size]  ,						)

													__UpperCamelCase	,				__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs_for_common()

													for model_class in self.all_model_classes:
																			__UpperCamelCase  	=      True
																			check_hidden_states_output(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      )

																			# check that output_hidden_states also work using config
																			del inputs_dict["output_hidden_states"]
																			__UpperCamelCase  	=      True

																			check_hidden_states_output(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      )



							def      A__		(	self  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_=False      )-> str:





													'''simple docstring'''






													__UpperCamelCase  	=      super()._prepare_for_class(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						return_labels=SCREAMING_SNAKE_CASE_      )

													if return_labels:
																			if model_class.__name__ == "EfficientFormerForImageClassificationWithTeacher":
																									del inputs_dict["labels"]

													return inputs_dict



							def      A__		(	self      )-> Optional[Any]:





													'''simple docstring'''






													__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs()
													self.model_tester.create_and_check_model(*SCREAMING_SNAKE_CASE_      )



							@unittest.skip(reason='''EfficientFormer does not implement masked image modeling yet'''      )
							def      A__		(	self      )-> Dict:





													'''simple docstring'''






													__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs()
													self.model_tester.create_and_check_for_masked_image_modeling(*SCREAMING_SNAKE_CASE_      )



							def      A__		(	self      )-> Optional[int]:





													'''simple docstring'''






													__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs()
													self.model_tester.create_and_check_for_image_classification(*SCREAMING_SNAKE_CASE_      )



							def      A__		(	self      )-> int:





													'''simple docstring'''






													if not self.model_tester.is_training:
																			return

													__UpperCamelCase	,				__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs_for_common()
													__UpperCamelCase  	=      True

													for model_class in self.all_model_classes:
																			# EfficientFormerForImageClassificationWithTeacher supports inference-only
																			if (
																			    model_class in get_values(SCREAMING_SNAKE_CASE_      )
																			    or model_class.__name__ == "EfficientFormerForImageClassificationWithTeacher"
																			):
																									continue
																			__UpperCamelCase  	=      model_class(SCREAMING_SNAKE_CASE_      )
																			model.to(SCREAMING_SNAKE_CASE_      )
																			model.train()
																			__UpperCamelCase  	=      self._prepare_for_class(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						return_labels=SCREAMING_SNAKE_CASE_      )
																			__UpperCamelCase  	=      model(**SCREAMING_SNAKE_CASE_      ).loss
																			loss.backward()



							def      A__		(	self      )-> str:





													'''simple docstring'''






													__UpperCamelCase	,				__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs_for_common()

													__UpperCamelCase  	=      [
													    {'''title''': '''multi_label_classification''', '''num_labels''': 2, '''dtype''': torch.float},
													    {'''title''': '''single_label_classification''', '''num_labels''': 1, '''dtype''': torch.long},
													    {'''title''': '''regression''', '''num_labels''': 1, '''dtype''': torch.float},
													]

													for model_class in self.all_model_classes:
																			if (
																			    model_class
																			    not in [
																			        *get_values(SCREAMING_SNAKE_CASE_      ),
																			    ]
																			    or model_class.__name__ == "EfficientFormerForImageClassificationWithTeacher"
																			):
																									continue

																			for problem_type in problem_types:
																									with self.subTest(msg=F"Testing {model_class} with {problem_type['title']}"      ):
																															__UpperCamelCase  	=      problem_type['''title''']
																															__UpperCamelCase  	=      problem_type['''num_labels''']

																															__UpperCamelCase  	=      model_class(SCREAMING_SNAKE_CASE_      )
																															model.to(SCREAMING_SNAKE_CASE_      )
																															model.train()

																															__UpperCamelCase  	=      self._prepare_for_class(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_  ,						return_labels=SCREAMING_SNAKE_CASE_      )

																															if problem_type["num_labels"] > 1:
																																					__UpperCamelCase  	=      inputs['''labels'''].unsqueeze(1      ).repeat(1  ,						problem_type['''num_labels''']      )

																															__UpperCamelCase  	=      inputs['''labels'''].to(problem_type['''dtype''']      )

																															# This tests that we do not trigger the warning form PyTorch "Using a target size that is different
																															# to the input size. This will likely lead to incorrect results due to broadcasting. Please ensure
																															# they have the same size." which is a symptom something in wrong for the regression problem.
																															# See https://github.com/huggingface/transformers/issues/11780
																															with warnings.catch_warnings(record=SCREAMING_SNAKE_CASE_      ) as warning_list:
																																					__UpperCamelCase  	=      model(**SCREAMING_SNAKE_CASE_      ).loss
																															for w in warning_list:
																																					if "Using a target size that is different to the input size" in str(w.message      ):
																																											raise ValueError(
																																											    F"Something is going wrong in the regression problem: intercepted {w.message}"      )

																															loss.backward()



							@slow
							def      A__		(	self      )-> Any:





													'''simple docstring'''






													for model_name in EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																			__UpperCamelCase  	=      EfficientFormerModel.from_pretrained(SCREAMING_SNAKE_CASE_      )
																			self.assertIsNotNone(SCREAMING_SNAKE_CASE_      )



							def      A__		(	self      )-> Union[str, Any]:





													'''simple docstring'''






													__UpperCamelCase	,				__UpperCamelCase  	=      self.model_tester.prepare_config_and_inputs_for_common()
													__UpperCamelCase  	=      True

													__UpperCamelCase  	=      getattr(self.model_tester  ,						'''seq_length'''  ,						SCREAMING_SNAKE_CASE_      )
													__UpperCamelCase  	=      getattr(self.model_tester  ,						'''encoder_seq_length'''  ,						SCREAMING_SNAKE_CASE_      )
													__UpperCamelCase  	=      getattr(self.model_tester  ,						'''key_length'''  ,						SCREAMING_SNAKE_CASE_      )
													__UpperCamelCase  	=      getattr(self.model_tester  ,						'''chunk_length'''  ,						SCREAMING_SNAKE_CASE_      )

													if chunk_length is not None and hasattr(self.model_tester  ,						'''num_hashes'''      ):
																			__UpperCamelCase  	=      encoder_seq_length * self.model_tester.num_hashes

													for model_class in self.all_model_classes:
																			__UpperCamelCase  	=      True
																			__UpperCamelCase  	=      False
																			__UpperCamelCase  	=      True
																			__UpperCamelCase  	=      model_class(SCREAMING_SNAKE_CASE_      )
																			model.to(SCREAMING_SNAKE_CASE_      )
																			model.eval()
																			with torch.no_grad():
																									__UpperCamelCase  	=      model(**self._prepare_for_class(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      )      )
																			__UpperCamelCase  	=      outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
																			self.assertEqual(len(SCREAMING_SNAKE_CASE_      )  ,						self.model_tester.num_attention_outputs      )

																			# check that output_attentions also work using config
																			del inputs_dict["output_attentions"]
																			__UpperCamelCase  	=      True
																			__UpperCamelCase  	=      model_class(SCREAMING_SNAKE_CASE_      )
																			model.to(SCREAMING_SNAKE_CASE_      )
																			model.eval()
																			with torch.no_grad():
																									__UpperCamelCase  	=      model(**self._prepare_for_class(SCREAMING_SNAKE_CASE_  ,						SCREAMING_SNAKE_CASE_      )      )
																			__UpperCamelCase  	=      outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
																			self.assertEqual(len(SCREAMING_SNAKE_CASE_      )  ,						self.model_tester.num_attention_outputs      )

																			if chunk_length is not None:
																									self.assertListEqual(
																									    list(attentions[0].shape[-4:]      )  ,						[self.model_tester.num_attention_heads, encoder_seq_length, chunk_length, encoder_key_length]  ,						)
																			else:
																									self.assertListEqual(
																									    list(attentions[0].shape[-3:]      )  ,						[self.model_tester.num_attention_heads, encoder_seq_length, encoder_key_length]  ,						)





def 						A_			(				)   ->     Any:



						'''simple docstring'''

						__UpperCamelCase  	=      Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''			)
						return image






@require_torch
@require_vision
class 							SCREAMING_SNAKE_CASE__     (				unittest.TestCase     ):

							"""simple docstring"""






							@cached_property
							def      A__		(	self      )-> int:





													'''simple docstring'''






													return (
													    EfficientFormerImageProcessor.from_pretrained('''snap-research/efficientformer-l1-300'''      )
													    if is_vision_available()
													    else None
													)



							@slow
							def      A__		(	self      )-> str:





													'''simple docstring'''






													__UpperCamelCase  	=      EfficientFormerForImageClassification.from_pretrained('''snap-research/efficientformer-l1-300'''      ).to(
													    SCREAMING_SNAKE_CASE_      )

													__UpperCamelCase  	=      self.default_image_processor
													__UpperCamelCase  	=      prepare_img()
													__UpperCamelCase  	=      image_processor(images=SCREAMING_SNAKE_CASE_  ,						return_tensors='''pt'''      ).to(SCREAMING_SNAKE_CASE_      )

													# forward pass
													with torch.no_grad():
																			__UpperCamelCase  	=      model(**SCREAMING_SNAKE_CASE_      )

													# verify the logits
													__UpperCamelCase  	=      (1, 1000)
													self.assertEqual(outputs.logits.shape  ,						SCREAMING_SNAKE_CASE_      )

													__UpperCamelCase  	=      torch.tensor([-0.0_5_5_5, 0.4_8_2_5, -0.0_8_5_2]      ).to(SCREAMING_SNAKE_CASE_      )
													self.assertTrue(torch.allclose(outputs.logits[0][:3]  ,						SCREAMING_SNAKE_CASE_  ,						atol=1E-4      )      )



							@slow
							def      A__		(	self      )-> List[Any]:





													'''simple docstring'''






													__UpperCamelCase  	=      EfficientFormerForImageClassificationWithTeacher.from_pretrained(
													    '''snap-research/efficientformer-l1-300'''      ).to(SCREAMING_SNAKE_CASE_      )

													__UpperCamelCase  	=      self.default_image_processor
													__UpperCamelCase  	=      prepare_img()
													__UpperCamelCase  	=      image_processor(images=SCREAMING_SNAKE_CASE_  ,						return_tensors='''pt'''      ).to(SCREAMING_SNAKE_CASE_      )

													# forward pass
													with torch.no_grad():
																			__UpperCamelCase  	=      model(**SCREAMING_SNAKE_CASE_      )

													# verify the logits
													__UpperCamelCase  	=      (1, 1000)
													self.assertEqual(outputs.logits.shape  ,						SCREAMING_SNAKE_CASE_      )

													__UpperCamelCase  	=      torch.tensor([-0.1_3_1_2, 0.4_3_5_3, -1.0_4_9_9]      ).to(SCREAMING_SNAKE_CASE_      )
													self.assertTrue(torch.allclose(outputs.logits[0][:3]  ,						SCREAMING_SNAKE_CASE_  ,						atol=1E-4      )      )











'''simple docstring'''






import timeit


class 	_lowercase    :


   def __init__(			self     , _UpperCAmelCase       ):
       if isinstance(_UpperCAmelCase     , _UpperCAmelCase       ):  # Initializes a matrix identical to the one provided.
           A							:							List[Any]				=    arg
           A							:							Dict				=    len(_UpperCAmelCase       )
       else:  # Initializes a square matrix of the given size and set values to zero.
           A							:							str				=    arg
           A							:							Union[str, Any]				=    [[0 for _ in range(self.n       )] for _ in range(self.n       )]


   def __mul__(			self     , _UpperCAmelCase       ):
       A							:							List[str]				=    Matrix(self.n       )
       for i in range(self.n       ):
           for j in range(self.n       ):
               for k in range(self.n       ):
                   matrix.t[i][j] += self.t[i][k] * b.t[k][j]
       return matrix







def 				_lowerCamelCase(	UpperCamelCase__     :			Union[str, Any]     ,							UpperCamelCase__     :			int		)		->	Union[str, Any]:
    A							:							Tuple				=    Matrix([[1, 0], [0, 1]]		)
    while b > 0:
        if b & 1:
            matrix *= a
        a *= a
        b >>= 1
    return matrix
def 				_lowerCamelCase(	UpperCamelCase__     :			int     ,							UpperCamelCase__     :			Tuple     ,							UpperCamelCase__     :			Any		)		->	Any:
    # Trivial Cases
    if n == 1:
        return fa
    elif n == 2:
        return fa
    A							:							Optional[Any]				=    Matrix([[1, 1], [1, 0]]		)
    A							:							int				=    modular_exponentiation(UpperCamelCase__     ,							n - 2		)
    return fa * matrix.t[0][0] + fa * matrix.t[0][1]
def 				_lowerCamelCase(	UpperCamelCase__     :			str     ,							UpperCamelCase__     :			Optional[Any]     ,							UpperCamelCase__     :			Any		)		->	List[Any]:
    # Trivial Cases
    if n == 1:
        return fa
    elif n == 2:
        return fa

    A							:							str				=    fa
    A							:							List[Any]				=    fa
    n -= 2

    while n > 0:
        A,						A							:							List[str]				=    fn_a + fn_a, fn_a
        n -= 1

    return fn_a
def 				_lowerCamelCase(	)		->	Union[str, Any]:
    A							:							Any				=    '''
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
'''
    A							:							Optional[int]				=    '''fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'''
    A							:							List[Any]				=    timeit.timeit(setup=UpperCamelCase__     ,							stmt=UpperCamelCase__     ,							number=100		)
    print('''With matrix exponentiation the average execution time is '''     ,							exec_time / 100		)
    return exec_time
def 				_lowerCamelCase(	)		->	List[Any]:
    A							:							str				=    '''
from random import randint
from __main__ import simple_fibonacci
'''
    A							:							Any				=    '''simple_fibonacci(randint(1,70000), 1, 1)'''
    A							:							str				=    timeit.timeit(setup=UpperCamelCase__     ,							stmt=UpperCamelCase__     ,							number=100		)
    print(
        '''Without matrix exponentiation the average execution time is '''     ,							exec_time / 100		)
    return exec_time
def 				_lowerCamelCase(	)		->	Optional[Any]:
    matrix_exponentiation_time()
    simple_fibonacci_time()


if __name__ == "__main__":
     main()
