



"""simple docstring"""


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"""


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

def 				_lowerCAmelCase   (     lowercase_		):
						return choose(8 + n	,			lowercase_		) + choose(9 + n	,			lowercase_		) - 10

def 				_lowerCAmelCase   (     lowercase_		):
						return sum(non_bouncy_exact(lowercase_		) for i in range(1	,			n + 1		)		)

def 				_lowerCAmelCase   (     lowercase_ = 100		):
						return non_bouncy_upto(lowercase_		)


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





