#include <bits/stdc++.h>
#define int long long int
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

void compute( int valx, int valy,int  swapped, int n)
{
    int valr=0;
    int valc;
    pair<int,int>x={1,0};
    pair<int,int> y={0,1};
    pair< int,int >r;
    while( valy)
    {
        valr=valx%valy;
        valc=valx/valy;
        ///x= y*c+r
        ///r= y*c-x;
        r={  x.first-y.first*valc,x.second- y.second*valc };
        valx=valy;
        valy=valr;
        x=y;
        y=r;
        
    }
    fout<< (x.second %n+ n)%n;
}
int32_t main()
{
    int a,n;
    int swapped=0;
 // a*x =1 mod n

  //a*x -ny=1
    fin>>a>>n;
    int valx,valy;
    if(a<n)
    {
     swapped=1;
     valx=n;
     valy=a;
    }
    else
    {
        valx=a;
        valy=n;
    }
    compute(valx,valy,swapped,n);

}