#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>

typedef long long LL;

const char IN[] = "inversmodular.in", OUT[] = "inversmodular.out";

using namespace std;

LL A, N;
LL phi;

inline void read_data()
{
	ifstream fin(IN);
	fin >> A >> N;
	fin.close();
}

//fi(N) = nr. de numere < N prime cu N
LL getPhi(LL N)
{
	int count = N;
	for (LL i = 2; i * i < N; ++i) {
		if (N % i == 0) {
			while (N % i == 0) N /= i;
			count = count / i * (i - 1);
		}
	}
	if (N != 1) count = count / N * (N - 1);
	return count;
}

LL logPow(LL B, LL EXP, LL MOD)
{
	if (EXP == 0) return 1;
	if (EXP == 1) return B;
	LL half = logPow(B, EXP / 2, MOD);
	if (EXP & 1) return half * B % MOD * half % MOD;
	return half * half % MOD;
}

int main()
{
	ofstream fout(OUT);
	read_data();
	phi = getPhi(N);
	if (phi == N) --phi;
	fout << logPow(A, phi - 1, N) << endl;
	return 0;
}