#include<cstdio>
using namespace std;

long long n;

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

long long putere (long long x, long long exp)
{
    long long y;
    if (exp==0) return 1;
    if (exp==1) return x;
    if (exp%2)
        return (x*putere(x,exp-1))%n;
    y=putere(x,exp/2);
    return (y*y)%n;
}

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