#include <cstdio>
#include <cmath>
using namespace std;
long long numprimes(long long n)
{
    long long lim=(long long)sqrt((double)n);
    long long ans=n;
    for(long long i=2; i<=lim; ++i)
    {
        bool ok=false;
        while(n%i==0)
        {
            n/=i;
            ok=true;
        }
        if(ok)
        {
            ans/=i;
            ans*=(i-1);
            lim=(long long)sqrt((double)n);
        }
    }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}
long long lgput (long long a,long long b,long long mod)
{
    if(b==0)
        return 1;
    else
    {
        long long c= lgput(a,b/2,mod);
        if(b&1)
            return c*c%mod*a%mod;
        else
            return c*c%mod;
    }
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long a,n;
    scanf("%lld%lld",&a,&n);
    printf("%d\n",lgput(a,numprimes(n)-1,n)%n);
    return 0;
}