





"""simple docstring"""
from functools import lru_cache






@lru_cache
def    A__							(     UpperCamelCase			):
							if not isinstance(UpperCamelCase   ,    UpperCamelCase			):
														raise TypeError("k must be an integer."			)
							if k < 0:
														raise ValueError("k integer must be greater or equal to zero."			)
							if k == 0:
														return 0
							elif k == 1:
														return 1
							else:
														return fibonacci(k - 1			) + fibonacci(k - 2			)






def    A__							(     UpperCamelCase   ,    UpperCamelCase			):
							A						=    len(UpperCamelCase			)
							# Find m such that F_m >= n where F_i is the i_th fibonacci number.
							A						=    0
							while True:
														if fibonacci(UpperCamelCase			) >= len_list:
																					A						=    i
																					break
														i += 1
							A						=    0
							while fibb_k > 0:
														A						=    min(
														    offset + fibonacci(fibb_k - 1			)   ,    len_list - 1			)  # Prevent out of range
														A						=    arr[index_k]
														if item_k_1 == val:
																					return index_k
														elif val < item_k_1:
																					fibb_k -= 1
														elif val > item_k_1:
																					offset += fibonacci(fibb_k - 1			)
																					fibb_k -= 2
							else:
														return -1


if __name__ == "__main__":
		import doctest

		doctest.testmod()









"""simple docstring"""
import inspect
import unittest

from transformers import ResNetConfig
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_backbone_common import BackboneTesterMixin
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 torch import nn

		from transformers import ResNetBackbone, ResNetForImageClassification, ResNetModel
		from transformers.models.resnet.modeling_resnet import RESNET_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
		from PIL import Image

		from transformers import AutoImageProcessor






class    _UpperCAmelCase  :


					def __init__(   self     :Optional[Any]	,			__UpperCamelCase     :Dict	,			__UpperCamelCase     :Optional[Any]=3	,			__UpperCamelCase     :Optional[int]=32	,			__UpperCamelCase     :str=3	,			__UpperCamelCase     :Union[str, Any]=10	,			__UpperCamelCase     :Union[str, Any]=[10, 20, 30, 40]	,			__UpperCamelCase     :int=[1, 1, 2, 1]	,			__UpperCamelCase     :Dict=True	,			__UpperCamelCase     :Optional[Any]=True	,			__UpperCamelCase     :Any="relu"	,			__UpperCamelCase     :Optional[Any]=3	,			__UpperCamelCase     :int=None	,			__UpperCamelCase     :str=["stage2", "stage3", "stage4"]	,			__UpperCamelCase     :str=[2, 3, 4]	,			):
												A						=    parent
												A						=    batch_size
												A						=    image_size
												A						=    num_channels
												A						=    embeddings_size
												A						=    hidden_sizes
												A						=    depths
												A						=    is_training
												A						=    use_labels
												A						=    hidden_act
												A						=    num_labels
												A						=    scope
												A						=    len(__UpperCamelCase						)
												A						=    out_features
												A						=    out_indices


					def       lowerCamelCase			(   self     :List[Any]						):
												A						=    floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]						)

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

												A						=    self.get_config()

												return config, pixel_values, labels


					def       lowerCamelCase			(   self     :Optional[Any]						):
												return ResNetConfig(
												    num_channels=self.num_channels	,			embeddings_size=self.embeddings_size	,			hidden_sizes=self.hidden_sizes	,			depths=self.depths	,			hidden_act=self.hidden_act	,			num_labels=self.num_labels	,			out_features=self.out_features	,			out_indices=self.out_indices	,			)


					def       lowerCamelCase			(   self     :int	,			__UpperCamelCase     :Optional[Any]	,			__UpperCamelCase     :str	,			__UpperCamelCase     :List[Any]						):
												A						=    ResNetModel(config=__UpperCamelCase						)
												model.to(__UpperCamelCase						)
												model.eval()
												A						=    model(__UpperCamelCase						)
												# expected last hidden states: B, C, H // 32, W // 32
												self.parent.assertEqual(
												    result.last_hidden_state.shape	,			(self.batch_size, self.hidden_sizes[-1], self.image_size // 32, self.image_size // 32)	,			)


					def       lowerCamelCase			(   self     :int	,			__UpperCamelCase     :Optional[Any]	,			__UpperCamelCase     :str	,			__UpperCamelCase     :str						):
												A						=    self.num_labels
												A						=    ResNetForImageClassification(__UpperCamelCase						)
												model.to(__UpperCamelCase						)
												model.eval()
												A						=    model(__UpperCamelCase	,			labels=__UpperCamelCase						)
												self.parent.assertEqual(result.logits.shape	,			(self.batch_size, self.num_labels)						)


					def       lowerCamelCase			(   self     :Dict	,			__UpperCamelCase     :Optional[Any]	,			__UpperCamelCase     :Optional[int]	,			__UpperCamelCase     :str						):
												A						=    ResNetBackbone(config=__UpperCamelCase						)
												model.to(__UpperCamelCase						)
												model.eval()
												A						=    model(__UpperCamelCase						)

												# verify feature maps
												self.parent.assertEqual(len(result.feature_maps						)	,			len(config.out_features						)						)
												self.parent.assertListEqual(list(result.feature_maps[0].shape						)	,			[self.batch_size, self.hidden_sizes[1], 4, 4]						)

												# verify channels
												self.parent.assertEqual(len(model.channels						)	,			len(config.out_features						)						)
												self.parent.assertListEqual(model.channels	,			config.hidden_sizes[1:]						)

												# verify backbone works with out_features=None
												A						=    None
												A						=    ResNetBackbone(config=__UpperCamelCase						)
												model.to(__UpperCamelCase						)
												model.eval()
												A						=    model(__UpperCamelCase						)

												# verify feature maps
												self.parent.assertEqual(len(result.feature_maps						)	,			1						)
												self.parent.assertListEqual(list(result.feature_maps[0].shape						)	,			[self.batch_size, self.hidden_sizes[-1], 1, 1]						)

												# verify channels
												self.parent.assertEqual(len(model.channels						)	,			1						)
												self.parent.assertListEqual(model.channels	,			[config.hidden_sizes[-1]]						)


					def       lowerCamelCase			(   self     :List[Any]						):
												A						=    self.prepare_config_and_inputs()
												A,      A,      A						=    config_and_inputs
												A						=    {"pixel_values": pixel_values}
												return config, inputs_dict







@require_torch
class    _UpperCAmelCase  (      lowercase_	,				lowercase_	,				unittest.TestCase					):
					UpperCamelCase						=				(
					    (
					        ResNetModel,
					        ResNetForImageClassification,
					        ResNetBackbone,
					    )
					    if is_torch_available()
					    else ()
					)
					UpperCamelCase						=				(
					    {'''feature-extraction''': ResNetModel, '''image-classification''': ResNetForImageClassification}
					    if is_torch_available()
					    else {}
					)

					UpperCamelCase						=				True
					UpperCamelCase						=				False
					UpperCamelCase						=				False
					UpperCamelCase						=				False
					UpperCamelCase						=				False


					def       lowerCamelCase			(   self     :List[Any]						):
												A						=    ResNetModelTester(self						)
												A						=    ConfigTester(self	,			config_class=__UpperCamelCase	,			has_text_modality=__UpperCamelCase						)


					def       lowerCamelCase			(   self     :List[Any]						):
												self.create_and_test_config_common_properties()
												self.config_tester.create_and_test_config_to_json_string()
												self.config_tester.create_and_test_config_to_json_file()
												self.config_tester.create_and_test_config_from_and_save_pretrained()
												self.config_tester.create_and_test_config_with_num_labels()
												self.config_tester.check_config_can_be_init_without_params()
												self.config_tester.check_config_arguments_init()


					def       lowerCamelCase			(   self     :Union[str, Any]						):
												return


					@unittest.skip(reason="ResNet does not use inputs_embeds"						)
					def       lowerCamelCase			(   self     :Optional[int]						):
												pass


					@unittest.skip(reason="ResNet does not support input and output embeddings"						)
					def       lowerCamelCase			(   self     :Optional[Any]						):
												pass


					def       lowerCamelCase			(   self     :List[Any]						):
												A,      A						=    self.model_tester.prepare_config_and_inputs_for_common()

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

																			A						=    ["pixel_values"]
																			self.assertListEqual(arg_names[:1]	,			__UpperCamelCase						)


					def       lowerCamelCase			(   self     :Tuple						):
												A						=    self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_model(*__UpperCamelCase						)


					def       lowerCamelCase			(   self     :Union[str, Any]						):
												A						=    self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_backbone(*__UpperCamelCase						)


					def       lowerCamelCase			(   self     :Optional[Any]						):
												A,      A						=    self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			A						=    model_class(config=__UpperCamelCase						)
																			for name, module in model.named_modules():
																										if isinstance(__UpperCamelCase	,			(nn.BatchNormad, nn.GroupNorm)						):
																																	self.assertTrue(
																																	    torch.all(module.weight == 1						)	,			msg=f"Parameter {name} of model {model_class} seems not properly initialized"	,			)
																																	self.assertTrue(
																																	    torch.all(module.bias == 0						)	,			msg=f"Parameter {name} of model {model_class} seems not properly initialized"	,			)


					def       lowerCamelCase			(   self     :Optional[Any]						):
												def check_hidden_states_output(__UpperCamelCase     :int	,			__UpperCamelCase     :Any	,			__UpperCamelCase     :Union[str, Any]						):
																			A						=    model_class(__UpperCamelCase						)
																			model.to(__UpperCamelCase						)
																			model.eval()

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

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

																			A						=    self.model_tester.num_stages
																			self.assertEqual(len(__UpperCamelCase						)	,			expected_num_stages + 1						)

																			# ResNet's feature maps are of shape (batch_size, num_channels, height, width)
																			self.assertListEqual(
																			    list(hidden_states[0].shape[-2:]						)	,			[self.model_tester.image_size // 4, self.model_tester.image_size // 4]	,			)

												A,      A						=    self.model_tester.prepare_config_and_inputs_for_common()
												A						=    ["basic", "bottleneck"]
												for model_class in self.all_model_classes:
																			for layer_type in layers_type:
																										A						=    layer_type
																										A						=    True
																										check_hidden_states_output(__UpperCamelCase	,			__UpperCamelCase	,			__UpperCamelCase						)

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

																										check_hidden_states_output(__UpperCamelCase	,			__UpperCamelCase	,			__UpperCamelCase						)


					@unittest.skip(reason="ResNet does not use feedforward chunking"						)
					def       lowerCamelCase			(   self     :Tuple						):
												pass


					def       lowerCamelCase			(   self     :Optional[int]						):
												A						=    self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_image_classification(*__UpperCamelCase						)


					@slow
					def       lowerCamelCase			(   self     :Union[str, Any]						):
												for model_name in RESNET_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																			A						=    ResNetModel.from_pretrained(__UpperCamelCase						)
																			self.assertIsNotNone(__UpperCamelCase						)







def    A__							(     ):
							A						=    Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"			)
							return image






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


					@cached_property
					def       lowerCamelCase			(   self     :List[Any]						):
												return (
												    AutoImageProcessor.from_pretrained(RESNET_PRETRAINED_MODEL_ARCHIVE_LIST[0]						)
												    if is_vision_available()
												    else None
												)


					@slow
					def       lowerCamelCase			(   self     :Dict						):
												A						=    ResNetForImageClassification.from_pretrained(RESNET_PRETRAINED_MODEL_ARCHIVE_LIST[0]						).to(__UpperCamelCase						)

												A						=    self.default_image_processor
												A						=    prepare_img()
												A						=    image_processor(images=__UpperCamelCase	,			return_tensors="pt"						).to(__UpperCamelCase						)

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

												# verify the logits
												A						=    torch.Size((1, 10_00)						)
												self.assertEqual(outputs.logits.shape	,			__UpperCamelCase						)

												A						=    torch.tensor([-11.1_069, -9.7_877, -8.3_777]						).to(__UpperCamelCase						)

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







@require_torch
class    _UpperCAmelCase  (      lowercase_	,				unittest.TestCase					):
					UpperCamelCase						=				(ResNetBackbone,) if is_torch_available() else ()
					UpperCamelCase						=				False
					UpperCamelCase						=				ResNetConfig


					def       lowerCamelCase			(   self     :Dict						):
												A						=    ResNetModelTester(self						)


