/*
    Keep It Simple!
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<stdio.h>
#include<list>
#include<stack>

#define MaxN 100001

using namespace std;

int N, M;

int CMMDC(int a, int b, int &x, int &y)
{
	if (!b)
	{
		x = 1; y = 0; return a;
	}
	else
	{
		int x0, y0, d;
		d = CMMDC(b, a%b, x0, y0);
		x = y0;
		y = x0 - (a / b)*y0;
	}
}

int main()
{
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);

	scanf("%d%d", &N,&M);

	int x, y;
	int d = CMMDC(N, M, x, y);
	
	while(x < 0)
		x += M;

	printf("%d", x);

	return 0;
}