#include <fstream>
using namespace std;

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

long long phi(int x)
{
   int phi = x;

   for(int i = 2;i * i <= x;i ++)
   {
       if(x % i == 0)
       {
           phi = phi / i * (i - 1);
           while(x % i == 0)
            x = x / i;
       }
   }
   if(x > 1)
    phi = phi / x * (x - 1);
   return phi;
}
long long lgput(int N, int P,int MOD) {

	if (P == 0)
		return 1;
	int a = lgput(N, P/2,MOD);
	int res = 1LL * a * a % MOD;
	if (P%2 == 1)
		res = 1LL * res * N % MOD;
	return res;
}

int main()
{
    long long  n, a;
    in >> a >> n;
    long long p = phi(n) - 1;
    out << lgput(a,p,n);
    return 0;
}