#include <cstdio>
int mod;
inline int phi(int n)
{
    int nr=n;
    for(int i=2;i*i<=n;i++)
        if(!(n%i))
        {
            while(!(n%i))
                n/=i;
            nr=nr/i*(i-1);
        }
    if(n>1)
        nr=nr/n*(n-1);
    return nr;
}
inline int lgput(long long a,int n)
{
    int ans=1;
    while(n)
    {
        if(n&1)
            ans=((long long)ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("inversmodular.in","r");
    fout=fopen("inversmodular.out","w");
    int n;
    long long a;
    fscanf(fin,"%lld%d",&a,&n);
    mod=n;
    fprintf(fout,"%d",lgput(a,phi(n)-1));
    fclose(fin);
    fclose(fout);
    return 0;
}