#include <cstdio>

using namespace std;
int ridput (int x,long long p,int mod){
    int sol=1;
    while (p){
        if (p&1)
            sol=((long long)sol*x)%mod;
        x=((long long)x*x)%mod;
        p/=2;
    }
    return sol;
}
int main()
{
    FILE *fin=fopen ("inversmodular.in","r");
    FILE *fout=fopen ("inversmodular.out","w");
    int a,n,ni;
    long long d,phi;
    fscanf (fin,"%d%d",&a,&n);
    ni=n;
    // det phi(n) in sqrt(n)
    d=2;
    phi=n;
    while (d*d<=n){
        if (n%d==0){
            while (n%d==0)
                n/=d;
            phi=(phi/d)*(d-1);
        }
        d++;
    }
    if (n!=1)
        phi=(phi/n)*(n-1);
    fprintf (fout,"%d",ridput(a,phi-1,ni));
    return 0;
}