int prime; 
void init(int p)
{
	prime=p;
}

int inv(int x)
{
	int s1=1,s2=0;
	int t1=0,t2=1;
	int a=x,b=prime;
	int q;
	while(b!=0)
	{
		q=a/b;
		int c=a;
		a=b;
		b=c-a*q;
		int s3=s2;
		s2=-1*q*s3+s1;
		s1=s3;
		int t3=t2;
		t2=-1*q*t3+t1;
		t1=t3;
	}
	return s2;
}