
from __future__ import annotations



def 		lowercase_     (  A__					,						A__					,						A__						)				->				int:
    """simple docstring"""

    assert n > 1 and a > 0 and greatest_common_divisor(A__					,						A__						) == 1
    ((snake_case)	,				(snake_case)	,				(snake_case))						=   extended_gcd(A__					,						A__						)  # Implemented below
    snake_case						=   (b * s) % n
    return x



def 		lowercase_     (  A__					,						A__						)				->				int:
    """simple docstring"""

    ((snake_case)	,				(snake_case))						=   extended_euclid(A__					,						A__						)  # Implemented below
    if b < 0:
        snake_case						=   (b % n + n) % n
    return b



def 		lowercase_     (  A__					,						A__					,						A__						)				->				int:
    """simple docstring"""

    snake_case						=   invert_modulo(A__					,						A__						)
    snake_case						=   (b * s) % n
    return x



def 		lowercase_     (  A__					,						A__						)				->				tuple[int, int, int]:
    """simple docstring"""

    assert a >= 0 and b >= 0

    if b == 0:
        snake_case	,				snake_case	,				snake_case						=   a, 1, 0
    else:
        ((snake_case)	,				(snake_case)	,				(snake_case))						=   extended_gcd(A__					,						a % b						)
        snake_case						=   q
        snake_case						=   p - q * (a // b)

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

    return (d, x, y)



def 		lowercase_     (  A__					,						A__						)				->				tuple[int, int]:
    """simple docstring"""

    if b == 0:
        return (1, 0)
    ((snake_case)	,				(snake_case))						=   extended_euclid(A__					,						a % b						)
    snake_case						=   a // b
    return (y, x - k * y)



def 		lowercase_     (  A__					,						A__						)				->				int:
    """simple docstring"""

    if a < b:
        snake_case	,				snake_case						=   b, a

    while a % b != 0:
        snake_case	,				snake_case						=   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)



_A       =					{
    "0": 1,
    "1": 1,
    "2": 2,
    "3": 6,
    "4": 24,
    "5": 1_20,
    "6": 7_20,
    "7": 50_40,
    "8": 4_03_20,
    "9": 36_28_80,
}

_A       =					{1_45: 1_45}

_A       =					{
    1_45: 0,
    1_69: 3,
    3_63_01: 3,
    14_54: 3,
    8_71: 2,
    4_53_61: 2,
    8_72: 2,
}



def 		lowercase_     (  A__						)				->				int:
    """simple docstring"""

    if n in CACHE_SUM_DIGIT_FACTORIALS:
        return CACHE_SUM_DIGIT_FACTORIALS[n]
    snake_case						=   sum(DIGIT_FACTORIALS[let] for let in str(A__						)						)
    snake_case						=   ret
    return ret



def 		lowercase_     (  A__					,						A__ = None						)				->				int:
    """simple docstring"""

    snake_case						=   previous or set()
    if n in CHAIN_LENGTH_CACHE:
        return CHAIN_LENGTH_CACHE[n]
    snake_case						=   sum_digit_factorials(A__						)
    if next_number in previous:
        snake_case						=   0
        return 0
    else:
        previous.add(A__						)
        snake_case						=   1 + chain_length(A__					,						A__						)
        snake_case						=   ret
        return ret



def 		lowercase_     (  A__ = 60					,						A__ = 100_0000						)				->				int:
    """simple docstring"""

    return sum(1 for i in range(1					,						A__						) if chain_length(A__						) == num_terms						)


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

