#include<fstream>
#include<cmath>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long n,p;
inline bool prim(int k)
{
    for(int i=2;i<sqrt(k);i++)
        if(k%i==0)return false;
    return true;
}
long long fi(int nr)
{
    int pp=2,eu=n;

    while( nr>1 )
    {
        if(nr%pp == 0)
            eu=eu*(pp-1)/pp;
        while(nr%pp == 0)nr/=pp;
        pp++;
    }

    return eu;
}
inline long long putere(long long s,long long k)
{
    long long sol=1,b=s;
    while(k)
    {   if(k%2==1)
           sol=sol%n*s%n;
        s=s%n*s%n;
        k/=2;
    }
    return sol%n;
}
int main()
{
    long long Euler;
    f>>p>>n;
    if(prim(n)==0)
        Euler=fi(n);
        else Euler=n-1;

    g<<putere(p,Euler-1)<<" ";

    return 0;
}