






"""simple docstring"""



import sys




def 						lowerCamelCase_				(  __A  :		Optional[Any]			,	__A  :		Any			):
					if not numbers:
										return 0
					if target == 0 and target in numbers:
										return 0
					if not isinstance(__A			,	(list, tuple)			) or not all(
					    isinstance(__A			,	__A			) for number in numbers			):
										raise ValueError('numbers must be an iterable of integers'			)

					lowerCamelCase__				=0
					lowerCamelCase__				=sys.maxsize

					while right < len(__A			):
										curr_sum += numbers[right]
										while curr_sum >= target and left <= right:
															lowerCamelCase__				=min(__A			,	right - left + 1			)
															curr_sum -= numbers[left]
															left += 1
										right += 1

					return 0 if min_len == sys.maxsize else min_len







"""simple docstring"""



from __future__ import annotations




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			,	__A  :		int			):
					assert n > 1 and a > 0 and greatest_common_divisor(__A			,	__A			) == 1
					((lowerCamelCase__)				,     (lowerCamelCase__)				,     (lowerCamelCase__))				=extended_gcd(__A			,	__A			)  # Implemented below
					lowerCamelCase__				=(b * s) % n
					return x




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




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




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			):
					assert a >= 0 and b >= 0

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




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			):
					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)