#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

FILE *e = fopen ("inversmodular.in", "r");
FILE *f = fopen ("inversmodular.out", "w");

int A, MOD, X;
	
int phi (int n)
{
	int x = n, r = n;
	for (int d = 2; d * d <= n; d++)
	{
		if (x % d == 0)
			r = r / d * (d - 1);
		while (x % d == 0)
			x /= d;
	}
	if (x != 1)
		r = r / x * (x - 1);
	return r;	
}

int exp (int n, int e)
{
	long long x = 1, a = n;
	while (e != 0)
	{
		if (e & 1)
			x = x * a % MOD;
		a = a * a % MOD;
		e >>= 1;
	}
	return x;
}

int main ()
{
	fscanf (e, "%d%d", &A, &MOD);
	int fi = phi (MOD);
	X = exp (A, fi - 1);
	fprintf (f, "%d\n", X);
	return 0;
}