


'''simple docstring'''


lowerCamelCase__    	=     range(2, 20 + 1)
lowerCamelCase__    	=     [10**k for k in range(ks[-1] + 1)]
lowerCamelCase__    	=     {}






def  __lowerCAmelCase (__lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase   ):
		_UpperCAmelCase		:       List[str]								=      sum(a_i[j] for j in range(_UpperCAmelCase      , len(_UpperCAmelCase   )   )   )
		_UpperCAmelCase		:       Any								=      sum(a_i[j] * base[j] for j in range(min(len(_UpperCAmelCase   )      , _UpperCAmelCase   )   )   )

		_UpperCAmelCase					,    _UpperCAmelCase		:       Tuple								=      0, 0
		_UpperCAmelCase		:       Any								=      n - i

		_UpperCAmelCase		:       List[Any]								=      memo.get(_UpperCAmelCase   )

		if sub_memo is not None:
				_UpperCAmelCase		:       Optional[Any]								=      sub_memo.get(_UpperCAmelCase   )

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

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

				else:
						_UpperCAmelCase		:       int								=      []
		else:
				_UpperCAmelCase		:       List[Any]								=      {c: []}
				_UpperCAmelCase		:       Tuple								=      sub_memo

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

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

		_UpperCAmelCase		:       Tuple								=      sub_memo[c]

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

				if addend == 0:
						break

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






def  __lowerCAmelCase (__lowerCAmelCase = 10**15   ):
		_UpperCAmelCase		:       Tuple								=      [1]
		_UpperCAmelCase		:       Optional[Any]								=      1
		_UpperCAmelCase		:       Union[str, Any]								=      0
		while True:
				_UpperCAmelCase					,    _UpperCAmelCase		:       Tuple								=      next_term(_UpperCAmelCase      , 20      , i + dn      , _UpperCAmelCase   )
				dn += terms_jumped
				if dn == n - i:
						break

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


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







'''simple docstring'''


from math import factorial






class 	lowerCAmelCase__			:




			def __init__(		self  :     int	,  lowerCamelCase__  :     Union[str, Any]	,  lowerCamelCase__  :     str )   ->Dict:



					'''simple docstring'''







					_UpperCAmelCase		:       Optional[Any]								=      real
					if isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Any								=      [1] * rank
					else:
							_UpperCAmelCase		:       Dict								=      rank




			def __repr__(		self  :     str )   ->List[str]:



					'''simple docstring'''







					return (
					    F"""{self.real}+"""
					    F"""{'+'.join(str(lowerCamelCase__ )+'E'+str(n+1 )for n,dual in enumerate(self.duals ) )}"""
					)




			def 							lowerCAmelCase__    (		self  :     Dict )   ->Tuple:



					'''simple docstring'''







					_UpperCAmelCase		:       Union[str, Any]								=      self.duals.copy()
					while cur[-1] == 0:
							cur.pop(-1 )
					return Dual(self.real	,  lowerCamelCase__ )




			def __add__(		self  :     Dict	,  lowerCamelCase__  :     List[Any] )   ->Any:



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							return Dual(self.real + other	,  self.duals )
					_UpperCAmelCase		:       Optional[int]								=      self.duals.copy()
					_UpperCAmelCase		:       Optional[int]								=      other.duals.copy()
					if len(lowerCamelCase__ ) > len(lowerCamelCase__ ):
							o_dual.extend([1] * (len(lowerCamelCase__ ) - len(lowerCamelCase__ )) )
					elif len(lowerCamelCase__ ) < len(lowerCamelCase__ ):
							s_dual.extend([1] * (len(lowerCamelCase__ ) - len(lowerCamelCase__ )) )
					_UpperCAmelCase		:       Union[str, Any]								=      []
					for i in range(len(lowerCamelCase__ ) ):
							new_duals.append(s_dual[i] + o_dual[i] )
					return Dual(self.real + other.real	,  lowerCamelCase__ )

			lowerCAmelCase :	Tuple          =     __add__




			def __sub__(		self  :     List[Any]	,  lowerCamelCase__  :     Union[str, Any] )   ->Dict:



					'''simple docstring'''







					return self + other * -1




			def __mul__(		self  :     List[str]	,  lowerCamelCase__  :     Optional[Any] )   ->Union[str, Any]:



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Optional[int]								=      []
							for i in self.duals:
									new_duals.append(i * other )
							return Dual(self.real * other	,  lowerCamelCase__ )
					_UpperCAmelCase		:       Union[str, Any]								=      [0] * (len(self.duals ) + len(other.duals ) + 1)
					for i, item in enumerate(self.duals ):
							for j, jtem in enumerate(other.duals ):
									new_duals[i + j + 1] += item * jtem
					for k in range(len(self.duals ) ):
							new_duals[k] += self.duals[k] * other.real
					for index in range(len(other.duals ) ):
							new_duals[index] += other.duals[index] * self.real
					return Dual(self.real * other.real	,  lowerCamelCase__ )

			lowerCAmelCase :	Union[str, Any]          =     __mul__




			def __truediv__(		self  :     Optional[Any]	,  lowerCamelCase__  :     List[Any] )   ->Union[str, Any]:



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Union[str, Any]								=      []
							for i in self.duals:
									new_duals.append(i / other )
							return Dual(self.real / other	,  lowerCamelCase__ )
					raise ValueError




			def __floordiv__(		self  :     str	,  lowerCamelCase__  :     str )   ->List[str]:



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Tuple								=      []
							for i in self.duals:
									new_duals.append(i // other )
							return Dual(self.real // other	,  lowerCamelCase__ )
					raise ValueError






			def __pow__(		self  :     Tuple	,  lowerCamelCase__  :     Optional[Any] )   ->Optional[int]:



					'''simple docstring'''







					if n < 0 or isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							raise ValueError("power must be a positive integer" )
					if n == 0:
							return 1
					if n == 1:
							return self
					_UpperCAmelCase		:       str								=      self
					for _ in range(n - 1 ):
							x *= self
					return x






def  __lowerCAmelCase (__lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase   ):
		if not callable(__lowerCAmelCase   ):
				raise ValueError("differentiate() requires a function as input for func"   )
		if not isinstance(__lowerCAmelCase      , (float, int)   ):
				raise ValueError("differentiate() requires a float as input for position"   )
		if not isinstance(__lowerCAmelCase      , __lowerCAmelCase   ):
				raise ValueError("differentiate() requires an int as input for order"   )
		_UpperCAmelCase		:       int								=      Dual(__lowerCAmelCase      , 1   )
		_UpperCAmelCase		:       Optional[int]								=      func(__lowerCAmelCase   )
		if order == 0:
				return result.real
		return result.duals[order - 1] * factorial(__lowerCAmelCase   )


if __name__ == "__main__":
						import doctest

						doctest.testmod()






						def  __lowerCAmelCase (__lowerCAmelCase   ):
								return y**2 * y**4





						print(differentiate(f, 9, 2))



