#include <iostream>
#include <fstream>

using namespace std;

long long quick(long long, long long);
long long n,a;
int main()
{
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	scanf("%d%d", &a, &n);
	long long d = 2;
	long long cn = n;
	long long phi = n - 1;
	for (long long i = 2; i*i <= n; i ++)
		if (!(n%i))
		{
			phi -= phi / i;
			while (!(n%i)) n /= i;
		}
	if (n>1) phi -= phi / n;
    n=cn;
	printf("%d\n", quick(a, phi - 1));
    return 0;
}

long long quick(long long nr, long long e) {
	if (e == 0) {
		return 1;
	}
	if (e == 1) {
		return nr;
	}
	long long p = 1;
	if (e % 2 == 1) {
		p = nr;
	}
	return (((p%n)*(quick(nr, e / 2) % n)) % n*(quick(nr, e / 2) % n)) % n;
}