#include <fstream>

using namespace std;

long long k;

long long power(long long x, int n)
{
    if(n==0)
        return 1;
    if(n==1)
        return x%k;
    if(n%2==0)
        return power((x*x)%k,n/2)%k;
    else
        return (x*power((x*x)%k,(n-1)/2))%k;
}

int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");

    long long a, n;
    in >> a >> n;
    in.close();

    k = n;
    out << power(a,n-2);
    out.close();

    return 0;
}