#include <fstream>

using namespace std;

int a,n;

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

void cmmdc(int a,int b,long long *x,long long *y){
     long long x0,y0;
     if (b==0) *x=1,*y=0;
     else
      {
       cmmdc(b,a%b,&x0,&y0);
       *x = y0;
       *y = x0 - (a / b) * y0;
      }
}
int main(){
    long long x,y;
    fin>>a>>n;
    cmmdc(a,n,&x,&y);
    fout<<((x%n)+n)%n;
    return 0;
}