




'''simple docstring'''



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




def   lowercase__(			__UpperCamelCase:					Optional[Any]      ,__UpperCamelCase:					List[Any]      ,__UpperCamelCase:					Optional[Any]      ,__UpperCamelCase:					Optional[int]    ):

      """simple docstring"""






      SCREAMING_SNAKE_CASE   :      Any    					=						sum(a_i[j] for j in range(__UpperCamelCase      ,len(__UpperCamelCase    )    )    )
      SCREAMING_SNAKE_CASE   :      Any    					=						sum(a_i[j] * base[j] for j in range(min(len(__UpperCamelCase    )      ,__UpperCamelCase    )    )    )

      SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      int    					=						0, 0
      SCREAMING_SNAKE_CASE   :      List[Any]    					=						n - i

      SCREAMING_SNAKE_CASE   :      Optional[int]    					=						memo.get(__UpperCamelCase    )

      if sub_memo is not None:
            SCREAMING_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
                  SCREAMING_SNAKE_CASE   :      Any    					=						-1
                  for _k in range(len(__UpperCamelCase    ) - 1      ,-1      ,-1    ):
                        if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
                              SCREAMING_SNAKE_CASE   :      str    					=						_k
                              break

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

            else:
                  SCREAMING_SNAKE_CASE   :      Any    					=						[]
      else:
            SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						{c: []}
            SCREAMING_SNAKE_CASE   :      Optional[int]    					=						sub_memo

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

      if k > ks[0]:
            while True:
                  # keep doing smaller jumps
                  SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      Any    					=						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
            SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      List[str]    					=						compute(__UpperCamelCase      ,__UpperCamelCase      ,i + dn      ,__UpperCamelCase    )
            diff += _diff
            dn += terms_jumped

      SCREAMING_SNAKE_CASE   :      Optional[int]    					=						sub_memo[c]

      # keep jumps sorted by # of terms skipped
      SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						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   lowercase__(			__UpperCamelCase:					Dict      ,__UpperCamelCase:					Optional[int]      ,__UpperCamelCase:					List[str]      ,__UpperCamelCase:					Union[str, Any]    ):

      """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)
      SCREAMING_SNAKE_CASE   :      Optional[int]    					=						i
      SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      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
            SCREAMING_SNAKE_CASE   :      List[Any]    					=						ds_c + ds_b
            diff += addend
            SCREAMING_SNAKE_CASE   :      Optional[int]    					=						0
            for j in range(__UpperCamelCase    ):
                  SCREAMING_SNAKE_CASE   :      Optional[int]    					=						a_i[j] + addend
                  SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						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   lowercase__(			__UpperCamelCase:					Tuple      ,__UpperCamelCase:					Union[str, Any]      ,__UpperCamelCase:					Union[str, Any]    ):

      """simple docstring"""






      for j in range(__UpperCamelCase      ,len(__UpperCamelCase    )    ):
            SCREAMING_SNAKE_CASE   :      List[str]    					=						digits[j] + addend
            if s >= 10:
                  SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      Any    					=						divmod(__UpperCamelCase      ,10    )
                  SCREAMING_SNAKE_CASE   :      List[str]    					=						addend // 10 + quotient
            else:
                  SCREAMING_SNAKE_CASE   :      str    					=						s
                  SCREAMING_SNAKE_CASE   :      Dict    					=						addend // 10

            if addend == 0:
                  break

      while addend > 0:
            SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						divmod(__UpperCamelCase      ,10    )
            digits.append(__UpperCamelCase    )




def   lowercase__(			__UpperCamelCase:					int = 10**15    ):

      """simple docstring"""






      SCREAMING_SNAKE_CASE   :      int    					=						[1]
      SCREAMING_SNAKE_CASE   :      Any    					=						1
      SCREAMING_SNAKE_CASE   :      List[str]    					=						0
      while True:
            SCREAMING_SNAKE_CASE					,    SCREAMING_SNAKE_CASE   :      Tuple    					=						next_term(__UpperCamelCase      ,20      ,i + dn      ,__UpperCamelCase    )
            dn += terms_jumped
            if dn == n - i:
                  break

      SCREAMING_SNAKE_CASE   :      int    					=						0
      for j in range(len(__UpperCamelCase    )    ):
            a_n += digits[j] * 10**j
      return a_n


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









from typing import Mapping

from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxSeqaSeqConfigWithPast
from ...utils import logging


_lowerCAmelCase				:   Optional[int]						       =						logging.get_logger(__name__)

_lowerCAmelCase				:   List[str]						       =						{
    '''google/umt5-small''': '''https://huggingface.co/google/umt5-small/resolve/main/config.json''',
    # See all umt5 models at https://huggingface.co/models?filter=umt5
}


class        __magic_name__	(				lowerCamelCase__				):





     """simple docstring"""



     __UpperCamelCase            =  '''umt5'''
     __UpperCamelCase            =  ['''past_key_values''']



     def __init__(				self							:int      ,   snake_case							:Optional[Any]=250_112      ,   snake_case							:Optional[int]=512      ,   snake_case							:Any=64      ,   snake_case							:Union[str, Any]=1_024      ,   snake_case							:Tuple=8      ,   snake_case							:Optional[int]=None      ,   snake_case							:Union[str, Any]=6      ,   snake_case							:List[Any]=32      ,   snake_case							:Dict=128      ,   snake_case							:List[str]=0.1      ,   snake_case							:List[Any]=1e-6      ,   snake_case							:Dict=1.0      ,   snake_case							:Union[str, Any]="gated-gelu"      ,   snake_case							:Union[str, Any]=True      ,   snake_case							:Any=True      ,   snake_case							:List[str]="T5Tokenizer"      ,   snake_case							:Union[str, Any]=True      ,   snake_case							:Union[str, Any]=0      ,   snake_case							:List[Any]=1      ,   snake_case							:List[Any]=0      ,   **snake_case							:Any      ,   ):





        '''simple docstring'''




        super().__init__(
            is_encoder_decoder=snake_case      ,   tokenizer_class=snake_case      ,   tie_word_embeddings=snake_case      ,   pad_token_id=snake_case      ,   eos_token_id=snake_case      ,   decoder_start_token_id=snake_case      ,   **snake_case      ,   )
        A_       :					Union[str, Any]        =      vocab_size
        A_       :					Tuple        =      d_model
        A_       :					List[str]        =      d_kv
        A_       :					Union[str, Any]        =      d_ff
        A_       :					Any        =      num_layers
        A_       :					Optional[Any]        =      (
            num_decoder_layers if num_decoder_layers is not None else self.num_layers
        )  # default = symmetry
        A_       :					List[Any]        =      num_heads
        A_       :					List[str]        =      relative_attention_num_buckets
        A_       :					Dict        =      relative_attention_max_distance
        A_       :					Optional[Any]        =      dropout_rate
        A_       :					Any        =      layer_norm_epsilon
        A_       :					List[Any]        =      initializer_factor
        A_       :					Any        =      feed_forward_proj
        A_       :					Optional[Any]        =      use_cache

        A_       :					int        =      self.feed_forward_proj.split("-"	)
        A_       :					Any        =      act_info[-1]
        A_       :					Tuple        =      act_info[0] == "gated"

        if len(snake_case	) > 1 and act_info[0] != "gated" or len(snake_case	) > 2:
           raise ValueError(
               f"`feed_forward_proj`: {feed_forward_proj} is not a valid activation function of the dense layer."
               "Please make sure `feed_forward_proj` is of the format `gated-{ACT_FN}` or `{ACT_FN}`, e.g. "
               "'gated-gelu' or 'relu'"	)

        if feed_forward_proj == "gated-gelu":
           A_       :					Optional[Any]        =      "gelu_new"



     @property
     def     SCREAMING_SNAKE_CASE		(				self							:str	):





        '''simple docstring'''




        return self.d_model



     @property
     def     SCREAMING_SNAKE_CASE		(				self							:str	):





        '''simple docstring'''




        return self.num_heads





     @property
     def     SCREAMING_SNAKE_CASE		(				self							:Tuple	):





        '''simple docstring'''




        return self.num_layers




class        __magic_name__	(				lowerCamelCase__				):





     """simple docstring"""



     @property
     # Copied from transformers.models.t5.configuration_t5.T5OnnxConfig.inputs
     def     SCREAMING_SNAKE_CASE		(				self							:Union[str, Any]	):





        '''simple docstring'''




        A_       :					List[Any]        =      {
            "input_ids": {0: "batch", 1: "encoder_sequence"},
            "attention_mask": {0: "batch", 1: "encoder_sequence"},
        }
        if self.use_past:
           A_       :					Any        =      "past_encoder_sequence + sequence"
           A_       :					Union[str, Any]        =      {0: "batch"}
           A_       :					Optional[int]        =      {0: "batch", 1: "past_decoder_sequence + sequence"}
        else:
           A_       :					Dict        =      {0: "batch", 1: "decoder_sequence"}
           A_       :					str        =      {0: "batch", 1: "decoder_sequence"}

        if self.use_past:
           self.fill_with_past_key_values_(snake_case      ,   direction="inputs"	)

        return common_inputs



     @property
     # Copied from transformers.models.t5.configuration_t5.T5OnnxConfig.default_onnx_opset
     def     SCREAMING_SNAKE_CASE		(				self							:Optional[int]	):





        '''simple docstring'''




        return 13





     @property
     def     SCREAMING_SNAKE_CASE		(				self							:List[str]	):





        '''simple docstring'''




        return 5e-4
