





'''simple docstring'''

def 						__UpperCamelCase						(			_UpperCAmelCase,       _UpperCAmelCase  ):
		__UpperCAmelCase	:							int     =     []
		__UpperCAmelCase	:							Union[str, Any]     =     len(_UpperCAmelCase  )
		for i in range(_UpperCAmelCase  ):
				__UpperCAmelCase	:							List[Any]     =     []
				for j in range(_UpperCAmelCase  ):
						__UpperCAmelCase	:							Optional[int]     =     0
						for k in range(_UpperCAmelCase  ):
								__UpperCAmelCase	:							str     =     val + matrix_a[i][k] * matrix_b[k][j]
						list_a.append(_UpperCAmelCase  )
				matrix_c.append(_UpperCAmelCase  )
		return matrix_c


def 						__UpperCamelCase						(			_UpperCAmelCase  ):
		return [[int(row == column  ) for column in range(_UpperCAmelCase  )] for row in range(_UpperCAmelCase  )]


def 						__UpperCamelCase						(			_UpperCAmelCase  ):
		if n <= 1:
				return n
		__UpperCAmelCase	:							List[str]     =     identity(2  )
		__UpperCAmelCase	:							Any     =     [[1, 1], [1, 0]]
		__UpperCAmelCase	:							Union[str, Any]     =     n - 1
		while n > 0:
				if n % 2 == 1:
						__UpperCAmelCase	:							Tuple     =     multiply(_UpperCAmelCase,       _UpperCAmelCase  )
				__UpperCAmelCase	:							str     =     multiply(_UpperCAmelCase,       _UpperCAmelCase  )
				__UpperCAmelCase	:							List[Any]     =     int(n / 2  )
		return res_matrix[0][0]


def 						__UpperCamelCase						(			_UpperCAmelCase  ):
		if n <= 1:
				return n
		__UpperCAmelCase	:							Union[str, Any]     =     0
		__UpperCAmelCase	:							Union[str, Any]     =     1
		for _ in range(2,       n + 1  ):
				__UpperCAmelCase  ,			__UpperCAmelCase	:							Optional[Any]     =     fiba, fiba + fiba
		return fiba


def 						__UpperCamelCase						(			):
		for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
				__UpperCAmelCase	:							List[str]     =     int("".join(c for c in ordinal if c in "0123456789"  )  )  # 1000th --> 1000
				print(
				    F"{ordinal} fibonacci number using matrix exponentiation is "
				    F"{nth_fibonacci_matrix(_UpperCAmelCase  )} and using bruteforce is "
				    F"{nth_fibonacci_bruteforce(_UpperCAmelCase  )}\n"  )
		# from timeit import timeit
		# print(timeit("nth_fibonacci_matrix(1000000)",
		#              "from main import nth_fibonacci_matrix", number=5))
		# print(timeit("nth_fibonacci_bruteforce(1000000)",
		#              "from main import nth_fibonacci_bruteforce", number=5))
		# 2.3342058970001744
		# 57.256506615000035


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()










from __future__ import annotations

import inspect
import unittest

from transformers import MobileViTConfig
from transformers.file_utils import is_tf_available, is_vision_available
from transformers.testing_utils import require_tf, slow

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
		import numpy as np
		import tensorflow as tf

		from transformers import TFMobileViTForImageClassification, TFMobileViTForSemanticSegmentation, TFMobileViTModel
		from transformers.models.mobilevit.modeling_tf_mobilevit import TF_MOBILEVIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
		from PIL import Image

		from transformers import MobileViTImageProcessor




class       UpperCAmelCase_   ( A							):




							'''simple docstring'''



							def  _UpperCAmelCase  (       self							:						Tuple      )      ->       int:
										SCREAMING_SNAKE_CASE     =       self.config_class(**self.inputs_dict      )
										self.parent.assertTrue(hasattr(a							,  """hidden_sizes"""      )      )
										self.parent.assertTrue(hasattr(a							,  """neck_hidden_sizes"""      )      )
										self.parent.assertTrue(hasattr(a							,  """num_attention_heads"""      )      )





class       UpperCAmelCase_   :




							'''simple docstring'''



							def __init__(       self							:						Optional[Any]							,  a							:						Dict							,  a							:						Optional[int]=13							,  a							:						Optional[int]=32							,  a							:						List[str]=2							,  a							:						Optional[int]=3							,  a							:						str=640							,  a							:						str=4							,  a							:						Optional[int]="silu"							,  a							:						Union[str, Any]=3							,  a							:						Optional[int]=32							,  a							:						Optional[Any]=0.1							,  a							:						Optional[int]=0.1							,  a							:						int=0.1							,  a							:						List[str]=0.02							,  a							:						Tuple=True							,  a							:						Optional[Any]=True							,  a							:						List[Any]=10							,  a							:						List[Any]=None							,  )      ->       List[str]:
										SCREAMING_SNAKE_CASE     =       parent
										SCREAMING_SNAKE_CASE     =       batch_size
										SCREAMING_SNAKE_CASE     =       image_size
										SCREAMING_SNAKE_CASE     =       patch_size
										SCREAMING_SNAKE_CASE     =       num_channels
										SCREAMING_SNAKE_CASE     =       last_hidden_size
										SCREAMING_SNAKE_CASE     =       num_attention_heads
										SCREAMING_SNAKE_CASE     =       hidden_act
										SCREAMING_SNAKE_CASE     =       conv_kernel_size
										SCREAMING_SNAKE_CASE     =       output_stride
										SCREAMING_SNAKE_CASE     =       hidden_dropout_prob
										SCREAMING_SNAKE_CASE     =       attention_probs_dropout_prob
										SCREAMING_SNAKE_CASE     =       classifier_dropout_prob
										SCREAMING_SNAKE_CASE     =       use_labels
										SCREAMING_SNAKE_CASE     =       is_training
										SCREAMING_SNAKE_CASE     =       num_labels
										SCREAMING_SNAKE_CASE     =       initializer_range
										SCREAMING_SNAKE_CASE     =       scope





							def  _UpperCAmelCase  (       self							:						Tuple      )      ->       List[Any]:
										SCREAMING_SNAKE_CASE     =       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]      )

										SCREAMING_SNAKE_CASE     =       None
										SCREAMING_SNAKE_CASE     =       None
										if self.use_labels:
													SCREAMING_SNAKE_CASE     =       ids_tensor([self.batch_size]							,  self.num_labels      )
													SCREAMING_SNAKE_CASE     =       ids_tensor([self.batch_size, self.image_size, self.image_size]							,  self.num_labels      )

										SCREAMING_SNAKE_CASE     =       self.get_config()

										return config, pixel_values, labels, pixel_labels





							def  _UpperCAmelCase  (       self							:						List[Any]      )      ->       Union[str, Any]:
										return MobileViTConfig(
										    image_size=self.image_size							,  patch_size=self.patch_size							,  num_channels=self.num_channels							,  num_attention_heads=self.num_attention_heads							,  hidden_act=self.hidden_act							,  conv_kernel_size=self.conv_kernel_size							,  output_stride=self.output_stride							,  hidden_dropout_prob=self.hidden_dropout_prob							,  attention_probs_dropout_prob=self.attention_probs_dropout_prob							,  classifier_dropout_prob=self.classifier_dropout_prob							,  initializer_range=self.initializer_range							,  )





							def  _UpperCAmelCase  (       self							:						List[str]							,  a							:						Union[str, Any]							,  a							:						Tuple							,  a							:						Optional[int]							,  a							:						str      )      ->       Tuple:
										SCREAMING_SNAKE_CASE     =       TFMobileViTModel(config=a      )
										SCREAMING_SNAKE_CASE     =       model(a							,  training=a      )
										SCREAMING_SNAKE_CASE     =       SCREAMING_SNAKE_CASE     =       self.image_size // self.output_stride
										self.parent.assertEqual(
										    result.last_hidden_state.shape							,  (self.batch_size, self.last_hidden_size, expected_height, expected_width)      )





							def  _UpperCAmelCase  (       self							:						Any							,  a							:						Dict							,  a							:						Optional[Any]							,  a							:						List[Any]							,  a							:						List[str]      )      ->       Any:
										SCREAMING_SNAKE_CASE     =       self.num_labels
										SCREAMING_SNAKE_CASE     =       TFMobileViTForImageClassification(a      )
										SCREAMING_SNAKE_CASE     =       model(a							,  labels=a							,  training=a      )
										self.parent.assertEqual(result.logits.shape							,  (self.batch_size, self.num_labels)      )





							def  _UpperCAmelCase  (       self							:						Dict							,  a							:						List[str]							,  a							:						Union[str, Any]							,  a							:						List[Any]							,  a							:						Union[str, Any]      )      ->       Optional[int]:
										SCREAMING_SNAKE_CASE     =       self.num_labels
										SCREAMING_SNAKE_CASE     =       TFMobileViTForSemanticSegmentation(a      )
										SCREAMING_SNAKE_CASE     =       SCREAMING_SNAKE_CASE     =       self.image_size // self.output_stride

										SCREAMING_SNAKE_CASE     =       model(a							,  training=a      )
										self.parent.assertEqual(
										    result.logits.shape							,  (self.batch_size, self.num_labels, expected_height, expected_width)      )

										SCREAMING_SNAKE_CASE     =       model(a							,  labels=a							,  training=a      )
										self.parent.assertEqual(
										    result.logits.shape							,  (self.batch_size, self.num_labels, expected_height, expected_width)      )







							def  _UpperCAmelCase  (       self							:						Any      )      ->       Optional[int]:
										SCREAMING_SNAKE_CASE     =       self.prepare_config_and_inputs()
										SCREAMING_SNAKE_CASE  ,	SCREAMING_SNAKE_CASE  ,	SCREAMING_SNAKE_CASE  ,	SCREAMING_SNAKE_CASE     =       config_and_inputs
										SCREAMING_SNAKE_CASE     =       {"""pixel_values""": pixel_values}
										return config, inputs_dict





@require_tf
class       UpperCAmelCase_   ( A		,   A		,   unittest.TestCase							):




							'''simple docstring'''



							a__    	=  (
							    (TFMobileViTModel, TFMobileViTForImageClassification, TFMobileViTForSemanticSegmentation)
							    if is_tf_available()
							    else ()
							)
							a__    	=  (
							    {'''feature-extraction''': TFMobileViTModel, '''image-classification''': TFMobileViTForImageClassification}
							    if is_tf_available()
							    else {}
							)

							a__    	=  False
							a__    	=  False
							a__    	=  False
							a__    	=  False
							a__    	=  False





							def  _UpperCAmelCase  (       self							:						str      )      ->       Dict:
										SCREAMING_SNAKE_CASE     =       TFMobileViTModelTester(self      )
										SCREAMING_SNAKE_CASE     =       TFMobileViTConfigTester(self							,  config_class=a							,  has_text_modality=a      )





							def  _UpperCAmelCase  (       self							:						Optional[Any]      )      ->       Dict:
										self.config_tester.run_common_tests()





							@unittest.skip(reason="""MobileViT does not use inputs_embeds"""      )
							def  _UpperCAmelCase  (       self							:						Dict      )      ->       Tuple:
										pass





							@unittest.skip(reason="""MobileViT does not support input and output embeddings"""      )
							def  _UpperCAmelCase  (       self							:						List[Any]      )      ->       Tuple:
										pass





							@unittest.skip(reason="""MobileViT does not output attentions"""      )
							def  _UpperCAmelCase  (       self							:						str      )      ->       List[Any]:
										pass





							def  _UpperCAmelCase  (       self							:						Union[str, Any]      )      ->       List[Any]:
										SCREAMING_SNAKE_CASE  ,	SCREAMING_SNAKE_CASE     =       self.model_tester.prepare_config_and_inputs_for_common()

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

													SCREAMING_SNAKE_CASE     =       ["""pixel_values"""]
													self.assertListEqual(arg_names[:1]							,  a      )





							def  _UpperCAmelCase  (       self							:						Union[str, Any]      )      ->       List[Any]:
										SCREAMING_SNAKE_CASE     =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_model(*a      )





							def  _UpperCAmelCase  (       self							:						Optional[int]      )      ->       Union[str, Any]:
										def check_hidden_states_output(a							:						Dict							,  a							:						Union[str, Any]							,  a							:						Optional[Any]      ):
													SCREAMING_SNAKE_CASE     =       model_class(a      )

													SCREAMING_SNAKE_CASE     =       model(**self._prepare_for_class(a							,  a      )      )

													SCREAMING_SNAKE_CASE     =       outputs.hidden_states

													SCREAMING_SNAKE_CASE     =       5
													self.assertEqual(len(a      )							,  a      )

													# MobileViT's feature maps are of shape (batch_size, num_channels, height, width)
													# with the width and height being successively divided by 2.
													SCREAMING_SNAKE_CASE     =       2
													for i in range(len(a      )      ):
																self.assertListEqual(
																    list(hidden_states[i].shape[-2:]      )							,  [self.model_tester.image_size // divisor, self.model_tester.image_size // divisor]							,  )
																divisor *= 2

													self.assertEqual(self.model_tester.output_stride							,  divisor // 2      )

										SCREAMING_SNAKE_CASE  ,	SCREAMING_SNAKE_CASE     =       self.model_tester.prepare_config_and_inputs_for_common()

										for model_class in self.all_model_classes:
													SCREAMING_SNAKE_CASE     =       True
													check_hidden_states_output(a							,  a							,  a      )

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

													check_hidden_states_output(a							,  a							,  a      )





							def  _UpperCAmelCase  (       self							:						Optional[Any]      )      ->       List[str]:
										SCREAMING_SNAKE_CASE     =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_image_classification(*a      )





							def  _UpperCAmelCase  (       self							:						List[str]      )      ->       Tuple:
										SCREAMING_SNAKE_CASE     =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_semantic_segmentation(*a      )





							@unittest.skipIf(
							    not is_tf_available() or len(tf.config.list_physical_devices("""GPU"""      )      ) == 0							,  reason="""TF does not support backprop for grouped convolutions on CPU."""							,  )
							def  _UpperCAmelCase  (       self							:						Optional[int]      )      ->       Any:
										super().test_dataset_conversion()





							def  _UpperCAmelCase  (       self							:						Union[str, Any]							,  a							:						List[str]							,  a							:						Optional[int]							,  a							:						Any=2E-1							,  a							:						List[str]=2E-1      )      ->       Dict:
										self.assertTrue(np.allclose(a							,  a							,  atol=a							,  rtol=a      )      )





							@unittest.skipIf(
							    not is_tf_available() or len(tf.config.list_physical_devices("""GPU"""      )      ) == 0							,  reason="""TF does not support backprop for grouped convolutions on CPU."""							,  )
							@slow
							def  _UpperCAmelCase  (       self							:						Optional[int]      )      ->       str:
										SCREAMING_SNAKE_CASE  ,	SCREAMING_SNAKE_CASE     =       self.model_tester.prepare_config_and_inputs_for_common()

										for model_class in self.all_model_classes:
													# Since `TFMobileViTModel` cannot operate with the default `fit()` method.
													if model_class.__name__ != "TFMobileViTModel":
																SCREAMING_SNAKE_CASE     =       model_class(a      )
																if getattr(a							,  """hf_compute_loss"""							,  a      ):
																			super().test_keras_fit()





							def  _UpperCAmelCase  (       self							:						int      )      ->       Optional[Any]:
										SCREAMING_SNAKE_CASE  ,	SCREAMING_SNAKE_CASE     =       self.model_tester.prepare_config_and_inputs_for_common()
										for model_class in self.all_model_classes:
													# set an ignore index to correctly test the masked loss used in
													# `TFMobileViTForSemanticSegmentation`.
													if model_class.__name__ != "TFMobileViTForSemanticSegmentation":
																SCREAMING_SNAKE_CASE     =       5

													SCREAMING_SNAKE_CASE     =       model_class(a      )
													if getattr(a							,  """hf_compute_loss"""							,  a      ):
																# The number of elements in the loss should be the same as the number of elements in the label
																SCREAMING_SNAKE_CASE     =       self._prepare_for_class(inputs_dict.copy()							,  a							,  return_labels=a      )
																SCREAMING_SNAKE_CASE     =       prepared_for_class[
																    sorted(prepared_for_class.keys() - inputs_dict.keys()							,  reverse=a      )[0]
																]
																SCREAMING_SNAKE_CASE     =       added_label.shape.as_list()[:1]

																# Test that model correctly compute the loss with kwargs
																SCREAMING_SNAKE_CASE     =       self._prepare_for_class(inputs_dict.copy()							,  a							,  return_labels=a      )
																SCREAMING_SNAKE_CASE     =       {"""input_ids""", """pixel_values""", """input_features"""}
																SCREAMING_SNAKE_CASE     =       possible_input_names.intersection(set(a      )      ).pop()
																SCREAMING_SNAKE_CASE     =       prepared_for_class.pop(a      )

																SCREAMING_SNAKE_CASE     =       model(a							,  **a      )[0]
																self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]      )

																# Test that model correctly compute the loss when we mask some positions
																SCREAMING_SNAKE_CASE     =       self._prepare_for_class(inputs_dict.copy()							,  a							,  return_labels=a      )
																SCREAMING_SNAKE_CASE     =       {"""input_ids""", """pixel_values""", """input_features"""}
																SCREAMING_SNAKE_CASE     =       possible_input_names.intersection(set(a      )      ).pop()
																SCREAMING_SNAKE_CASE     =       prepared_for_class.pop(a      )
																if "labels" in prepared_for_class:
																			SCREAMING_SNAKE_CASE     =       prepared_for_class["""labels"""].numpy()
																			if len(labels.shape      ) > 1 and labels.shape[1] != 1:
																						# labels[0] = -100
																						SCREAMING_SNAKE_CASE     =       tf.convert_to_tensor(a      )
																						SCREAMING_SNAKE_CASE     =       model(a							,  **a      )[0]
																						self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]      )
																						self.assertTrue(not np.any(np.isnan(loss.numpy()      )      )      )

                # Test that model correctly compute the loss with a dict
																SCREAMING_SNAKE_CASE     =       self._prepare_for_class(inputs_dict.copy()							,  a							,  return_labels=a      )
																SCREAMING_SNAKE_CASE     =       model(a      )[0]
																self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]      )

																# Test that model correctly compute the loss with a tuple
																SCREAMING_SNAKE_CASE     =       self._prepare_for_class(inputs_dict.copy()							,  a							,  return_labels=a      )

																# Get keys that were added with the _prepare_for_class function
																SCREAMING_SNAKE_CASE     =       prepared_for_class.keys() - inputs_dict.keys()
																SCREAMING_SNAKE_CASE     =       inspect.signature(model.call      ).parameters
																SCREAMING_SNAKE_CASE     =       list(signature.keys()      )

																# Create a dictionary holding the location of the tensors in the tuple
																SCREAMING_SNAKE_CASE     =       {0: input_name}
																for label_key in label_keys:
																			SCREAMING_SNAKE_CASE     =       signature_names.index(a      )
																			SCREAMING_SNAKE_CASE     =       label_key
																SCREAMING_SNAKE_CASE     =       sorted(tuple_index_mapping.items()      )
																# Initialize a list with their default values, update the values and convert to a tuple
																SCREAMING_SNAKE_CASE     =       []

																for name in signature_names:
																			if name != "kwargs":
																						list_input.append(signature[name].default      )

																for index, value in sorted_tuple_index_mapping:
																			SCREAMING_SNAKE_CASE     =       prepared_for_class[value]

																SCREAMING_SNAKE_CASE     =       tuple(a      )

																# Send to model
																SCREAMING_SNAKE_CASE     =       model(tuple_input[:-1]      )[0]

																self.assertTrue(loss.shape.as_list() == expected_loss_size or loss.shape.as_list() == [1]      )







							@slow
							def  _UpperCAmelCase  (       self							:						str      )      ->       List[Any]:
										for model_name in TF_MOBILEVIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
													SCREAMING_SNAKE_CASE     =       TFMobileViTModel.from_pretrained(a      )
													self.assertIsNotNone(a      )





def        lowerCamelCase_     (     ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE     =       Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png""" )
			return image




@require_tf
class       UpperCAmelCase_   ( unittest.TestCase							):




							'''simple docstring'''



							@slow
							def  _UpperCAmelCase  (       self							:						Dict      )      ->       Dict:
										SCREAMING_SNAKE_CASE     =       TFMobileViTForImageClassification.from_pretrained("""apple/mobilevit-xx-small"""      )

										SCREAMING_SNAKE_CASE     =       MobileViTImageProcessor.from_pretrained("""apple/mobilevit-xx-small"""      )
										SCREAMING_SNAKE_CASE     =       prepare_img()
										SCREAMING_SNAKE_CASE     =       image_processor(images=a							,  return_tensors="""tf"""      )

										# forward pass
										SCREAMING_SNAKE_CASE     =       model(**a							,  training=a      )

										# verify the logits
										SCREAMING_SNAKE_CASE     =       tf.TensorShape((1, 1_000)      )
										self.assertEqual(outputs.logits.shape							,  a      )

										SCREAMING_SNAKE_CASE     =       tf.constant([-1.9364, -1.2327, -0.4653]      )

										tf.debugging.assert_near(outputs.logits[0, :3]							,  a							,  atol=1E-4							,  rtol=1E-0_4      )







							@slow
							def  _UpperCAmelCase  (       self							:						int      )      ->       Tuple:
										# `from_pt` will be removed
										SCREAMING_SNAKE_CASE     =       TFMobileViTForSemanticSegmentation.from_pretrained("""apple/deeplabv3-mobilevit-xx-small"""      )

										SCREAMING_SNAKE_CASE     =       MobileViTImageProcessor.from_pretrained("""apple/deeplabv3-mobilevit-xx-small"""      )

										SCREAMING_SNAKE_CASE     =       prepare_img()
										SCREAMING_SNAKE_CASE     =       image_processor(images=a							,  return_tensors="""tf"""      )

										# forward pass
										SCREAMING_SNAKE_CASE     =       model(inputs.pixel_values							,  training=a      )
										SCREAMING_SNAKE_CASE     =       outputs.logits

										# verify the logits
										SCREAMING_SNAKE_CASE     =       tf.TensorShape((1, 21, 32, 32)      )
										self.assertEqual(logits.shape							,  a      )

										SCREAMING_SNAKE_CASE     =       tf.constant(
										    [
										        [[6.9713, 6.9786, 7.2422], [7.2893, 7.2825, 7.4446], [7.6580, 7.8797, 7.9420]],
										        [[-10.6869, -10.3250, -10.3471], [-10.4228, -9.9868, -9.7132], [-11.0405, -11.0221, -10.7318]],
										        [[-3.3089, -2.8539, -2.6740], [-3.2706, -2.5621, -2.5108], [-3.2534, -2.6615, -2.6651]],
										    ]      )

										tf.debugging.assert_near(logits[0, :3, :3, :3]							,  a							,  rtol=1E-4							,  atol=1E-4      )






