



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





def   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase       ):
    __a		 =       sum(a_i[j] for j in range(_UpperCAmelCase     ,				len(_UpperCAmelCase       )       )       )
    __a		 =       sum(a_i[j] * base[j] for j in range(min(len(_UpperCAmelCase       )     ,				_UpperCAmelCase       )       )       )

    __a ,     __a		 =       0, 0
    __a		 =       n - i

    __a		 =       memo.get(_UpperCAmelCase       )

    if sub_memo is not None:
        __a		 =       sub_memo.get(_UpperCAmelCase       )

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

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

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

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

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

    __a		 =       sub_memo[c]

    # keep jumps sorted by # of terms skipped
    __a		 =       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   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase       ):
    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)
    __a		 =       i
    __a ,     __a ,     __a		 =       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
        __a		 =       ds_c + ds_b
        diff += addend
        __a		 =       0
        for j in range(_UpperCAmelCase       ):
            __a		 =       a_i[j] + addend
            __a ,     __a		 =       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   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase       ):
    for j in range(_UpperCAmelCase     ,				len(_UpperCAmelCase       )       ):
        __a		 =       digits[j] + addend
        if s >= 10:
            __a ,     __a		 =       divmod(_UpperCAmelCase     ,				10       )
            __a		 =       addend // 10 + quotient
        else:
            __a		 =       s
            __a		 =       addend // 10

        if addend == 0:
            break

    while addend > 0:
        __a ,     __a		 =       divmod(_UpperCAmelCase     ,				10       )
        digits.append(_UpperCAmelCase       )





def   __snake_case			(    _UpperCAmelCase = 10**15       ):
    __a		 =       [1]
    __a		 =       1
    __a		 =       0
    while True:
        __a ,     __a		 =       next_term(_UpperCAmelCase     ,				20     ,				i + dn     ,				_UpperCAmelCase       )
        dn += terms_jumped
        if dn == n - i:
            break

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


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










import os
import sys
import unittest


__snake_case		:Union[str, Any]   	=  os.path.abspath(os.path.dirname(os.path.dirname(os.path.dirname(__file__))))
sys.path.append(os.path.join(git_repo_path, '''utils'''))

import check_dummies  # noqa: E402
from check_dummies import create_dummy_files, create_dummy_object, find_backend, read_init  # noqa: E402


# Align TRANSFORMERS_PATH in check_dummies with the current path
__snake_case		:List[str]   	=  os.path.join(git_repo_path, '''src''', '''transformers''')

__snake_case		:Any   	=  '''
{0} = None
'''

__snake_case		:Dict   	=  '''
class {0}(metaclass=DummyObject):
    _backends = {1}

    def __init__(self, *args, **kwargs):
        requires_backends(self, {1})
'''


__snake_case		:str   	=  '''
def {0}(*args, **kwargs):
    requires_backends({0}, {1})
'''

class 					_A (			unittest.TestCase					):



       def 	_lowerCamelCase    (	self							:  List[Any]):


           '''simple docstring'''

           __a		 =       find_backend('''    _import_structure["models.albert"].append("AlbertTokenizerFast")''')
           self.assertIsNone(__SCREAMING_SNAKE_CASE)

           __a		 =       find_backend('''    if not is_tokenizers_available():''')
           self.assertEqual(__SCREAMING_SNAKE_CASE  ,	'''tokenizers''')

           __a		 =       find_backend('''    if not is_tensorflow_text_available():''')
           self.assertEqual(__SCREAMING_SNAKE_CASE  ,	'''tensorflow_text''')

           __a		 =       find_backend('''    if not (is_sentencepiece_available() and is_tokenizers_available()):''')
           self.assertEqual(__SCREAMING_SNAKE_CASE  ,	'''sentencepiece_and_tokenizers''')

           __a		 =       find_backend(
               '''    if not (is_sentencepiece_available() and is_tensorflow_text_available()):''')
           self.assertEqual(__SCREAMING_SNAKE_CASE  ,	'''sentencepiece_and_tensorflow_text''')

           __a		 =       find_backend(
               '''    if not (is_sentencepiece_available() and is_tokenizers_available() and is_vision_available()):''')
           self.assertEqual(__SCREAMING_SNAKE_CASE  ,	'''sentencepiece_and_tokenizers_and_vision''')



       def 	_lowerCamelCase    (	self							:  Optional[Any]):


           '''simple docstring'''

           __a		 =       read_init()
           # We don't assert on the exact list of keys to allow for smooth grow of backend-specific objects
           self.assertIn('''torch'''  ,	__SCREAMING_SNAKE_CASE)
           self.assertIn('''tensorflow_text'''  ,	__SCREAMING_SNAKE_CASE)
           self.assertIn('''sentencepiece_and_tokenizers'''  ,	__SCREAMING_SNAKE_CASE)

           # Likewise, we can't assert on the exact content of a key
           self.assertIn('''BertModel'''  ,	objects['''torch'''])
           self.assertIn('''TFBertModel'''  ,	objects['''tf'''])
           self.assertIn('''FlaxBertModel'''  ,	objects['''flax'''])
           self.assertIn('''BertModel'''  ,	objects['''torch'''])
           self.assertIn('''TFBertTokenizer'''  ,	objects['''tensorflow_text'''])
           self.assertIn('''convert_slow_tokenizer'''  ,	objects['''sentencepiece_and_tokenizers'''])



       def 	_lowerCamelCase    (	self							:  Any):


           '''simple docstring'''

           __a		 =       create_dummy_object('''CONSTANT'''  ,	'''\'torch\'''')
           self.assertEqual(__SCREAMING_SNAKE_CASE  ,	'''\nCONSTANT = None\n''')

           __a		 =       create_dummy_object('''function'''  ,	'''\'torch\'''')
           self.assertEqual(
               __SCREAMING_SNAKE_CASE  ,	'''\ndef function(*args, **kwargs):\n    requires_backends(function, \'torch\')\n''')

           __a		 =       '''
class FakeClass(metaclass=DummyObject):
    _backends = \'torch\'

    def __init__(self, *args, **kwargs):
        requires_backends(self, \'torch\')
'''
           __a		 =       create_dummy_object('''FakeClass'''  ,	'''\'torch\'''')
           self.assertEqual(__SCREAMING_SNAKE_CASE  ,	__SCREAMING_SNAKE_CASE)





       def 	_lowerCamelCase    (	self							:  Optional[Any]):


           '''simple docstring'''

           __a		 =       '''# This file is autogenerated by the command `make fix-copies`, do not edit.
from ..utils import DummyObject, requires_backends


CONSTANT = None


def function(*args, **kwargs):
    requires_backends(function, ["torch"])


class FakeClass(metaclass=DummyObject):
    _backends = ["torch"]

    def __init__(self, *args, **kwargs):
        requires_backends(self, ["torch"])
'''
           __a		 =       create_dummy_files({'''torch''': ['''CONSTANT''', '''function''', '''FakeClass''']})
           self.assertEqual(dummy_files['''torch''']  ,	__SCREAMING_SNAKE_CASE)





