#include<fstream>

using namespace std;

void euclid( long long A, long long B, long long &x, long long &y){
	if( B == 0 ){
		x = 1;
		y = 0;
		return;
	}
	long long X0,Y0;
	euclid( B, A%B, X0, Y0);
	x = Y0;
	y = X0 - ( A/B ) * Y0;

}

int main(){

	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	
	long long A,N,x,y;
	f>>A>>N;
	euclid(A,N,x,y);
	if( x<0 ) g<<N + x%N;
	else g<<x%N;
	return 0;
}