M2 - EX欧几里得-乘法逆元

typedef long long llong;

template< class type >
type exgcd(type a, type b, type &x, type &y) {
	static type d;
	if (b) {
		d = exgcd(b, a % b, y, x);
		y -= a / b * x;
		return d;
	} else {
		x = 1, y = 0;
		return a;
	}
}