#include<cstdio>
using namespace std;

long long n;

long long phi (long long x)
{
    long long i,rez=x;
    for (i=2; i*i<=x; i++)
        if (x%i==0)
        {
            while (x%i==0) x/=i;
            rez=(rez/i)*(i-1);;
        }
    if (x>1)
        rez=(rez/x)*(x-1);
    return rez;
}

long long pow (long long a, long long b)
{
    if (b==0)
        return 1;
    if (b==1)
        return a;
    if (b%2) return (a*pow(a,b-1))%n;
    long long y=pow(a,b/2);
    return (y*y)%n;
}

int main ()
{
    long long put,a;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld %lld",&a,&n);
    put=phi(n)-1;
    printf("%lld\n",pow(a,put));
    return 0;
}