#include<cstdio>
#include<cmath>

using namespace std;

int a,n,keep;

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    scanf("%d %d",&a,&n);

    keep=n;
    long long int phi=n;
    int lim=sqrt(n);

    for(int i=2;i<=lim;i++)
    {
        if(keep%i==0)
        {
            while(keep%i==0)
            {
                keep/=i;
            }
            phi=(phi/i)*(i-1);
        }
    }
    if(keep!=1)
    {
        phi=(phi/keep)*(keep-1);
    }

    phi--;
    long long int cpow=a;
    long long int res=1;
    for(long long int i=1;i<=phi;i<<=1)
    {
        if(i&phi)
        {
            res*=cpow;
            res%=n;
        }
        cpow*=cpow;
        cpow%=n;
    }
    printf("%lld",res);
}