

from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


_lowerCAmelCase     :			List[str]    ={"""configuration_nat""": ["""NAT_PRETRAINED_CONFIG_ARCHIVE_MAP""", """NatConfig"""]}


try:
			if not is_torch_available():
						raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
			pass
else:
			_lowerCAmelCase     :			Union[str, Any]    =[
			    """NAT_PRETRAINED_MODEL_ARCHIVE_LIST""",
			    """NatForImageClassification""",
			    """NatModel""",
			    """NatPreTrainedModel""",
			    """NatBackbone""",
			]

if TYPE_CHECKING:
			from .configuration_nat import NAT_PRETRAINED_CONFIG_ARCHIVE_MAP, NatConfig

			try:
						if not is_torch_available():
									raise OptionalDependencyNotAvailable()
			except OptionalDependencyNotAvailable:
						pass
			else:
						from .modeling_nat import (
						    NAT_PRETRAINED_MODEL_ARCHIVE_LIST,
						    NatBackbone,
						    NatForImageClassification,
						    NatModel,
						    NatPreTrainedModel,
						)

else:
			import sys

			_lowerCAmelCase     :			Any    =_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)


from __future__ import annotations



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



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	((UpperCAmelCase__)       ,	(UpperCAmelCase__)):  int		       =   extended_euclid(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			)  # Implemented below
	if b < 0:
		UpperCAmelCase__:  List[str]		       =   (b % n + n) % n
	return b



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	UpperCAmelCase__:  Union[str, Any]		       =   invert_modulo(SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			)
	UpperCAmelCase__:  Any		       =   (b * s) % n
	return x



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	assert a >= 0 and b >= 0

	if b == 0:
		UpperCAmelCase__       ,	UpperCAmelCase__       ,	UpperCAmelCase__:  List[Any]		       =   a, 1, 0
	else:
		((UpperCAmelCase__)       ,	(UpperCAmelCase__)       ,	(UpperCAmelCase__)):  Tuple		       =   extended_gcd(SCREAMING_SNAKE_CASE  ,a % b			)
		UpperCAmelCase__:  Union[str, Any]		       =   q
		UpperCAmelCase__:  Union[str, Any]		       =   p - q * (a // b)

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

	return (d, x, y)



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	if b == 0:
		return (1, 0)
	((UpperCAmelCase__)       ,	(UpperCAmelCase__)):  List[str]		       =   extended_euclid(SCREAMING_SNAKE_CASE  ,a % b			)
	UpperCAmelCase__:  Optional[Any]		       =   a // b
	return (y, x - k * y)



def  _A  (			SCREAMING_SNAKE_CASE  ,SCREAMING_SNAKE_CASE			):
	if a < b:
		UpperCAmelCase__       ,	UpperCAmelCase__:  str		       =   b, a

	while a % b != 0:
		UpperCAmelCase__       ,	UpperCAmelCase__:  Union[str, Any]		       =   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)