def modularquickpow(x, y, z):
    """
    Fastly computes (x^y) % z
    """
    if y == 0:
        return 1
    if y == 1:
        return (x % z)

    halfpow = modularquickpow(x, y//2, z) % z
    if (y % 2) == 0:
        return (halfpow * halfpow) % z
    else:
        return (((halfpow * halfpow) % z) * (x % z)) % z