



from __future__ import annotations

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

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

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_	,			lowercase_		):
						UpperCAmelCase    =				invert_modulo(lowercase_	,			lowercase_		)
						UpperCAmelCase    =				(b * s) % n
						return x

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_		):
						assert a >= 0 and b >= 0

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

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_		):
						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 dataclasses import dataclass
from typing import Callable, Optional

import datasets







@dataclass
class    A_    (  datasets.BuilderConfig       ):



						"""simple docstring"""
						__UpperCamelCase	       =							None
						__UpperCamelCase	       =							None
						__UpperCamelCase	       =							None






						def 			UpperCAmelCase__  (      self				:str      )       ->    Optional[Any]:
												assert self.generator is not None, "generator must be specified"

												if self.gen_kwargs is None:
																		UpperCAmelCase    =				{}







class    A_    (  datasets.GeneratorBasedBuilder       ):



						"""simple docstring"""
						__UpperCamelCase	       =							GeneratorConfig






						def 			UpperCAmelCase__  (      self				:Union[str, Any]      )       ->    str:
												return datasets.DatasetInfo(features=self.config.features      )






						def 			UpperCAmelCase__  (      self				:List[Any]     ,						lowercase_				:List[Any]      )       ->    Union[str, Any]:
												return [datasets.SplitGenerator(name=datasets.Split.TRAIN     ,						gen_kwargs=self.config.gen_kwargs      )]






						def 			UpperCAmelCase__  (      self				:Optional[int]     ,						**lowercase_				:Dict      )       ->    str:
												for idx, ex in enumerate(self.config.generator(**lowercase_      )      ):
																		yield idx, ex





