#include <cstdio>
#include <cmath>
int n,a,MOD;
int phi(int a)
{
    int res=a,lun=sqrt(a);
    if(a%2==0)
    {
        res/=2;
        while(a%2==0) a/=2;
    }
    for(int j=3;j<=lun;j+=2)
    {
        if(a%j==0)
        {
            res/=j;
            res*=(j-1);
            while(a%j==0) a/=j;
        }
    }
    if(a!=1)
    {
        res/=a;
        res*=(a-1);
    }
    return res;
}
long long putere(long long a,long long b)
{
    long long res=1,num=a;
    for(;b!=0;b>>=1)
    {
        if((b&1)==1)
        {
            res*=num;
            res%=MOD;
        }
        num*=num;
        num%=MOD;
    }
    return res;
}
int main()
{
    freopen ("inversmodular.in","r",stdin);
    freopen ("inversmodular.out","w",stdout);
    int a,n;
    scanf("%d%d",&a,&n);
    MOD=n;
    printf("%lld\n",putere(a,phi(n)-1));
}