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

using namespace std;

string NumeFisier = "inversmodular";
ifstream fin(NumeFisier + ".in");
ofstream fout(NumeFisier + ".out");

typedef unsigned long long int ull;

ull Totien(ull N)
{
	ull rez = N;
	ull i = 2;
	while (N > 1)
	{
		if (N % i == 0)
		{
			rez = (rez / i) * (i-1);
			while (N % i == 0)
				N /= i;
		}
		i++;
		if (i * i > N)
			i = N;
	}
	return rez;
}

ull FastExpo(ull baza, ull exp, ull N)
{
	ull rez = 1;
	while (exp)
	{
		if (exp % 2 == 1)
			rez = ((rez % N) * (baza % N)) % N;

		baza = (baza % N) * (baza % N);
		exp /= 2;
	}
	return rez;
}

int main()
{
	
	ull A, N;
	fin >> A >> N;
	fout << FastExpo(A, Totien(N) - 1,N) % N;

}