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