#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
long long a,n;
long long Phi(long long n)
{
    long long r=n;
    for(long long i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            r=r-r/i;
        }
    }
    if(n>1)
    	r=r-r/n;
    return r;
}
long long putere(long long a,long long b)
{
    if(b==1)
        return a%n;
    long long r=putere(a,b/2);
    if(b%2==1)
        return r*r%n*a%n;
    return r*r%n;
}
int main()
{
    in>>a>>n;
    long long u=Phi(n);
    --u;
    out<<putere(a,u);
    return 0;
}