#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;
       }
       i ++;
   }
   if(phi == x)
    phi --;
   return phi;
}
long long lgput(int N, int P,int MOD) {
	// returneaza N^P % 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 >> n >> a;
    long long p = phi(n) - 1;
    out << lgput(a,p,n);
    return 0;
}