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