#include <fstream>
#include <cstdlib>

using namespace std;
inline void gcd( int a, int b, int& x, int& y )
{
	if( !b )
	{
		x=1;
		y=0;
		return;
	}
	int x0, y0;
	gcd( b, a%b, x0, y0 );
	x=y0;
	y=x0-(a/b)*y0;
}
int main( void )
{
	int A, N, x, y;
	ifstream in( "inversmodular.in" );
	in>>A>>N;
	gcd( A, N, x, y );
	ofstream out( "inversmodular.out" );
	out<<( x < 0 ? (0LL+x+N)%N : x )<<'\n';
	return EXIT_SUCCESS;
}