#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int lgput(int a,int b)
{
    if(b==0)
        return 1;
    if(b==1)
        return a;
    if(b%2==0)
        return lgput(a*a,b/2);
    return lgput(a*a,b/2)*a;
}
int cn;
int lgputmod(int a,int b)
{
    if(b==0)
        return 1;
    if(b==1)
        return a%cn;
    if(b%2==0)
        return lgput(a*a%cn,b/2)%cn;
    return a*lgput(a*a%cn,b/2)%cn;

}
int main()
{
    int k,a,n,i,j,d,q,s=1;
    f>>a>>n;
    cn=n;
    k=0;
    while(n%2==0)
    {
        k+=1;
        n/=2;
    }
    if(k>=1)
        s*=(lgput(2,k-1));
    d=3;
    while(d*d<=n)
    {
        k=0;
        while(n%d==0)
        {
            n/=d;
            k+=1;
        }
        if(k>=1)
        {
            s*=(d-1)*lgput(d,k-1);
        }
        d+=2;
    }
    if(n!=1)
    {
        s*=(n-1);
    }
    g<<lgputmod(a,s-1);
    return 0;
}