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

int inv(int a){
	int x,y,b=mod;
	exgcd(a,b,x,y);
	if (x<0) x+=mod;
	return x;
}