#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long A,N;

long long putere(long long n, long long p)
{
if(p == 0) return 1;
else if(p==1) return n;
else if(p==2) return (n * n)%N;
else if(p & 1) return (n * putere(putere(n,p/2),2)%N)%N;
else return putere(putere(n,p/2),2)%N;
}
long long fi(long long n)
{
int i;
long long prod = n;
for(i=2;i<=sqrt(n);i++) if(!(n%i)) {while(!(n%i)) n/=i; prod = (prod/i) * (i-1);}
if(prod==n) return prod-1;
else return prod;
}

int main()
{

f >> A >> N;


g << putere(A,fi(N)-1);


    return 0;
}