#include <cstdio>

#define ll long long

ll A, N, InvMod, Aux;

inline void EE( ll &X, ll &Y, ll A, ll B )
{
	if( !B )
	{
		X = 1, Y = 0;
		return;
	}
	
	EE( X, Y, B, A%B );
	ll aux = X;
	X = Y;
	Y = aux - (A/B)*Y;
}

int main()
{
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	
	scanf("%lld%lld", &A, &N );
	EE( InvMod, Aux, A, N );
	while( InvMod < 0 )
		InvMod += N;
	printf("%lld\n", InvMod );
	
	return 0;
}