

'''simple docstring'''

from __future__ import annotations





def 				lowercase (					__magic_name__			,   __magic_name__			,   __magic_name__							):



					'''simple docstring'''







					assert n > 1 and a > 0 and greatest_common_divisor(__magic_name__			,   __magic_name__							) == 1
					((UpperCAmelCase) ,			(UpperCAmelCase) ,			(UpperCAmelCase))		:							Optional[int]        =       extended_gcd(__magic_name__			,   __magic_name__							)  # Implemented below
					UpperCAmelCase		:							int        =       (b * s) % n
					return x





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					((UpperCAmelCase) ,			(UpperCAmelCase))		:							str        =       extended_euclid(__magic_name__			,   __magic_name__							)  # Implemented below
					if b < 0:
										UpperCAmelCase		:							str        =       (b % n + n) % n
					return b





def 				lowercase (					__magic_name__			,   __magic_name__			,   __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							int        =       invert_modulo(__magic_name__			,   __magic_name__							)
					UpperCAmelCase		:							Tuple        =       (b * s) % n
					return x





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					assert a >= 0 and b >= 0

					if b == 0:
										UpperCAmelCase ,			UpperCAmelCase ,			UpperCAmelCase		:							int        =       a, 1, 0
					else:
										((UpperCAmelCase) ,			(UpperCAmelCase) ,			(UpperCAmelCase))		:							Optional[int]        =       extended_gcd(__magic_name__			,   a % b							)
										UpperCAmelCase		:							Dict        =       q
										UpperCAmelCase		:							Optional[int]        =       p - q * (a // b)

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

					return (d, x, y)





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					if b == 0:
										return (1, 0)
					((UpperCAmelCase) ,			(UpperCAmelCase))		:							Union[str, Any]        =       extended_euclid(__magic_name__			,   a % b							)
					UpperCAmelCase		:							List[Any]        =       a // b
					return (y, x - k * y)





def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					if a < b:
										UpperCAmelCase ,			UpperCAmelCase		:							Dict        =       b, a

					while a % b != 0:
										UpperCAmelCase ,			UpperCAmelCase		:							Optional[int]        =       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'''

def 				lowercase (					__magic_name__			,   __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							Dict        =       1.0
					for i in range(1			,   r + 1							):
										ret *= (n + 1 - i) / i
					return round(__magic_name__							)





def 				lowercase (					__magic_name__							):



					'''simple docstring'''







					return choose(8 + n			,   __magic_name__							) + choose(9 + n			,   __magic_name__							) - 10





def 				lowercase (					__magic_name__							):



					'''simple docstring'''







					return sum(non_bouncy_exact(__magic_name__							) for i in range(1			,   n + 1							)							)





def 				lowercase (					__magic_name__ = 100							):



					'''simple docstring'''







					return non_bouncy_upto(__magic_name__							)


if __name__ == "__main__":
				print(F'{solution() = }')
