





lowerCAmelCase_				= range(2, 2_0 + 1)
lowerCAmelCase_				= [1_0**k for k in range(ks[-1] + 1)]
lowerCAmelCase_				= {}




def     A_      (	lowercase_   ,		lowercase_   ,		lowercase_   ,		lowercase_	)      ->    Optional[int]:
       _snake_case   :				Dict  					=    sum(a_i[j] for j in range(__UpperCAmelCase   ,		len(__UpperCAmelCase	)	)	)
       _snake_case   :				List[Any]  					=    sum(a_i[j] * base[j] for j in range(min(len(__UpperCAmelCase	)   ,		__UpperCAmelCase	)	)	)

       _snake_case					,     _snake_case   :				str  					=    0, 0
       _snake_case   :				Optional[Any]  					=    n - i

       _snake_case   :				Any  					=    memo.get(__UpperCAmelCase	)

       if sub_memo is not None:
              _snake_case   :				Any  					=    sub_memo.get(__UpperCAmelCase	)

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

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

              else:
                     _snake_case   :				List[Any]  					=    []
       else:
              _snake_case   :				Any  					=    {c: []}
              _snake_case   :				Union[str, Any]  					=    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   :				str  					=    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   :				List[str]  					=    compute(__UpperCAmelCase   ,		__UpperCAmelCase   ,		i + dn   ,		__UpperCAmelCase	)
              diff += _diff
              dn += terms_jumped

       _snake_case   :				str  					=    sub_memo[c]

       # keep jumps sorted by # of terms skipped
       _snake_case   :				Optional[int]  					=    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     A_      (	lowercase_   ,		lowercase_   ,		lowercase_   ,		lowercase_	)      ->    str:







       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   :				List[str]  					=    i
       _snake_case					,     _snake_case					,     _snake_case   :				Optional[int]  					=    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   :				List[Any]  					=    ds_c + ds_b
              diff += addend
              _snake_case   :				Dict  					=    0
              for j in range(__UpperCAmelCase	):
                     _snake_case   :				List[str]  					=    a_i[j] + addend
                     _snake_case					,     _snake_case   :				str  					=    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     A_      (	lowercase_   ,		lowercase_   ,		lowercase_	)      ->    Union[str, Any]:







       for j in range(__UpperCAmelCase   ,		len(__UpperCAmelCase	)	):
              _snake_case   :				List[Any]  					=    digits[j] + addend
              if s >= 10:
                     _snake_case					,     _snake_case   :				Union[str, Any]  					=    divmod(__UpperCAmelCase   ,		10	)
                     _snake_case   :				Tuple  					=    addend // 10 + quotient
              else:
                     _snake_case   :				Optional[int]  					=    s
                     _snake_case   :				Union[str, Any]  					=    addend // 10

              if addend == 0:
                     break

       while addend > 0:
              _snake_case					,     _snake_case   :				Tuple  					=    divmod(__UpperCAmelCase   ,		10	)
              digits.append(__UpperCAmelCase	)




def     A_      (	lowercase_ = 10**15	)      ->    int:
       _snake_case   :				Optional[Any]  					=    [1]
       _snake_case   :				List[Any]  					=    1
       _snake_case   :				Optional[int]  					=    0
       while True:
              _snake_case					,     _snake_case   :				List[str]  					=    next_term(__UpperCAmelCase   ,		20   ,		i + dn   ,		__UpperCAmelCase	)
              dn += terms_jumped
              if dn == n - i:
                     break

       _snake_case   :				Dict  					=    0
       for j in range(len(__UpperCAmelCase	)	):
              a_n += digits[j] * 10**j
       return a_n


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













'''simple docstring'''

import gc
import unittest

from transformers import CTRLConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
    import torch

    from transformers import (
        CTRL_PRETRAINED_MODEL_ARCHIVE_LIST,
        CTRLForSequenceClassification,
        CTRLLMHeadModel,
        CTRLModel,
    )







class __a			:





   def __init__(       self					:      Union[str, Any]					,lowerCamelCase					:      Optional[int]					,lowerCamelCase					:      Tuple=14					,lowerCamelCase					:      Optional[Any]=7					,lowerCamelCase					:      str=True					,lowerCamelCase					:      List[str]=True					,lowerCamelCase					:      Dict=True					,lowerCamelCase					:      Any=True					,lowerCamelCase					:      int=True					,lowerCamelCase					:      Dict=99					,lowerCamelCase					:      Dict=32					,lowerCamelCase					:      Optional[Any]=5					,lowerCamelCase					:      Tuple=4					,lowerCamelCase					:      Optional[int]=37					,lowerCamelCase					:      Optional[int]="gelu"					,lowerCamelCase					:      Optional[Any]=0.1					,lowerCamelCase					:      Tuple=0.1					,lowerCamelCase					:      Dict=512					,lowerCamelCase					:      int=16					,lowerCamelCase					:      Union[str, Any]=2					,lowerCamelCase					:      Tuple=0.02					,lowerCamelCase					:      str=3					,lowerCamelCase					:      Union[str, Any]=4					,lowerCamelCase					:      Any=None					,):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							parent
      __SCREAMING_SNAKE_CASE   				=							batch_size
      __SCREAMING_SNAKE_CASE   				=							seq_length
      __SCREAMING_SNAKE_CASE   				=							is_training
      __SCREAMING_SNAKE_CASE   				=							use_token_type_ids
      __SCREAMING_SNAKE_CASE   				=							use_input_mask
      __SCREAMING_SNAKE_CASE   				=							use_labels
      __SCREAMING_SNAKE_CASE   				=							use_mc_token_ids
      __SCREAMING_SNAKE_CASE   				=							vocab_size
      __SCREAMING_SNAKE_CASE   				=							hidden_size
      __SCREAMING_SNAKE_CASE   				=							num_hidden_layers
      __SCREAMING_SNAKE_CASE   				=							num_attention_heads
      __SCREAMING_SNAKE_CASE   				=							intermediate_size
      __SCREAMING_SNAKE_CASE   				=							hidden_act
      __SCREAMING_SNAKE_CASE   				=							hidden_dropout_prob
      __SCREAMING_SNAKE_CASE   				=							attention_probs_dropout_prob
      __SCREAMING_SNAKE_CASE   				=							max_position_embeddings
      __SCREAMING_SNAKE_CASE   				=							type_vocab_size
      __SCREAMING_SNAKE_CASE   				=							type_sequence_label_size
      __SCREAMING_SNAKE_CASE   				=							initializer_range
      __SCREAMING_SNAKE_CASE   				=							num_labels
      __SCREAMING_SNAKE_CASE   				=							num_choices
      __SCREAMING_SNAKE_CASE   				=							scope
      __SCREAMING_SNAKE_CASE   				=							self.vocab_size - 1





   def   UpperCAmelCase__  (       self					:      Dict     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.batch_size, self.seq_length]					,self.vocab_size     )

      __SCREAMING_SNAKE_CASE   				=							None
      if self.use_input_mask:
         __SCREAMING_SNAKE_CASE   				=							random_attention_mask([self.batch_size, self.seq_length]     )

      __SCREAMING_SNAKE_CASE   				=							None
      if self.use_token_type_ids:
         __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.batch_size, self.seq_length]					,self.type_vocab_size     )

      __SCREAMING_SNAKE_CASE   				=							None
      if self.use_mc_token_ids:
         __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.batch_size, self.num_choices]					,self.seq_length     )

      __SCREAMING_SNAKE_CASE   				=							None
      __SCREAMING_SNAKE_CASE   				=							None
      __SCREAMING_SNAKE_CASE   				=							None
      if self.use_labels:
         __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.batch_size]					,self.type_sequence_label_size     )
         __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.batch_size, self.seq_length]					,self.num_labels     )
         __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.batch_size]					,self.num_choices     )

      __SCREAMING_SNAKE_CASE   				=							self.get_config()

      __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.num_hidden_layers, self.num_attention_heads]					,2     )

      return (
          config,
          input_ids,
          input_mask,
          head_mask,
          token_type_ids,
          mc_token_ids,
          sequence_labels,
          token_labels,
          choice_labels,
      )





   def   UpperCAmelCase__  (       self					:      int     ):

      '''simple docstring'''

      return CTRLConfig(
          vocab_size=self.vocab_size					,n_embd=self.hidden_size					,n_layer=self.num_hidden_layers					,n_head=self.num_attention_heads					,n_positions=self.max_position_embeddings					,pad_token_id=self.pad_token_id					,)





   def   UpperCAmelCase__  (       self					:      Tuple					,lowerCamelCase					:      Optional[Any]					,lowerCamelCase					:      Tuple					,lowerCamelCase					:      Any					,lowerCamelCase					:      List[str]					,lowerCamelCase					:      str					,*lowerCamelCase					:      Tuple     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							CTRLModel(config=lowerCamelCase     )
      model.to(lowerCamelCase     )
      model.eval()

      model(lowerCamelCase					,token_type_ids=lowerCamelCase					,head_mask=lowerCamelCase     )
      model(lowerCamelCase					,token_type_ids=lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							model(lowerCamelCase     )
      self.parent.assertEqual(result.last_hidden_state.shape					,(self.batch_size, self.seq_length, self.hidden_size)     )
      self.parent.assertEqual(len(result.past_key_values     )					,config.n_layer     )





   def   UpperCAmelCase__  (       self					:      Optional[int]					,lowerCamelCase					:      int					,lowerCamelCase					:      Optional[Any]					,lowerCamelCase					:      Optional[Any]					,lowerCamelCase					:      int					,lowerCamelCase					:      Dict					,*lowerCamelCase					:      int     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							CTRLLMHeadModel(lowerCamelCase     )
      model.to(lowerCamelCase     )
      model.eval()

      __SCREAMING_SNAKE_CASE   				=							model(lowerCamelCase					,token_type_ids=lowerCamelCase					,labels=lowerCamelCase     )
      self.parent.assertEqual(result.loss.shape					,()     )
      self.parent.assertEqual(result.logits.shape					,(self.batch_size, self.seq_length, self.vocab_size)     )





   def   UpperCAmelCase__  (       self					:      List[Any]     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							self.prepare_config_and_inputs()

      (
          (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  (
          __SCREAMING_SNAKE_CASE
      )				,  
      )   				=							config_and_inputs

      __SCREAMING_SNAKE_CASE   				=							{"""input_ids""": input_ids, """token_type_ids""": token_type_ids, """head_mask""": head_mask}

      return config, inputs_dict





   def   UpperCAmelCase__  (       self					:      Dict					,lowerCamelCase					:      int					,lowerCamelCase					:      str					,lowerCamelCase					:      Optional[Any]					,lowerCamelCase					:      Optional[Any]					,*lowerCamelCase					:      Optional[Any]     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							self.num_labels
      __SCREAMING_SNAKE_CASE   				=							CTRLForSequenceClassification(lowerCamelCase     )
      model.to(lowerCamelCase     )
      model.eval()
      __SCREAMING_SNAKE_CASE   				=							ids_tensor([self.batch_size]					,self.type_sequence_label_size     )
      __SCREAMING_SNAKE_CASE   				=							model(lowerCamelCase					,token_type_ids=lowerCamelCase					,labels=lowerCamelCase     )
      self.parent.assertEqual(result.logits.shape					,(self.batch_size, self.num_labels)     )







@require_torch
class __a			( _snake_case, _snake_case, _snake_case, unittest.TestCase      ):
   __UpperCamelCase :			str						   =						(CTRLModel, CTRLLMHeadModel, CTRLForSequenceClassification) if is_torch_available() else ()
   __UpperCamelCase :			Dict						   =						(CTRLLMHeadModel,) if is_torch_available() else ()
   __UpperCamelCase :			int						   =						(
       {
           'feature-extraction': CTRLModel,
           'text-classification': CTRLForSequenceClassification,
           'text-generation': CTRLLMHeadModel,
           'zero-shot': CTRLForSequenceClassification,
       }
       if is_torch_available()
       else {}
   )
   __UpperCamelCase :			List[str]						   =						True
   __UpperCamelCase :			Dict						   =						False
   __UpperCamelCase :			Tuple						   =						False





   def   UpperCAmelCase__  (       self					:      Dict					,lowerCamelCase					:      Any					,lowerCamelCase					:      str					,lowerCamelCase					:      List[str]					,lowerCamelCase					:      int					,lowerCamelCase					:      Dict     ):

      '''simple docstring'''

      if pipeline_test_casse_name == "ZeroShotClassificationPipelineTests":
         # Get `tokenizer does not have a padding token` error for both fast/slow tokenizers.
         # `CTRLConfig` was never used in pipeline tests, either because of a missing checkpoint or because a tiny
         # config could not be created.
         return True

      return False





   def   UpperCAmelCase__  (       self					:      int     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							CTRLModelTester(self     )
      __SCREAMING_SNAKE_CASE   				=							ConfigTester(self					,config_class=lowerCamelCase					,n_embd=37     )





   def   UpperCAmelCase__  (       self					:      List[str]     ):

      '''simple docstring'''

      super().tearDown()
      # clean-up as much as possible GPU memory occupied by PyTorch
      gc.collect()
      torch.cuda.empty_cache()





   def   UpperCAmelCase__  (       self					:      Optional[int]     ):

      '''simple docstring'''

      self.config_tester.run_common_tests()





   def   UpperCAmelCase__  (       self					:      Dict     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_ctrl_model(*lowerCamelCase     )





   def   UpperCAmelCase__  (       self					:      int     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_lm_head_model(*lowerCamelCase     )





   @unittest.skip("""Will be fixed soon by reducing the size of the model used for common tests."""     )
   def   UpperCAmelCase__  (       self					:      int     ):

      '''simple docstring'''

      pass





   @slow
   def   UpperCAmelCase__  (       self					:      List[str]     ):

      '''simple docstring'''

      for model_name in CTRL_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
         __SCREAMING_SNAKE_CASE   				=							CTRLModel.from_pretrained(lowerCamelCase     )
         self.assertIsNotNone(lowerCamelCase     )





   @unittest.skip("""The model doesn't support left padding"""     )  # and it's not used enough to be worth fixing :)
   def   UpperCAmelCase__  (       self					:      Tuple     ):

      '''simple docstring'''

      pass







@require_torch
class __a			( unittest.TestCase      ):





   def   UpperCAmelCase__  (       self					:      int     ):

      '''simple docstring'''

      super().tearDown()
      # clean-up as much as possible GPU memory occupied by PyTorch
      gc.collect()
      torch.cuda.empty_cache()





   @slow
   def   UpperCAmelCase__  (       self					:      Union[str, Any]     ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE   				=							CTRLLMHeadModel.from_pretrained("""ctrl"""     )
      model.to(lowerCamelCase     )
      __SCREAMING_SNAKE_CASE   				=							torch.tensor(
          [[1_1859, 0, 1611, 8]]					,dtype=torch.long					,device=lowerCamelCase     )  # Legal the president is
      __SCREAMING_SNAKE_CASE   				=							[
          1_1859,
          0,
          1611,
          8,
          5,
          150,
          2_6449,
          2,
          19,
          348,
          469,
          3,
          2595,
          48,
          2_0740,
          24_6533,
          24_6533,
          19,
          30,
          5,
      ]  # Legal the president is a good guy and I don't want to lose my job. \n \n I have a

      __SCREAMING_SNAKE_CASE   				=							model.generate(lowerCamelCase					,do_sample=lowerCamelCase     )
      self.assertListEqual(output_ids[0].tolist()					,lowerCamelCase     )





