
_UpperCamelCase:					Union[str, Any]     ={
    '0': 1,
    '1': 1,
    '2': 2,
    '3': 6,
    '4': 24,
    '5': 120,
    '6': 720,
    '7': 5_040,
    '8': 40_320,
    '9': 362_880,
}

_UpperCamelCase:					Tuple     ={145: 145}

_UpperCamelCase:					Any     ={
    145: 0,
    169: 3,
    36_301: 3,
    1_454: 3,
    871: 2,
    45_361: 2,
    872: 2,
}



def 	_a  (					__SCREAMING_SNAKE_CASE					:  int    ):






  """simple docstring"""




  if n in CACHE_SUM_DIGIT_FACTORIALS:
    return CACHE_SUM_DIGIT_FACTORIALS[n]
  _lowerCAmelCase						=		sum(DIGIT_FACTORIALS[let] for let in str(__SCREAMING_SNAKE_CASE    )    )
  _lowerCAmelCase						=		ret
  return ret



def 	_a  (					__SCREAMING_SNAKE_CASE					:  int		,				__SCREAMING_SNAKE_CASE					:  set | None = None    ):






  """simple docstring"""




  _lowerCAmelCase						=		previous or set()
  if n in CHAIN_LENGTH_CACHE:
    return CHAIN_LENGTH_CACHE[n]
  _lowerCAmelCase						=		sum_digit_factorials(__SCREAMING_SNAKE_CASE    )
  if next_number in previous:
    _lowerCAmelCase						=		0
    return 0
  else:
    previous.add(__SCREAMING_SNAKE_CASE    )
    _lowerCAmelCase						=		1 + chain_length(__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE    )
    _lowerCAmelCase						=		ret
    return ret



def 	_a  (					__SCREAMING_SNAKE_CASE					:  int = 60		,				__SCREAMING_SNAKE_CASE					:  int = 1000000    ):






  """simple docstring"""




  return sum(1 for i in range(1		,				__SCREAMING_SNAKE_CASE    ) if chain_length(__SCREAMING_SNAKE_CASE    ) == num_terms    )


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


from __future__ import annotations



def 	_a  (					__SCREAMING_SNAKE_CASE					:  list		,				__SCREAMING_SNAKE_CASE					:  list    ):






  """simple docstring"""




  _lowerCAmelCase						=		[None] * (len(__SCREAMING_SNAKE_CASE    ) + len(__SCREAMING_SNAKE_CASE    ))

  _lowerCAmelCase						=		0  # pointer to current index for left Half
  _lowerCAmelCase						=		0  # pointer to current index for the right Half
  _lowerCAmelCase						=		0  # pointer to current index for the sorted array Half

  while pointera < len(__SCREAMING_SNAKE_CASE    ) and pointera < len(__SCREAMING_SNAKE_CASE    ):
    if left_half[pointera] < right_half[pointera]:
      _lowerCAmelCase						=		left_half[pointera]
      pointera += 1
      index += 1
    else:
      _lowerCAmelCase						=		right_half[pointera]
      pointera += 1
      index += 1
  while pointera < len(__SCREAMING_SNAKE_CASE    ):
    _lowerCAmelCase						=		left_half[pointera]
    pointera += 1
    index += 1

  while pointera < len(__SCREAMING_SNAKE_CASE    ):
    _lowerCAmelCase						=		right_half[pointera]
    pointera += 1
    index += 1

  return sorted_array



def 	_a  (					__SCREAMING_SNAKE_CASE					:  list    ):






  """simple docstring"""




  if len(__SCREAMING_SNAKE_CASE    ) <= 1:
    return array
  # the actual formula to calculate the middle element = left + (right - left) // 2
  # this avoids integer overflow in case of large N
  _lowerCAmelCase						=		0 + (len(__SCREAMING_SNAKE_CASE    ) - 0) // 2

  # Split the array into halves till the array length becomes equal to One
  # merge the arrays of single length returned by mergeSort function and
  # pass them into the merge arrays function which merges the array
  _lowerCAmelCase						=		array[:middle]
  _lowerCAmelCase						=		array[middle:]

  return merge(merge_sort(__SCREAMING_SNAKE_CASE    )		,				merge_sort(__SCREAMING_SNAKE_CASE    )    )


if __name__ == "__main__":
       import doctest

       doctest.testmod()
