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