#include <cstdio>
using namespace std;
bool ciur[45000];
int prime[45000];
int divs[1000];
long long putere(long long a,int pow,int mod)
{
    long long rez=1;
    while(pow)
    {
        if(pow%2==0)
        {
            pow/=2;
            a*=a;
            a%=mod;
        }
        if(pow%2)
        {
            pow--;
            rez*=a;
            rez%=mod;
        }
    }
    return rez;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int a,n,i,pwr,j,nrp=0,nrd=0,cn;
    long long k;
    scanf("%d%d",&a,&n);
    pwr=n-1;
    cn=n;
    ciur[0]=1;
    ciur[1]=1;
    for(i=2;i*i<=n;i++)
        if(!ciur[i])
            {for(j=2*i;j*j<=n;j+=i)
                ciur[j]=1;
            prime[++nrp]=i;}
    for(i=1;i<=nrp;i++)
        if(n%prime[i]==0)
        {
            divs[++nrd]=prime[i];
            while(n%prime[i]==0)
                n/=prime[i];
        }
    if(n>1)
        divs[++nrd]=n;
    for(i=1;i<=nrd;i++)
            pwr-=(pwr/divs[i]);
    k=a;
    printf("%lld",putere(k,pwr-1,cn));
    return 0;
}