

_UpperCAmelCase						:  int									=			range(2, 20 + 1)
_UpperCAmelCase						:  Dict									=			[10**k for k in range(ks[-1] + 1)]
_UpperCAmelCase						:  dict[int, dict[int, list[list[int]]]]									=			{}





def    __lowerCamelCase      (					UpperCamelCase__  ,				UpperCamelCase__  ,				UpperCamelCase__  ,				UpperCamelCase__ ):







							'''simple docstring'''






							snake_case_     							=       sum(a_i[j] for j in range(UpperCamelCase__  ,				len(UpperCamelCase__ ) ) )
							snake_case_     							=       sum(a_i[j] * base[j] for j in range(min(len(UpperCamelCase__ )  ,				UpperCamelCase__ ) ) )

							snake_case_							,       snake_case_     							=       0, 0
							snake_case_     							=       n - i

							snake_case_     							=       memo.get(UpperCamelCase__ )

							if sub_memo is not None:
														snake_case_     							=       sub_memo.get(UpperCamelCase__ )

														if jumps is not None and len(UpperCamelCase__ ) > 0:
																					# find and make the largest jump without going over
																					snake_case_     							=       -1
																					for _k in range(len(UpperCamelCase__ ) - 1  ,				-1  ,				-1 ):
																												if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
																																			snake_case_     							=       _k
																																			break

																					if max_jump >= 0:
																												snake_case_							,       snake_case_							,       snake_case_     							=       jumps[max_jump]
																												# since the difference between jumps is cached, add c
																												snake_case_     							=       diff + c
																												for j in range(min(UpperCamelCase__  ,				len(UpperCamelCase__ ) ) ):
																																			snake_case_							,       snake_case_     							=       divmod(UpperCamelCase__  ,				10 )
																												if new_c > 0:
																																			add(UpperCamelCase__  ,				UpperCamelCase__  ,				UpperCamelCase__ )

														else:
																					snake_case_     							=       []
							else:
														snake_case_     							=       {c: []}
														snake_case_     							=       sub_memo

							if dn >= max_dn or c + diff >= base[k]:
														return diff, dn

							if k > ks[0]:
														while True:
																					# keep doing smaller jumps
																					snake_case_							,       snake_case_     							=       next_term(UpperCamelCase__  ,				k - 1  ,				i + dn  ,				UpperCamelCase__ )
																					diff += _diff
																					dn += terms_jumped

																					if dn >= max_dn or c + diff >= base[k]:
																												break
							else:
														# would be too small a jump, just compute sequential terms instead
														snake_case_							,       snake_case_     							=       compute(UpperCamelCase__  ,				UpperCamelCase__  ,				i + dn  ,				UpperCamelCase__ )
														diff += _diff
														dn += terms_jumped

							snake_case_     							=       sub_memo[c]

							# keep jumps sorted by # of terms skipped
							snake_case_     							=       0
							while j < len(UpperCamelCase__ ):
														if jumps[j][1] > dn:
																					break
														j += 1

							# cache the jump for this value digitsum(b) and c
							sub_memo[c].insert(UpperCamelCase__  ,				(diff, dn, k) )
							return (diff, dn)





def    __lowerCamelCase      (					UpperCamelCase__  ,				UpperCamelCase__  ,				UpperCamelCase__  ,				UpperCamelCase__ ):







							'''simple docstring'''






							if i >= n:
														return 0, i
							if k > len(UpperCamelCase__ ):
														a_i.extend([0 for _ in range(k - len(UpperCamelCase__ ) )] )

							# note: a_i -> b * 10^k + c
							# ds_b -> digitsum(b)
							# ds_c -> digitsum(c)
							snake_case_     							=       i
							snake_case_							,       snake_case_							,       snake_case_     							=       0, 0, 0
							for j in range(len(UpperCamelCase__ ) ):
														if j >= k:
																					ds_b += a_i[j]
														else:
																					ds_c += a_i[j]

							while i < n:
														i += 1
														snake_case_     							=       ds_c + ds_b
														diff += addend
														snake_case_     							=       0
														for j in range(UpperCamelCase__ ):
																					snake_case_     							=       a_i[j] + addend
																					snake_case_							,       snake_case_     							=       divmod(UpperCamelCase__  ,				10 )

																					ds_c += a_i[j]

														if addend > 0:
																					break

							if addend > 0:
														add(UpperCamelCase__  ,				UpperCamelCase__  ,				UpperCamelCase__ )
							return diff, i - start_i





def    __lowerCamelCase      (					UpperCamelCase__  ,				UpperCamelCase__  ,				UpperCamelCase__ ):







							'''simple docstring'''






							for j in range(UpperCamelCase__  ,				len(UpperCamelCase__ ) ):
														snake_case_     							=       digits[j] + addend
														if s >= 10:
																					snake_case_							,       snake_case_     							=       divmod(UpperCamelCase__  ,				10 )
																					snake_case_     							=       addend // 10 + quotient
														else:
																					snake_case_     							=       s
																					snake_case_     							=       addend // 10

														if addend == 0:
																					break

							while addend > 0:
														snake_case_							,       snake_case_     							=       divmod(UpperCamelCase__  ,				10 )
														digits.append(UpperCamelCase__ )





def    __lowerCamelCase      (					UpperCamelCase__ = 10**15 ):







							'''simple docstring'''






							snake_case_     							=       [1]
							snake_case_     							=       1
							snake_case_     							=       0
							while True:
														snake_case_							,       snake_case_     							=       next_term(UpperCamelCase__  ,				20  ,				i + dn  ,				UpperCamelCase__ )
														dn += terms_jumped
														if dn == n - i:
																					break

							snake_case_     							=       0
							for j in range(len(UpperCamelCase__ ) ):
														a_n += digits[j] * 10**j
							return a_n


if __name__ == "__main__":
					print(F'''{solution() = }''')







import inspect
import math
import tempfile
import unittest

import numpy as np

from transformers import ViTMAEConfig
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 torch import nn

					from transformers import ViTMAEForPreTraining, ViTMAEModel
					from transformers.models.vit.modeling_vit import VIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
					from PIL import Image

					from transformers import ViTImageProcessor







class 					lowercase							:




				def __init__(   self ,  snake_case ,  snake_case=13 ,  snake_case=30 ,  snake_case=2 ,  snake_case=3 ,  snake_case=True ,  snake_case=True ,  snake_case=32 ,  snake_case=5 ,  snake_case=4 ,  snake_case=37 ,  snake_case="gelu" ,  snake_case=0.1 ,  snake_case=0.1 ,  snake_case=10 ,  snake_case=0.02 ,  snake_case=3 ,  snake_case=0.6 ,  snake_case=None ,  ):
											snake_case_     							=       parent
											snake_case_     							=       batch_size
											snake_case_     							=       image_size
											snake_case_     							=       patch_size
											snake_case_     							=       num_channels
											snake_case_     							=       is_training
											snake_case_     							=       use_labels
											snake_case_     							=       hidden_size
											snake_case_     							=       num_hidden_layers
											snake_case_     							=       num_attention_heads
											snake_case_     							=       intermediate_size
											snake_case_     							=       hidden_act
											snake_case_     							=       hidden_dropout_prob
											snake_case_     							=       attention_probs_dropout_prob
											snake_case_     							=       type_sequence_label_size
											snake_case_     							=       initializer_range
											snake_case_     							=       mask_ratio
											snake_case_     							=       scope

											# in ViTMAE, the expected sequence length = (num_patches + 1) * (1 - config.mask_ratio), rounded above
											# (we add 1 for the [CLS] token)
											snake_case_     							=       (image_size // patch_size) ** 2
											snake_case_     							=       int(math.ceil((1 - mask_ratio) * (num_patches + 1)			)			)




				def        a				(   self			):
											snake_case_     							=       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]			)

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

											snake_case_     							=       self.get_config()

											return config, pixel_values, labels




				def        a				(   self			):
											return ViTMAEConfig(
											    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=snake_case ,  initializer_range=self.initializer_range ,  mask_ratio=self.mask_ratio ,  )




				def        a				(   self ,  snake_case ,  snake_case ,  snake_case			):
											snake_case_     							=       ViTMAEModel(config=snake_case			)
											model.to(snake_case			)
											model.eval()
											snake_case_     							=       model(snake_case			)
											self.parent.assertEqual(result.last_hidden_state.shape ,  (self.batch_size, self.seq_length, self.hidden_size)			)




				def        a				(   self ,  snake_case ,  snake_case ,  snake_case			):
											snake_case_     							=       ViTMAEForPreTraining(snake_case			)
											model.to(snake_case			)
											model.eval()
											snake_case_     							=       model(snake_case			)
											snake_case_     							=       (self.image_size // self.patch_size) ** 2
											snake_case_     							=       self.patch_size**2 * self.num_channels
											self.parent.assertEqual(result.logits.shape ,  (self.batch_size, num_patches, expected_num_channels)			)

											# test greyscale images
											snake_case_     							=       1
											snake_case_     							=       ViTMAEForPreTraining(snake_case			)
											model.to(snake_case			)
											model.eval()
											snake_case_     							=       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]			)
											snake_case_     							=       model(snake_case			)
											snake_case_     							=       self.patch_size**2
											self.parent.assertEqual(result.logits.shape ,  (self.batch_size, num_patches, expected_num_channels)			)




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







@require_torch
class 					lowercase							(			lowercase_      ,    lowercase_      ,    unittest.TestCase     ):
				__SCREAMING_SNAKE_CASE   :					Dict			     =     (ViTMAEModel, ViTMAEForPreTraining) if is_torch_available() else ()
				__SCREAMING_SNAKE_CASE   :					Union[str, Any]			     =     {'''feature-extraction''': ViTMAEModel} if is_torch_available() else {}

				__SCREAMING_SNAKE_CASE   :					List[Any]			     =     False
				__SCREAMING_SNAKE_CASE   :					Union[str, Any]			     =     False
				__SCREAMING_SNAKE_CASE   :					List[Any]			     =     False
				__SCREAMING_SNAKE_CASE   :					Union[str, Any]			     =     False




				def        a				(   self			):
											snake_case_     							=       ViTMAEModelTester(self			)
											snake_case_     							=       ConfigTester(self ,  config_class=snake_case ,  has_text_modality=snake_case ,  hidden_size=37			)




				def        a				(   self			):
											self.config_tester.run_common_tests()




				@unittest.skip(reason='ViTMAE does not use inputs_embeds'			)
				def        a				(   self			):
											pass




				def        a				(   self			):
											snake_case_							,       snake_case_     							=       self.model_tester.prepare_config_and_inputs_for_common()

											for model_class in self.all_model_classes:
																		snake_case_     							=       model_class(snake_case			)
																		self.assertIsInstance(model.get_input_embeddings() ,  (nn.Module)			)
																		snake_case_     							=       model.get_output_embeddings()
																		self.assertTrue(x is None or isinstance(snake_case ,  nn.Linear			)			)




				def        a				(   self			):
											snake_case_							,       snake_case_     							=       self.model_tester.prepare_config_and_inputs_for_common()

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

																		snake_case_     							=       ['pixel_values']
																		self.assertListEqual(arg_names[:1] ,  snake_case			)




				def        a				(   self			):
											snake_case_     							=       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_model(*snake_case			)




				def        a				(   self			):
											snake_case_     							=       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_for_pretraining(*snake_case			)




				def        a				(   self ,  snake_case ,  snake_case ,  snake_case			):
											# make masks reproducible
											np.random.seed(2			)

											snake_case_     							=       int((pt_model.config.image_size // pt_model.config.patch_size) ** 2			)
											snake_case_     							=       np.random.uniform(size=(self.model_tester.batch_size, num_patches)			)
											snake_case_     							=       torch.from_numpy(snake_case			)

											# Add `noise` argument.
											# PT inputs will be prepared in `super().check_pt_tf_models()` with this added `noise` argument
											snake_case_     							=       pt_noise

											super().check_pt_tf_models(snake_case ,  snake_case ,  snake_case			)




				def        a				(   self			):
											snake_case_							,       snake_case_     							=       self.model_tester.prepare_config_and_inputs_for_common()

											for model_class in self.all_model_classes:
																		snake_case_     							=       model_class(snake_case			)
																		model.to(snake_case			)
																		model.eval()
																		# make random mask reproducible
																		torch.manual_seed(2			)
																		with torch.no_grad():
																									snake_case_     							=       model(**self._prepare_for_class(snake_case ,  snake_case			)			)

																		snake_case_     							=       outputs[0].cpu().numpy()
																		snake_case_     							=       0

																		with tempfile.TemporaryDirectory() as tmpdirname:
																									model.save_pretrained(snake_case			)
																									snake_case_     							=       model_class.from_pretrained(snake_case			)
																									model.to(snake_case			)
																									# make random mask reproducible
																									torch.manual_seed(2			)
																									with torch.no_grad():
																																snake_case_     							=       model(**self._prepare_for_class(snake_case ,  snake_case			)			)

																									# Make sure we don't have nans
																									snake_case_     							=       after_outputs[0].cpu().numpy()
																									snake_case_     							=       0
																									snake_case_     							=       np.amax(np.abs(out_a - out_a			)			)
																									self.assertLessEqual(snake_case ,  1e-5			)




				@unittest.skip(
				    reason='ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load\n    to get deterministic results.'			)
				def        a				(   self			):
											pass




				@unittest.skip(
				    reason='ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load\n    to get deterministic results.'			)
				def        a				(   self			):
											pass




				@unittest.skip(
				    reason='ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load\n    to get deterministic results.'			)
				def        a				(   self			):
											pass




				@unittest.skip(reason='ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load'			)
				def        a				(   self			):
											pass




				@unittest.skip('Will be fixed soon by reducing the size of the model used for common tests.'			)
				def        a				(   self			):
											pass




				@slow
				def        a				(   self			):
											for model_name in VIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																		snake_case_     							=       ViTMAEModel.from_pretrained(snake_case			)
																		self.assertIsNotNone(snake_case			)





def    __lowerCamelCase      (					):







							'''simple docstring'''






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







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




				@cached_property
				def        a				(   self			):
											return ViTImageProcessor.from_pretrained('facebook/vit-mae-base'			) if is_vision_available() else None




				@slow
				def        a				(   self			):
											# make random mask reproducible across the PT and TF model
											np.random.seed(2			)

											snake_case_     							=       ViTMAEForPreTraining.from_pretrained('facebook/vit-mae-base'			).to(snake_case			)

											snake_case_     							=       self.default_image_processor
											snake_case_     							=       prepare_img()
											snake_case_     							=       image_processor(images=snake_case ,  return_tensors='pt'			).to(snake_case			)

											# prepare a noise vector that will be also used for testing the TF model
											# (this way we can ensure that the PT and TF models operate on the same inputs)
											snake_case_     							=       ViTMAEConfig()
											snake_case_     							=       int((vit_mae_config.image_size // vit_mae_config.patch_size) ** 2			)
											snake_case_     							=       np.random.uniform(size=(1, num_patches)			)

											# forward pass
											with torch.no_grad():
																		snake_case_     							=       model(**snake_case ,  noise=torch.from_numpy(snake_case			).to(device=snake_case			)			)

											# verify the logits
											snake_case_     							=       torch.Size((1, 196, 768)			)
											self.assertEqual(outputs.logits.shape ,  snake_case			)

											snake_case_     							=       torch.tensor(
											    [[-0.05_48, -1.70_23, -0.93_25], [0.37_21, -0.56_70, -0.22_33], [0.82_35, -1.38_78, -0.35_24]]			)

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




