public static long modMultInverse(long a, long N) {
		// we want to calculate b s.t.
		// ab = 1 (mod N)
		// equiviliantly,
		// ab - 1 = Nq
		// ab + Nq = 1 (we don't care about the sign of q)
		// this is a diophantine equation

		// notable, if gcd(a, N) != 1, then there is no inverse
		long[] result = extendedEuler(a, N);
		if(result[2] != 1){
			return -1;
		}
//		System.out.println(Arrays.toString(result));
		return result[0];
	}