#include <cstdio>

using namespace std;
int a,n,m;
FILE *in=fopen ("inversmodular.in","r");
FILE *out=fopen ("inversmodular.out","w");
long long power (long long a, int n)
{
    if (n==0) return 1;
    if (n==1) return a%m;
    if (n%2==0) return power ((a*a)%m,n/2)%m;
    return (a*power ((a*a)%m,(n-1)/2))%m;
}
long long phi (long long n)
{
    long long p=n;
    for (long long d=2;d*d<=n;d++)
    {
        if (n%d==0)
        p=p*(d-1)/d;
        while (n%d==0) n/=d;
    }
    if (n!=1) p=p*(n-1)/n;
    return p;
}
int main()
{
    fscanf (in,"%d%d",&a,&n);
    m=n;
    fprintf(out,"%lld",power (a,phi(n)-1));
    return 0;
}