#include <fstream>
using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
long long A, N;
long long EuclidExtins(long long a, long long b, long long&x, long long& y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	long long x1, y1;
	long long r = EuclidExtins(b, a%b, x1, y1);

	x = y1;
	y = x1 - (a / b) * y1;

	return r;
}
int main()
{
	
	in >> A >> N;
	long long x, y;

	long long gcd = EuclidExtins(A, N, x, y);

	out << (x + N) % N;
}