#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

typedef unsigned long long ull;
ull A,N,MOD;

ull lgput(ull a, ull b)
{
    if(b==0) return 1;
    if(b==0) return 1;
    if(b==1) return a;
    ull aux=lgput(a,b/2);
    if(b&1) return ((((aux*aux)%MOD)*a)%MOD);
    return (aux*aux)%MOD;
}

int main()
{
    fin>>A>>N;
    MOD=N;
    fout<<lgput(A,MOD-2);
    return 0;
}