#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long n,k;
long long phi(long long k)
{
    long long pr=k,p=0;
    long long d=2;
    while(d*d<=k)
    {
        p=0;
        while(k%d==0) {p++;k/=d;}
        if(p!=0) {pr=pr/d*(d-1);}
        d++;
    }
    if(k>1) pr=pr/k*(k-1);
    return pr;
}
long long put(long long n,long long b)
{
    long long p=1;
    while(b!=0)
    {
        if(b%2==1) p=p*n%k;
        b/=2;
        n=n*n%k;
    }
    return p;
}
long long inv(long long n,long long k)
{
    return put(n,phi(k)-1);
}
int main()
{
    cin>>n>>k;
    cout<<inv(n,k);
    return 0;
}