


'''simple docstring'''



from __future__ import annotations






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






def 						lowerCamelCase							(_SCREAMING_SNAKE_CASE   :     int		,   _SCREAMING_SNAKE_CASE   :     int     ):
					((__a)					,       (__a))    : Dict      					=						extended_euclid(_SCREAMING_SNAKE_CASE		,   _SCREAMING_SNAKE_CASE     )  # Implemented below
					if b < 0:
										__a    : Union[str, Any]      					=						(b % n + n) % n
					return b






def 						lowerCamelCase							(_SCREAMING_SNAKE_CASE   :     int		,   _SCREAMING_SNAKE_CASE   :     int		,   _SCREAMING_SNAKE_CASE   :     int     ):
					__a    : List[Any]      					=						invert_modulo(_SCREAMING_SNAKE_CASE		,   _SCREAMING_SNAKE_CASE     )
					__a    : str      					=						(b * s) % n
					return x






def 						lowerCamelCase							(_SCREAMING_SNAKE_CASE   :     int		,   _SCREAMING_SNAKE_CASE   :     int     ):
					assert a >= 0 and b >= 0

					if b == 0:
										__a					,       __a					,       __a    : Dict      					=						a, 1, 0
					else:
										((__a)					,       (__a)					,       (__a))    : Any      					=						extended_gcd(_SCREAMING_SNAKE_CASE		,   a % b     )
										__a    : List[str]      					=						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 						lowerCamelCase							(_SCREAMING_SNAKE_CASE   :     int		,   _SCREAMING_SNAKE_CASE   :     int     ):
					if b == 0:
										return (1, 0)
					((__a)					,       (__a))    : Any      					=						extended_euclid(_SCREAMING_SNAKE_CASE		,   a % b     )
					__a    : Optional[int]      					=						a // b
					return (y, x - k * y)






def 						lowerCamelCase							(_SCREAMING_SNAKE_CASE   :     int		,   _SCREAMING_SNAKE_CASE   :     int     ):
					if a < b:
										__a					,       __a    : Any      					=						b, a

					while a % b != 0:
										__a					,       __a    : Dict      					=						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'''



def 						lowerCamelCase							(_SCREAMING_SNAKE_CASE   :     set		,   _SCREAMING_SNAKE_CASE   :     set     ):
					assert isinstance(_SCREAMING_SNAKE_CASE		,   _SCREAMING_SNAKE_CASE     ), F"""The input value of [set_a={set_a}] is not a set"""
					assert isinstance(_SCREAMING_SNAKE_CASE		,   _SCREAMING_SNAKE_CASE     ), F"""The input value of [set_b={set_b}] is not a set"""

					return {a + b for a in set_a for b in set_b}


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

	testmod()



