#include <iostream>
#include<fstream>
using namespace std;
long long 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<<x<<n;
     g<<power(x,n-2)%s;
    return 0;
}