#include <iostream>
#include<fstream>
using namespace std;
long long s;
long long power (long long x, long long n )
{
    if(n==0) return 1;
    if(n==1)return x%s;
    if(n%2==0) return power((x*x)%s,n/2)%s;
     else return (x*power((x*x)%s,(n-1)/2))%s;
}

/*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 f("inversmodular.in");
    ofstream g("inversmodular.out");
    long long x, n;

     f>>x>>n;
     s=n;
     g<<power(x,n-2);
    return 0;
}