#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
typedef unsigned long long ull;
ull lgput(ull a,ull 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;
}
ull cn;
ull lgputmod(ull a,ull b)
{
    if(b==1)
        return a%cn;
    if(b%2==0)
        return lgput(a%cn*a%cn,b/2)%cn;
    return a%cn*lgput(a%cn*a%cn,b/2)%cn;

}
int main()
{
    ull 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);
    }
    s--;
    ull putere=1;
    while(s)
    {
        if(s%2==1)
        {
            putere*=a%cn;
            putere%=cn;
        }
        a=a%cn*a%cn;
        s/=2;
    }
    g<<putere;
    return 0;
}