#include <fstream>

using namespace std;

ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");

int main()
{
    long long a,n,x,p,rez;
    in >> a >> n;

    x=a;
    p=n-2;

    rez=1;
    while(p)
    {
        if(p%2==1)
            rez=(rez*x)%n;
        x=(x*x)%n;
        p=p/2;
    }

    out << rez;
    return 0;
}