





"""simple docstring"""




def 		UpperCAmelCase__						(	_UpperCAmelCase					,   _UpperCAmelCase   ):






  """simple docstring"""





  A_    :			Dict									=    []
  A_    :			Optional[Any]									=    len(a_   )
  for i in range(a_   ):
    A_    :			int									=    []
    for j in range(a_   ):
      A_    :			Tuple									=    0
      for k in range(a_   ):
        A_    :			Optional[int]									=    val + matrix_a[i][k] * matrix_b[k][j]
      list_a.append(a_   )
    matrix_c.append(a_   )
  return matrix_c





def 		UpperCAmelCase__						(	_UpperCAmelCase   ):






  """simple docstring"""





  return [[int(row == column   ) for column in range(a_   )] for row in range(a_   )]





def 		UpperCAmelCase__						(	_UpperCAmelCase   ):






  """simple docstring"""





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





def 		UpperCAmelCase__						(	_UpperCAmelCase   ):






  """simple docstring"""





  if n <= 1:
    return n
  A_    :			Tuple									=    0
  A_    :			str									=    1
  for _ in range(2					,   n + 1   ):
    A_    :			str									=    fiba, fiba + fiba
  return fiba





def 		UpperCAmelCase__						(	):






  """simple docstring"""





  for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
    A_    :			Any									=    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(a_   )} and using bruteforce is """
        f"""{nth_fibonacci_bruteforce(a_   )}\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()




'''simple docstring'''





import inspect
import unittest

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

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_MAPPING, GLPNConfig, GLPNForDepthEstimation, GLPNModel
  from transformers.models.glpn.modeling_glpn import GLPN_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
  from PIL import Image

  from transformers import GLPNImageProcessor


class 							_lowerCAmelCase	(  __A							):


 """simple docstring"""

 def       UpperCAmelCase_       (      self  )    ->    int:
    A_  :		Tuple						=					self.config_class(**self.inputs_dict  )
    self.parent.assertTrue(hasattr(_lowerCamelCase					,    """hidden_sizes"""  )  )
    self.parent.assertTrue(hasattr(_lowerCamelCase					,    """num_attention_heads"""  )  )
    self.parent.assertTrue(hasattr(_lowerCamelCase					,    """num_encoder_blocks"""  )  )


class 							_lowerCAmelCase	:


 """simple docstring"""

 def __init__(      self					,    _lowerCamelCase					,    _lowerCamelCase=13					,    _lowerCamelCase=64					,    _lowerCamelCase=3					,    _lowerCamelCase=4					,    _lowerCamelCase=[2, 2, 2, 2]					,    _lowerCamelCase=[8, 4, 2, 1]					,    _lowerCamelCase=[16, 32, 64, 128]					,    _lowerCamelCase=[1, 4, 8, 16]					,    _lowerCamelCase=[1, 2, 4, 8]					,    _lowerCamelCase=True					,    _lowerCamelCase=True					,    _lowerCamelCase="gelu"					,    _lowerCamelCase=0.1					,    _lowerCamelCase=0.1					,    _lowerCamelCase=0.02					,    _lowerCamelCase=16					,    _lowerCamelCase=3					,    _lowerCamelCase=None					,    )    ->    Optional[int]:
    A_  :		int						=					parent
    A_  :		int						=					batch_size
    A_  :		Optional[int]						=					image_size
    A_  :		str						=					num_channels
    A_  :		Optional[Any]						=					num_encoder_blocks
    A_  :		List[str]						=					sr_ratios
    A_  :		int						=					depths
    A_  :		str						=					hidden_sizes
    A_  :		Optional[int]						=					downsampling_rates
    A_  :		Any						=					num_attention_heads
    A_  :		List[str]						=					is_training
    A_  :		Optional[Any]						=					use_labels
    A_  :		List[str]						=					hidden_act
    A_  :		Tuple						=					hidden_dropout_prob
    A_  :		Optional[int]						=					attention_probs_dropout_prob
    A_  :		Optional[int]						=					initializer_range
    A_  :		str						=					decoder_hidden_size
    A_  :		Optional[Any]						=					num_labels
    A_  :		List[Any]						=					scope







 def       UpperCAmelCase_       (      self  )    ->    List[Any]:
    A_  :		List[Any]						=					floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]  )

    A_  :		Dict						=					None
    if self.use_labels:
       A_  :		Optional[Any]						=					ids_tensor([self.batch_size, self.image_size, self.image_size]					,    self.num_labels  )

    A_  :		Any						=					self.get_config()
    return config, pixel_values, labels







 def       UpperCAmelCase_       (      self  )    ->    Tuple:
    return GLPNConfig(
        image_size=self.image_size					,    num_channels=self.num_channels					,    num_encoder_blocks=self.num_encoder_blocks					,    depths=self.depths					,    hidden_sizes=self.hidden_sizes					,    num_attention_heads=self.num_attention_heads					,    hidden_act=self.hidden_act					,    hidden_dropout_prob=self.hidden_dropout_prob					,    attention_probs_dropout_prob=self.attention_probs_dropout_prob					,    initializer_range=self.initializer_range					,    decoder_hidden_size=self.decoder_hidden_size					,    )







 def       UpperCAmelCase_       (      self					,    _lowerCamelCase					,    _lowerCamelCase					,    _lowerCamelCase  )    ->    str:
    A_  :		Tuple						=					GLPNModel(config=_lowerCamelCase  )
    model.to(_lowerCamelCase  )
    model.eval()
    A_  :		Optional[Any]						=					model(_lowerCamelCase  )
    A_  :		Optional[int]						=					self.image_size // (self.downsampling_rates[-1] * 2)
    self.parent.assertEqual(
        result.last_hidden_state.shape					,    (self.batch_size, self.hidden_sizes[-1], expected_height, expected_width)  )







 def       UpperCAmelCase_       (      self					,    _lowerCamelCase					,    _lowerCamelCase					,    _lowerCamelCase  )    ->    Optional[int]:
    A_  :		Tuple						=					self.num_labels
    A_  :		Any						=					GLPNForDepthEstimation(_lowerCamelCase  )
    model.to(_lowerCamelCase  )
    model.eval()
    A_  :		Dict						=					model(_lowerCamelCase  )
    self.parent.assertEqual(result.predicted_depth.shape					,    (self.batch_size, self.image_size, self.image_size)  )
    A_  :		Optional[int]						=					model(_lowerCamelCase					,    labels=_lowerCamelCase  )
    self.parent.assertEqual(result.predicted_depth.shape					,    (self.batch_size, self.image_size, self.image_size)  )







 def       UpperCAmelCase_       (      self  )    ->    Dict:
    A_  :		Optional[Any]						=					self.prepare_config_and_inputs()
    A_						,  A_						,  A_  :		Tuple						=					config_and_inputs
    A_  :		Dict						=					{"""pixel_values""": pixel_values}
    return config, inputs_dict


@require_torch
class 							_lowerCAmelCase	(  __A,							__A,							unittest.TestCase							):


 """simple docstring"""

 lowerCamelCase									=     (GLPNModel, GLPNForDepthEstimation) if is_torch_available() else ()
 lowerCamelCase									=     (
     {'''depth-estimation''': GLPNForDepthEstimation, '''feature-extraction''': GLPNModel} if is_torch_available() else {}
 )

 lowerCamelCase									=     False
 lowerCamelCase									=     False
 lowerCamelCase									=     False







 def       UpperCAmelCase_       (      self  )    ->    Tuple:
    A_  :		Optional[Any]						=					GLPNModelTester(self  )
    A_  :		Dict						=					GLPNConfigTester(self					,    config_class=_lowerCamelCase  )







 def       UpperCAmelCase_       (      self  )    ->    Optional[int]:
    self.config_tester.run_common_tests()







 def       UpperCAmelCase_       (      self  )    ->    List[str]:
    A_  :		int						=					self.model_tester.prepare_config_and_inputs()
    self.model_tester.create_and_check_model(*_lowerCamelCase  )







 def       UpperCAmelCase_       (      self  )    ->    List[str]:
    A_  :		Dict						=					self.model_tester.prepare_config_and_inputs()
    self.model_tester.create_and_check_for_depth_estimation(*_lowerCamelCase  )







 @unittest.skip("""GLPN does not use inputs_embeds"""  )
 def       UpperCAmelCase_       (      self  )    ->    List[Any]:
    pass







 @unittest.skip("""GLPN does not have get_input_embeddings method and get_output_embeddings methods"""  )
 def       UpperCAmelCase_       (      self  )    ->    Any:
    pass







 def       UpperCAmelCase_       (      self  )    ->    Dict:
    A_						,  A_  :		Union[str, Any]						=					self.model_tester.prepare_config_and_inputs_for_common()

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

       A_  :		Dict						=					["""pixel_values"""]
       self.assertListEqual(arg_names[:1]					,    _lowerCamelCase  )







 def       UpperCAmelCase_       (      self  )    ->    Dict:
    A_						,  A_  :		List[str]						=					self.model_tester.prepare_config_and_inputs_for_common()
    A_  :		Optional[Any]						=					True

    for model_class in self.all_model_classes:
       A_  :		int						=					True
       A_  :		str						=					False
       A_  :		Any						=					True
       A_  :		Dict						=					model_class(_lowerCamelCase  )
       model.to(_lowerCamelCase  )
       model.eval()
       with torch.no_grad():
          A_  :		List[str]						=					model(**self._prepare_for_class(_lowerCamelCase					,    _lowerCamelCase  )  )
       A_  :		Union[str, Any]						=					outputs.attentions

       A_  :		List[str]						=					sum(self.model_tester.depths  )
       self.assertEqual(len(_lowerCamelCase  )					,    _lowerCamelCase  )

       # check that output_attentions also work using config
       del inputs_dict["output_attentions"]
       A_  :		Dict						=					True
       A_  :		List[str]						=					model_class(_lowerCamelCase  )
       model.to(_lowerCamelCase  )
       model.eval()
       with torch.no_grad():
          A_  :		Any						=					model(**self._prepare_for_class(_lowerCamelCase					,    _lowerCamelCase  )  )
       A_  :		str						=					outputs.attentions

       self.assertEqual(len(_lowerCamelCase  )					,    _lowerCamelCase  )

       # verify the first attentions (first block, first layer)
       A_  :		List[Any]						=					(self.model_tester.image_size // 4) ** 2
       A_  :		str						=					(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
       self.assertListEqual(
           list(attentions[0].shape[-3:]  )					,    [self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]					,    )

       # verify the last attentions (last block, last layer)
       A_  :		Optional[Any]						=					(self.model_tester.image_size // 32) ** 2
       A_  :		Optional[Any]						=					(self.model_tester.image_size // (32 * self.model_tester.sr_ratios[-1])) ** 2
       self.assertListEqual(
           list(attentions[-1].shape[-3:]  )					,    [self.model_tester.num_attention_heads[-1], expected_seq_len, expected_reduced_seq_len]					,    )
       A_  :		str						=					len(_lowerCamelCase  )

       # Check attention is always last and order is fine
       A_  :		Union[str, Any]						=					True
       A_  :		str						=					True
       A_  :		Tuple						=					model_class(_lowerCamelCase  )
       model.to(_lowerCamelCase  )
       model.eval()
       with torch.no_grad():
          A_  :		Dict						=					model(**self._prepare_for_class(_lowerCamelCase					,    _lowerCamelCase  )  )

       self.assertEqual(out_len + 1					,    len(_lowerCamelCase  )  )

       A_  :		Any						=					outputs.attentions

       self.assertEqual(len(_lowerCamelCase  )					,    _lowerCamelCase  )
       # verify the first attentions (first block, first layer)
       A_  :		List[Any]						=					(self.model_tester.image_size // 4) ** 2
       A_  :		Optional[int]						=					(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
       self.assertListEqual(
           list(self_attentions[0].shape[-3:]  )					,    [self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]					,    )







 def       UpperCAmelCase_       (      self  )    ->    Dict:
    def check_hidden_states_output(_lowerCamelCase					,    _lowerCamelCase					,    _lowerCamelCase  ):
       A_  :		List[Any]						=					model_class(_lowerCamelCase  )
       model.to(_lowerCamelCase  )
       model.eval()

       with torch.no_grad():
          A_  :		Tuple						=					model(**self._prepare_for_class(_lowerCamelCase					,    _lowerCamelCase  )  )

       A_  :		List[str]						=					outputs.hidden_states

       A_  :		Dict						=					self.model_tester.num_encoder_blocks
       self.assertEqual(len(_lowerCamelCase  )					,    _lowerCamelCase  )

       # verify the first hidden states (first block)
       self.assertListEqual(
           list(hidden_states[0].shape[-3:]  )					,    [
               self.model_tester.hidden_sizes[0],
               self.model_tester.image_size // 4,
               self.model_tester.image_size // 4,
           ]					,    )

    A_						,  A_  :		Optional[int]						=					self.model_tester.prepare_config_and_inputs_for_common()

    for model_class in self.all_model_classes:
       A_  :		Any						=					True
       check_hidden_states_output(_lowerCamelCase					,    _lowerCamelCase					,    _lowerCamelCase  )

       # check that output_hidden_states also work using config
       del inputs_dict["output_hidden_states"]
       A_  :		Optional[Any]						=					True

       check_hidden_states_output(_lowerCamelCase					,    _lowerCamelCase					,    _lowerCamelCase  )







 def       UpperCAmelCase_       (      self  )    ->    Optional[Any]:
    if not self.model_tester.is_training:
       return

    A_						,  A_  :		Any						=					self.model_tester.prepare_config_and_inputs_for_common()
    A_  :		Union[str, Any]						=					True

    for model_class in self.all_model_classes:
       if model_class in get_values(_lowerCamelCase  ):
          continue
       # TODO: remove the following 3 lines once we have a MODEL_FOR_DEPTH_ESTIMATION_MAPPING
       # this can then be incorporated into _prepare_for_class in test_modeling_common.py
       if model_class.__name__ == "GLPNForDepthEstimation":
          A_						,  A_						,  A_						,  A_  :		Any						=					inputs_dict["""pixel_values"""].shape
          A_  :		List[Any]						=					torch.zeros(
              [self.model_tester.batch_size, height, width]					,    device=_lowerCamelCase  ).long()
       A_  :		Union[str, Any]						=					model_class(_lowerCamelCase  )
       model.to(_lowerCamelCase  )
       model.train()
       A_  :		List[str]						=					self._prepare_for_class(_lowerCamelCase					,    _lowerCamelCase					,    return_labels=_lowerCamelCase  )
       A_  :		Dict						=					model(**_lowerCamelCase  ).loss
       loss.backward()







 @slow
 def       UpperCAmelCase_       (      self  )    ->    Dict:
    for model_name in GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
       A_  :		Union[str, Any]						=					GLPNModel.from_pretrained(_lowerCamelCase  )
       self.assertIsNotNone(_lowerCamelCase  )



def     UpperCAmelCase     (    )   ->       int:



   """simple docstring"""






   A_  :		int						=					Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""		)
   return image







@require_torch
@require_vision
@slow
class 							_lowerCAmelCase	(  unittest.TestCase							):


 """simple docstring"""

 @slow
 def       UpperCAmelCase_       (      self  )    ->    Tuple:
    A_  :		Tuple						=					GLPNImageProcessor.from_pretrained(GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[0]  )
    A_  :		List[Any]						=					GLPNForDepthEstimation.from_pretrained(GLPN_PRETRAINED_MODEL_ARCHIVE_LIST[0]  ).to(_lowerCamelCase  )

    A_  :		str						=					prepare_img()
    A_  :		int						=					image_processor(images=_lowerCamelCase					,    return_tensors="""pt"""  ).to(_lowerCamelCase  )

    # forward pass
    with torch.no_grad():
       A_  :		Optional[int]						=					model(**_lowerCamelCase  )

    # verify the predicted depth
    A_  :		List[Any]						=					torch.Size([1, 480, 640]  )
    self.assertEqual(outputs.predicted_depth.shape					,    _lowerCamelCase  )

    A_  :		Union[str, Any]						=					torch.tensor(
        [[3.4291, 2.7865, 2.5151], [3.2841, 2.7021, 2.3502], [3.1147, 2.4625, 2.2481]]  ).to(_lowerCamelCase  )

    self.assertTrue(torch.allclose(outputs.predicted_depth[0, :3, :3]					,    _lowerCamelCase					,    atol=1e-4  )  )
