def solve(a, m, k):
    """
    Solve simple linear conguruence equation
    Find the least x such that ax=k (mod m)
    """

    if a == 0:
        if k == 0:
            return 0
        else:
            raise ValueError(f"{a}x%{m}={k} - No SOLUTIONS")

    if a == 1:
        return k % m

    if k % a == 0:
        return k // a

    new_x = solve(
        a=m % a,
        m=a,
        k=(a - k) % a
    )
    x = (k + new_x * m) // a
    return x