#include <cstdio>
using namespace std;

int get_phi(int n)
{
    double phi=n;
    for(int d=2;d*d<=n;d++)
    {
        if(n%d==0)
        {
            phi*=(double)(d-1)/(double)d;
            while(n%d==0)
                n/=d;
        }
    }
    if(n!=1)
        phi*=(double)(n-1)/(double)n;
    return (int)phi;
}

int n;

long long pow(const int a,int m,const int sp)
{
    if(m==0)
        return 1;
    if(m==1)
        return a%sp;
    if(m%2==1)
        return (a*pow(a,m-1,sp))%sp;
    long long x=pow(a,m/2,sp);
    x=(x*x)%sp;
    return x;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int a;
    scanf("%d%d",&a,&n);

    printf("%lld",pow(a,get_phi(n)-1,n));

    return 0;
}