#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "inversmodular.in"
#define FOUT "inversmodular.out"
#define LL long long

LL A, N;

	int main ()
	{
		LL exp, i, p, res, N0;

		freopen (FIN, "r", stdin);
		freopen (FOUT, "w", stdout);
	
		scanf ("%lld %lld", &A, &N);
		exp = N, N0 = N;
		for (i = 2; i * i <= N; ++i)
		{
			if (N % i == 0) 
			{
				while (N % i == 0) N /= i;
				exp = (exp / i) * (i - 1);
			}
		}
		if (N != 1) exp = (exp / N) * (N - 1);
		exp -= 1;
	
		res = 1;
		for (p = 1; p <= exp; p <<= 1)
		{
			if (p & exp) res = (res * A) % N0;
			A = (A * A) % N0;
		}

		printf ("%lld\n", res);

		return 0;
	}