





'''simple docstring'''






from __future__ import annotations





def      lowercase  (  lowerCAmelCase :						int   , lowerCAmelCase :						int   , lowerCAmelCase :						int):



				"""simple docstring"""


				assert n > 1 and a > 0 and greatest_common_divisor(lowerCAmelCase   , lowerCAmelCase) == 1
				((_A)	,       (_A)	,       (_A)) :				Union[str, Any]				=  extended_gcd(lowerCAmelCase   , lowerCAmelCase)  # Implemented below
				_A :				Optional[int]				=  (b * s) % n
				return x





def      lowercase  (  lowerCAmelCase :						int   , lowerCAmelCase :						int):



				"""simple docstring"""


				((_A)	,       (_A)) :				Any				=  extended_euclid(lowerCAmelCase   , lowerCAmelCase)  # Implemented below
				if b < 0:
								_A :				int				=  (b % n + n) % n
				return b





def      lowercase  (  lowerCAmelCase :						int   , lowerCAmelCase :						int   , lowerCAmelCase :						int):



				"""simple docstring"""


				_A :				Dict				=  invert_modulo(lowerCAmelCase   , lowerCAmelCase)
				_A :				str				=  (b * s) % n
				return x





def      lowercase  (  lowerCAmelCase :						int   , lowerCAmelCase :						int):



				"""simple docstring"""


				assert a >= 0 and b >= 0

				if b == 0:
								_A	,       _A	,       _A :				Optional[int]				=  a, 1, 0
				else:
								((_A)	,       (_A)	,       (_A)) :				Union[str, Any]				=  extended_gcd(lowerCAmelCase   , a % b)
								_A :				Dict				=  q
								_A :				Optional[Any]				=  p - q * (a // b)

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

				return (d, x, y)





def      lowercase  (  lowerCAmelCase :						int   , lowerCAmelCase :						int):



				"""simple docstring"""


				if b == 0:
								return (1, 0)
				((_A)	,       (_A)) :				Dict				=  extended_euclid(lowerCAmelCase   , a % b)
				_A :				Any				=  a // b
				return (y, x - k * y)





def      lowercase  (  lowerCAmelCase :						int   , lowerCAmelCase :						int):



				"""simple docstring"""


				if a < b:
								_A	,       _A :				int				=  b, a

				while a % b != 0:
								_A	,       _A :				str				=  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)







'''simple docstring'''






import sys

sys.set_int_max_str_digits(0)  # type: ignore





def      lowercase  (  lowerCAmelCase :						int):



				"""simple docstring"""


				_A :				List[Any]				=  [0] * 11
				_A :				Optional[Any]				=  [0] * 11

				# mark last 9 numbers
				for _ in range(9):
								_A :				Dict				=  1
								_A :				Optional[int]				=  number // 10
				# flag
				_A :				str				=  True

				# check last 9 numbers for pandigitality

				for x in range(9):
								if not check_last[x + 1]:
												_A :				Dict				=  False
				if not f:
								return f

				# mark first 9 numbers
				_A :				str				=  int(str(lowerCAmelCase)[:9])

				for _ in range(9):
								_A :				Tuple				=  1
								_A :				Union[str, Any]				=  number // 10

				# check first 9 numbers for pandigitality

				for x in range(9):
								if not check_front[x + 1]:
												_A :				Union[str, Any]				=  False
				return f





def      lowercase  (  lowerCAmelCase :						int):



				"""simple docstring"""


				_A :				Tuple				=  [0] * 11

				# mark last 9 numbers
				for _ in range(9):
								_A :				int				=  1
								_A :				Optional[int]				=  number // 10
				# flag
				_A :				List[str]				=  True

				# check last 9 numbers for pandigitality

				for x in range(9):
								if not check_last[x + 1]:
												_A :				Any				=  False
				return f





def      lowercase  (  ):



				"""simple docstring"""


				_A :				Union[str, Any]				=  1
				_A :				Tuple				=  1
				_A :				List[str]				=  2
				# temporary Fibonacci numbers

				_A :				List[str]				=  1
				_A :				str				=  1
				_A :				List[str]				=  2
				# temporary Fibonacci numbers mod 1e9

				# mod m=1e9, done for fast optimisation
				_A :				Any				=  [0] * 100_0000
				_A :				List[Any]				=  10_0000_0000

				for x in range(100_0000):
								_A :				Dict				=  (aa + ba) % m
								_A :				str				=  ba % m
								_A :				Union[str, Any]				=  ca % m
								if checka(lowerCAmelCase):
												_A :				List[str]				=  1

				for x in range(100_0000):
								_A :				str				=  a + b
								_A :				List[str]				=  b
								_A :				int				=  c
								# perform check only if in tocheck
								if tocheck[x + 3] and check(lowerCAmelCase):
												return x + 3  # first 2 already done
				return -1


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