




from __future__ import annotations



def     lowerCAmelCase		(		_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int						):




 """simple docstring"""







 assert n > 1 and a > 0 and greatest_common_divisor(lowerCAmelCase__    ,				lowerCAmelCase__						) == 1
 (UpperCAmelCase__)							=    extended_gcd(lowerCAmelCase__    ,				lowerCAmelCase__						)  # Implemented below
 UpperCAmelCase__							=    (b * s) % n
 return x



def     lowerCAmelCase		(		_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int						):




 """simple docstring"""







 (UpperCAmelCase__)							=    extended_euclid(lowerCAmelCase__    ,				lowerCAmelCase__						)  # Implemented below
 if b < 0:
  UpperCAmelCase__							=    (b % n + n) % n
 return b



def     lowerCAmelCase		(		_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int						):




 """simple docstring"""







 UpperCAmelCase__							=    invert_modulo(lowerCAmelCase__    ,				lowerCAmelCase__						)
 UpperCAmelCase__							=    (b * s) % n
 return x



def     lowerCAmelCase		(		_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int						):




 """simple docstring"""







 assert a >= 0 and b >= 0

 if b == 0:
  UpperCAmelCase__							=    a, 1, 0
 else:
  (UpperCAmelCase__)							=    extended_gcd(lowerCAmelCase__    ,				a % b						)
  UpperCAmelCase__							=    q
  UpperCAmelCase__							=    p - q * (a // b)

 assert a % d == 0 and b % d == 0
 assert d == a * x + b * y

 return (d, x, y)



def     lowerCAmelCase		(		_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int						):




 """simple docstring"""







 if b == 0:
  return (1, 0)
 (UpperCAmelCase__)							=    extended_euclid(lowerCAmelCase__    ,				a % b						)
 UpperCAmelCase__							=    a // b
 return (y, x - k * y)



def     lowerCAmelCase		(		_lowerCAmelCase				: int    ,				_lowerCAmelCase				: int						):




 """simple docstring"""







 if a < b:
  UpperCAmelCase__							=    b, a

 while a % b != 0:
  UpperCAmelCase__							=    b, a % b

 return b


if __name__ == "__main__":
  from doctest import testmod

  testmod(name="modular_division", verbose=True)
  testmod(name="modular_division2", verbose=True)
  testmod(name="invert_modulo", verbose=True)
  testmod(name="extended_gcd", verbose=True)
  testmod(name="extended_euclid", verbose=True)
  testmod(name="greatest_common_divisor", verbose=True)













def        _lowerCamelCase(      lowerCAmelCase__					:		int = 99_8001   ):





				'''simple docstring'''







				for number in range(n - 1     ,     9999     ,     -1   ):
								SCREAMING_SNAKE_CASE_ :						int    				= str(lowerCAmelCase__   )

								# checks whether 'str_number' is a palindrome.
								if str_number == str_number[::-1]:
												SCREAMING_SNAKE_CASE_ :						str    				= 999

												# if 'number' is a product of two 3-digit numbers
												# then number is the answer otherwise fetch next number.
												while divisor != 99:
																if (number % divisor == 0) and (len(str(number // divisor   )   ) == 3.0):
																				return number
																divisor -= 1
				raise ValueError('That number is larger than our acceptable range.'   )


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