#include <cstdio>
#include <algorithm>
using namespace std;

int gcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	else 
	{
		int X,Y,d;
		d=gcd(b,a%b,X,Y);
		x=Y,y=X-Y*(a/b);
		return d;
	}
}
int A,N,D,x,y;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
		scanf("%d%d",&A,&N);
		D=gcd(A,N,x,y);
		while(x<0)x+=N;
		printf("%d",x%N);
    return 0;
}