





'''simple docstring'''

from __future__ import annotations


def 						__UpperCamelCase						(			_UpperCAmelCase,       _UpperCAmelCase,       _UpperCAmelCase  ):
		assert n > 1 and a > 0 and greatest_common_divisor(_UpperCAmelCase,       _UpperCAmelCase  ) == 1
		(__UpperCAmelCase)	:							Optional[Any]     =     extended_gcd(_UpperCAmelCase,       _UpperCAmelCase  )  # Implemented below
		__UpperCAmelCase	:							Dict     =     (b * s) % n
		return x


def 						__UpperCamelCase						(			_UpperCAmelCase,       _UpperCAmelCase  ):
		(__UpperCAmelCase)	:							Tuple     =     extended_euclid(_UpperCAmelCase,       _UpperCAmelCase  )  # Implemented below
		if b < 0:
				__UpperCAmelCase	:							Optional[Any]     =     (b % n + n) % n
		return b


def 						__UpperCamelCase						(			_UpperCAmelCase,       _UpperCAmelCase,       _UpperCAmelCase  ):
		__UpperCAmelCase	:							Tuple     =     invert_modulo(_UpperCAmelCase,       _UpperCAmelCase  )
		__UpperCAmelCase	:							Tuple     =     (b * s) % n
		return x


def 						__UpperCamelCase						(			_UpperCAmelCase,       _UpperCAmelCase  ):
		assert a >= 0 and b >= 0

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

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

		return (d, x, y)


def 						__UpperCamelCase						(			_UpperCAmelCase,       _UpperCAmelCase  ):



		if b == 0:
				return (1, 0)
		(__UpperCAmelCase)	:							int     =     extended_euclid(_UpperCAmelCase,       a % b  )
		__UpperCAmelCase	:							Dict     =     a // b
		return (y, x - k * y)


def 						__UpperCamelCase						(			_UpperCAmelCase,       _UpperCAmelCase  ):



		if a < b:
				__UpperCAmelCase	:							Optional[Any]     =     b, a

		while a % b != 0:
				__UpperCAmelCase	:							Optional[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)








from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


__UpperCamelCase							:							Dict    							=					{
    "configuration_dpr": ["DPR_PRETRAINED_CONFIG_ARCHIVE_MAP", "DPRConfig"],
    "tokenization_dpr": [
        "DPRContextEncoderTokenizer",
        "DPRQuestionEncoderTokenizer",
        "DPRReaderOutput",
        "DPRReaderTokenizer",
    ],
}


try:
       if not is_tokenizers_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       __UpperCamelCase							:							Any    							=					[
           "DPRContextEncoderTokenizerFast",
           "DPRQuestionEncoderTokenizerFast",
           "DPRReaderTokenizerFast",
       ]

try:
       if not is_torch_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       __UpperCamelCase							:							str    							=					[
           "DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST",
           "DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST",
           "DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST",
           "DPRContextEncoder",
           "DPRPretrainedContextEncoder",
           "DPRPreTrainedModel",
           "DPRPretrainedQuestionEncoder",
           "DPRPretrainedReader",
           "DPRQuestionEncoder",
           "DPRReader",
       ]

try:
       if not is_tf_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       __UpperCamelCase							:							int    							=					[
           "TF_DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST",
           "TF_DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST",
           "TF_DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST",
           "TFDPRContextEncoder",
           "TFDPRPretrainedContextEncoder",
           "TFDPRPretrainedQuestionEncoder",
           "TFDPRPretrainedReader",
           "TFDPRQuestionEncoder",
           "TFDPRReader",
       ]


if TYPE_CHECKING:
       from .configuration_dpr import DPR_PRETRAINED_CONFIG_ARCHIVE_MAP, DPRConfig
       from .tokenization_dpr import (
           DPRContextEncoderTokenizer,
           DPRQuestionEncoderTokenizer,
           DPRReaderOutput,
           DPRReaderTokenizer,
       )

       try:
              if not is_tokenizers_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .tokenization_dpr_fast import (
                  DPRContextEncoderTokenizerFast,
                  DPRQuestionEncoderTokenizerFast,
                  DPRReaderTokenizerFast,
              )

       try:
              if not is_torch_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_dpr import (
                  DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                  DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                  DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST,
                  DPRContextEncoder,
                  DPRPretrainedContextEncoder,
                  DPRPreTrainedModel,
                  DPRPretrainedQuestionEncoder,
                  DPRPretrainedReader,
                  DPRQuestionEncoder,
                  DPRReader,
              )

       try:
              if not is_tf_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_tf_dpr import (
                  TF_DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                  TF_DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                  TF_DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST,
                  TFDPRContextEncoder,
                  TFDPRPretrainedContextEncoder,
                  TFDPRPretrainedQuestionEncoder,
                  TFDPRPretrainedReader,
                  TFDPRQuestionEncoder,
                  TFDPRReader,
              )

else:
       import sys

       __UpperCamelCase							:							Dict    							=					_LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)


