def legendre(a, p):
    """
    Legendre symbol (a|p): 1 if a is a quadratic residue mod p, -1 if it isn't,
    and 0 if a % p == 0.  Not meaningful if p isn't prime.
    Input:
        a -- an integer
        p -- a prime
    Output: -1, 0, or 1
    Examples:
    >>> [legendre(a, 11) for a in [-10, -7, -4, -2, -1, 0, 1, 2, 4, 7, 10]]
    [1, 1, -1, 1, -1, 0, 1, -1, 1, -1, -1]
    >>> [legendre(a, 17) for a in [-10, -9, -4, -2, -1, 0, 1, 2, 4, 9, 10]]
    [-1, 1, 1, 1, 1, 0, 1, 1, 1, 1, -1]
    >>> [legendre(a, 101) for a in [-10, -9, -4, -2, -1, 0, 1, 2, 4, 9, 10]]
    [-1, 1, 1, -1, 1, 0, 1, -1, 1, 1, -1]
    """
    return (pow(a, p - 1 >> 1, p) + 1) % p - 1
