#include <fstream>

using namespace std;
int n,k,i,p;
long long x,y;
long long r=1;
void invers(long long &x,long long &y,int a,int b)
{
    if (!b)
    {
        x=1;
        y=0;
    }
    else
    {
        long long x0,y0;
        invers(x0,y0,b,a%b);
        x=y0;
        y=x0-(a/b)*y0;
    }
}
int main()
{
    ifstream fin ("inversmodular.in");
    ofstream fout ("inversmodular.out");
    fin>>n>>p;
    /*if (k<n-k)
    {
        for (i=n-k+1;i<=n;i++)
            r=(r*i)%p;
        for (i=2;i<=k;i++)
        {
            invers(x,y,i,p);
            if (x<0) x=i+x%i;
            r=(r*x)%p;
        }
    }
    fout<<r;*/
    invers(x,y,n,p);
    if (x<0) x=n+x%n;
    fout<<x;
    return 0;
}