#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long ind(long long nr)
{
    long long baza=2,rez=nr;
    while(baza*baza<=nr)
    {
        if(nr%baza==0)
        {
            rez/=baza;
            rez*=(baza-1);
            while(!(nr%baza))
                nr/=baza;
        }
        baza++;
    }
    if(nr>1)
    {
        rez*=nr-1;
        rez/=nr;
    }
    return rez;
}
long long put(long long b,long long e,long long mod)
{
    long long r=1;
    while(e>0)
    {
        if(e%2==0)
        {
            b*=b;
            b%=mod;
            e/=2;
        }
        else
        {
            r*=b;
            r%=mod;
            e--;
        }
    }
    return r%mod;
}
int main()
{
    long long a,m;
    cin>>a>>m;
    long long i=ind(m);
    i%=m;
    cout<<put(a,i-1,m);
    return 0;
}