#include<cstdio>
int a,N;
int phi(int n)
{
    int prod=n;
    for(int i=2;(long long)i*i<=n;++i)
        if(n%i==0)
        {
            prod*=(i-1);
            prod/=i;
            while(n%i==0)
                n/=i;
        }
    if(n!=1)
    {
        prod*=(n-1);
        prod/=n;
    }
    return prod;
}
int putlog(int n,int p)
{
    int pp,a;
    pp=1;
    a=n;
    while(p)
    {
        if(p&1)//n%2==1
        {
            pp*=a;
            pp%=N;
        }
        a*=a;
        a%=N;
        p>>=1;
    }
    return pp;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&a,&N);
    printf("%d",putlog(a,phi(N)-1));
    return 0;
}