#include <iostream>
#include <fstream>
#include <cmath>
#define LL long long
using namespace std;
LL M;
int prim(LL x)
{
    int i,rad=sqrt((double)x);
    if(x<2) return 0;
    if(x==2) return 1;
    if(x%2==0) return 0;
    for(i=3;i<=rad;i+=2)
        if(x%rad==0) return 0;
    return 1;
}
LL putere(LL x,LL n)
{
    LL r=1;
    while(n>0)
    {
        if(n & 1)
        {
            n--;
            r=(r%M * x%M)%M;
        }
        x=(x%M * x%M)%M;
        n>>=1;
    }
    return r;
}
LL inversmodular(LL x,LL n)
{
    return putere(x,n);
}
int main()
{
    LL a,n;
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>a>>n;
    M=n;
    if(prim(n))
        g<<inversmodular(a,n-2);
}