



from __future__ import annotations


def 						_UpperCAmelCase							( snake_case      ,		snake_case      ,		snake_case     ):





					"""simple docstring"""

					assert n > 1 and a > 0 and greatest_common_divisor(snake_case      ,		snake_case     ) == 1
					((_lowerCAmelCase)      ,      (_lowerCAmelCase)      ,      (_lowerCAmelCase))         =       extended_gcd(snake_case      ,		snake_case     )  # Implemented below
					_lowerCAmelCase         =       (b * s) % n
					return x


def 						_UpperCAmelCase							( snake_case      ,		snake_case     ):





					"""simple docstring"""

					((_lowerCAmelCase)      ,      (_lowerCAmelCase))         =       extended_euclid(snake_case      ,		snake_case     )  # Implemented below
					if b < 0:
										_lowerCAmelCase         =       (b % n + n) % n
					return b


def 						_UpperCAmelCase							( snake_case      ,		snake_case      ,		snake_case     ):





					"""simple docstring"""

					_lowerCAmelCase         =       invert_modulo(snake_case      ,		snake_case     )
					_lowerCAmelCase         =       (b * s) % n
					return x


def 						_UpperCAmelCase							( snake_case      ,		snake_case     ):





					"""simple docstring"""

					assert a >= 0 and b >= 0

					if b == 0:
										_lowerCAmelCase      ,      _lowerCAmelCase      ,      _lowerCAmelCase         =       a, 1, 0
					else:
										((_lowerCAmelCase)      ,      (_lowerCAmelCase)      ,      (_lowerCAmelCase))         =       extended_gcd(snake_case      ,		a % b     )
										_lowerCAmelCase         =       q
										_lowerCAmelCase         =       p - q * (a // b)

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

					return (d, x, y)


def 						_UpperCAmelCase							( snake_case      ,		snake_case     ):





					"""simple docstring"""

					if b == 0:
										return (1, 0)
					((_lowerCAmelCase)      ,      (_lowerCAmelCase))         =       extended_euclid(snake_case      ,		a % b     )
					_lowerCAmelCase         =       a // b
					return (y, x - k * y)


def 						_UpperCAmelCase							( snake_case      ,		snake_case     ):





					"""simple docstring"""

					if a < b:
										_lowerCAmelCase      ,      _lowerCAmelCase         =       b, a

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







_A		:					Union[str, Any]          =							1_000



def      __lowerCAmelCase    (				snake_case						:     float			)							->				float:
   return x * x



def      __lowerCAmelCase    (				snake_case						:     Optional[int]    ,   snake_case						:     float    ,   snake_case						:     float    ,   snake_case						:     int = 4			)							->				float:
   assert callable(
       snake_case			), f'the function(object) passed should be callable your input : {function}'
   assert isinstance(snake_case    ,   (float, int)			), f'a should be float or integer your input : {a}'
   assert isinstance(function(snake_case			)    ,   (float, int)			), (
       "the function should return integer or float return type of your function, "
       f'{type(snake_case			)}'
   )
   assert isinstance(snake_case    ,   (float, int)			), f'b should be float or integer your input : {b}'
   assert (
       isinstance(snake_case    ,   snake_case			) and precision > 0
   ), f'precision should be positive integer your input : {precision}'

   # just applying the formula of simpson for approximate integration written in
   # mentioned article in first comment of this file and above this function

   __lowerCamelCase:					List[str]	 =						(b - a) / N_STEPS
   __lowerCamelCase:					Optional[Any]	 =						function(snake_case			) + function(snake_case			)

   for i in range(1    ,   snake_case			):
      __lowerCamelCase:					Dict	 =						a + h * i
      result += function(snake_case			) * (4 if i % 2 else 2)

   result *= h / 3
   return round(snake_case    ,   snake_case			)


if __name__ == "__main__":
   import doctest

   doctest.testmod()


