#include <fstream>
///INVERS MODULAR INFO ARENA  100p cu functia lui Euler si exponentiere rapida
using namespace std;


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;
}

long long exp_rapida(long long a,long long b,long long M){
    long long  nr = a;
	long long putere = 1;
    for(long long p = 1;p <= b;p <<= 1)
    {
	 	if (p & b) putere= (putere * nr) % M;
	  	nr = (nr * nr) % M;
	}
	return putere;
}

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int main()
{long long A,N;
   fin>>A>>N;
       long long exp = euler(N) - 1;

	fout<<exp_rapida(A,exp,N);
    return 0;
}