#include <fstream>

using namespace std;

long long N,M;

long long euler(long long n)
{
	long long cn = n;
	long long i;
	for(i = 2;i * i <= n; ++i)
	{
		if (n % i == 0)
		{
			while(n % i == 0)n /= i;
			cn = (cn / i) * (i - 1);
		}
	}
        if (n != 1) cn= cn/ n * (n - 1);
	return cn;
}
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int main()
{long long A,N;
   fin>>A>>N;
       long long exp = euler(N) - 1;
	long long  nr = A;
	long long putere = 1;
    for(long long p = 1;p <= exp;p <<= 1)
    {
	 	if (p & exp) putere= (putere * nr) % N;
	  	nr = (nr * nr) % N;
	}
	fout<<putere;
	return 0;

    return 0;
}