

'''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
  ((UpperCAmelCase)							,      (UpperCAmelCase)							,      (UpperCAmelCase))													=	extended_gcd(SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE						)  # Implemented below
  UpperCAmelCase													=	(b * s) % n
  return x


def       lowerCamelCase__		(						SCREAMING_SNAKE_CASE      :   int       ,   SCREAMING_SNAKE_CASE      :   int						):
  ((UpperCAmelCase)							,      (UpperCAmelCase))													=	extended_euclid(SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE						)  # Implemented below
  if b < 0:
    UpperCAmelCase													=	(b % n + n) % n
  return b


def       lowerCamelCase__		(						SCREAMING_SNAKE_CASE      :   int       ,   SCREAMING_SNAKE_CASE      :   int       ,   SCREAMING_SNAKE_CASE      :   int						):
  UpperCAmelCase													=	invert_modulo(SCREAMING_SNAKE_CASE       ,   SCREAMING_SNAKE_CASE						)
  UpperCAmelCase													=	(b * s) % n
  return x


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

  if b == 0:
    UpperCAmelCase							,      UpperCAmelCase							,      UpperCAmelCase													=	a, 1, 0
  else:
    ((UpperCAmelCase)							,      (UpperCAmelCase)							,      (UpperCAmelCase))													=	extended_gcd(SCREAMING_SNAKE_CASE       ,   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__		(						SCREAMING_SNAKE_CASE      :   int       ,   SCREAMING_SNAKE_CASE      :   int						):
  if b == 0:
    return (1, 0)
  ((UpperCAmelCase)							,      (UpperCAmelCase))													=	extended_euclid(SCREAMING_SNAKE_CASE       ,   a % b						)
  UpperCAmelCase													=	a // b
  return (y, x - k * y)


def       lowerCamelCase__		(						SCREAMING_SNAKE_CASE      :   int       ,   SCREAMING_SNAKE_CASE      :   int						):
  if a < b:
    UpperCAmelCase							,      UpperCAmelCase													=	b, a

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





'''simple docstring'''




from collections import OrderedDict
from dataclasses import fields
from typing import Any, Tuple

import numpy as np

from .import_utils import is_torch_available


def       lowerCamelCase__		(						SCREAMING_SNAKE_CASE      :   Optional[Any]						):
  if is_torch_available():
    import torch

    if isinstance(SCREAMING_SNAKE_CASE       ,   torch.Tensor						):
      return True

  return isinstance(SCREAMING_SNAKE_CASE       ,   np.ndarray						)



class        lowercase_	(		a ):

  '''simple docstring'''





  def 						snake_case_			(     self     )							->				List[str]:


    """simple docstring"""
    UpperCAmelCase													=	fields(self     )

    # Safety and consistency checks
    if not len(a_     ):
      raise ValueError(F'''{self.__class__.__name__} has no fields.'''     )

    UpperCAmelCase													=	getattr(self   , class_fields[0].name     )
    UpperCAmelCase													=	all(getattr(self   , field.name     ) is None for field in class_fields[1:]     )

    if other_fields_are_none and isinstance(a_   , a_     ):
      for key, value in first_field.items():
        UpperCAmelCase													=	value
    else:
      for field in class_fields:
        UpperCAmelCase													=	getattr(self   , field.name     )
        if v is not None:
          UpperCAmelCase													=	v
  def __delitem__(     self   , *a_   , **a_     )							->				int:


    """simple docstring"""
    raise Exception(F'''You cannot use ``__delitem__`` on a {self.__class__.__name__} instance.'''     )
  def 						snake_case_			(     self   , *a_   , **a_     )							->				Tuple:


    """simple docstring"""
    raise Exception(F'''You cannot use ``setdefault`` on a {self.__class__.__name__} instance.'''     )
  def 						snake_case_			(     self   , *a_   , **a_     )							->				int:


    """simple docstring"""
    raise Exception(F'''You cannot use ``pop`` on a {self.__class__.__name__} instance.'''     )
  def 						snake_case_			(     self   , *a_   , **a_     )							->				Dict:


    """simple docstring"""
    raise Exception(F'''You cannot use ``update`` on a {self.__class__.__name__} instance.'''     )
  def __getitem__(     self   , a_     )							->				Tuple:


    """simple docstring"""
    if isinstance(a_   , a_     ):
      UpperCAmelCase													=	dict(self.items()     )
      return inner_dict[k]
    else:
      return self.to_tuple()[k]
  def __setattr__(     self   , a_   , a_     )							->				Dict:


    """simple docstring"""
    if name in self.keys() and value is not None:
      # Don't call self.__setitem__ to avoid recursion errors
      super().__setitem__(a_   , a_     )
    super().__setattr__(a_   , a_     )
  def __setitem__(     self   , a_   , a_     )							->				str:


    """simple docstring"""
    # Will raise a KeyException if needed
    super().__setitem__(a_   , a_     )
    # Don't call self.__setattr__ to avoid recursion errors
    super().__setattr__(a_   , a_     )





  def 						snake_case_			(     self     )							->				Tuple[Any]:


    """simple docstring"""
    return tuple(self[k] for k in self.keys()     )


