#include <fstream>

using namespace std;

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

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

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

    fout << LogarithmicExponentiation(a, n - 2, 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;
}