#include <iostream>
#include<fstream>
using namespace std;
int s;
long long power (long long x, int 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 x%s*power((x*x)%s,(n-1)/2)%s;
}
int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    int x, n;

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