public static final long inv(long x) throws Exception {
        if (x == 0) throw new Exception ("Divide by zero");
        long f = p;
        long g = x;
        long a = 0;
        long b = 1;
        while (g != 0) {
            long h = f % g;
            long c = a - f / g * b;
            f = g;
            g = h;
            a = b;
            b = c;
        }
        return (a + p) % p;
    }