//扩展欧几里得 

 
int exgcd(int a, int b, int &x, int &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	int d = exgcd(b, a%b, y, x);
	y -= (a / b) * x;
	return d;
}


typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	ll d = exgcd(b, a%b, y, x);
	y -= (a / b) * x;
	return d;
}