#include <fstream>

using namespace std;

int LogarithmicExponentiation(int x, int exp, int mod);
int ComputeTotient(int n);

int main()
{
    ifstream fin;
    ofstream fout;
    fout.open("inversmodular.out");
    fin.open("inversmodular.in");

    int a, n;
    fin >> a >> n;

    int totient = ComputeTotient(n);
    fout << LogarithmicExponentiation(a, totient - 1, n);

    fin.close();
    fout.close();
    return 0;
}

int LogarithmicExponentiation(int x, int exp, int mod)
{
	long long result = 1;
	long long a = x;

	for(int i = 0; (1LL << i) <= exp; i++)
	{
		if(exp & (1 << i))
		{
			result = (result * a) % mod;
		}

		a = (a * a) % mod;
	}

	return result;
}

int ComputeTotient(int n)
{
	int result = n;
	for(int i = 2; i*i <= n; i++)
	{
		if(n % i == 0)
		{
			while(n % i == 0)
			{
				n /= i;
			}

			result = (result / i) * (i-1);
		}
	}

	if(n != 1)
	{
		result = result / n * (n - 1);
	}

	return result;
}