#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long k,i,m,x,j,ct,phi;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&x,&m);
    for(k=2;k<=sqrt(m);k++)
    {
        if(m%k==0)
            ct+=2;
        if(k==sqrt(m)&&m%k==0)
            ct--;
    }
    if(ct==0)
        phi=m-1;
    else
        phi=m-ct;
    for(k=phi-1,j=1,i=x;k!=1;)
    {
        if(k%2==0)
        {
            k/=2;
            i*=i;
        }
        else
        {
            k--;
            j*=i;
        }
    }
    printf("%lld\n",j*i%m);
    return 0;
}