#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a,n;
int MOD;


unsigned long long put(unsigned long long a, unsigned long long b)
{
    if(b==0) return 1;
    if(b==1) return a;
    unsigned long long aux=put(a,b/2);
    if(b&1) return ((aux*aux)%MOD*a)%MOD;
    else return(aux*aux)%MOD;
}

int main()
{

    f>>a>>n;
    MOD=n;
    g<<put(a,n-2)<<'\n';
    f.close();
    g.close();
    return 0;
}