'''simple docstring'''

from __future__ import annotations







def 					UpperCamelCase_						( snake_case_	:	int						,		snake_case_	:	int						,		snake_case_	:	int				) ->					int:






 '''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_	:	int						,		snake_case_	:	int				) ->					int:






 '''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_	:	int						,		snake_case_	:	int						,		snake_case_	:	int				) ->					int:






 '''simple docstring'''

 __lowerCAmelCase    							=						invert_modulo(snake_case_						,		snake_case_				)
 __lowerCAmelCase    							=						(b * s) % n
 return x







def 					UpperCamelCase_						( snake_case_	:	int						,		snake_case_	:	int				) ->					tuple[int, int, int]:






 '''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_	:	int						,		snake_case_	:	int				) ->					tuple[int, int]:






 '''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_	:	int						,		snake_case_	:	int				) ->					int:






 '''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)







'''simple docstring'''

from unittest.mock import patch

import datasets
from datasets import Dataset







def 					UpperCamelCase_						( ) ->					Dict:






 '''simple docstring'''

 __lowerCAmelCase    							=						Dataset.from_dict({"""col_1""": [3, 2, 0, 1]}				)

 with patch("""tqdm.auto.tqdm"""				) as mock_tqdm:
  datasets.disable_progress_bar()
  dset.map(lambda snake_case_				: {"col_2": x["col_1"] + 1}				)
  mock_tqdm.assert_not_called()

  mock_tqdm.reset_mock()

  datasets.enable_progress_bar()
  dset.map(lambda snake_case_				: {"col_2": x["col_1"] + 1}				)
  mock_tqdm.assert_called()






