#include <iostream>
#include <stdio.h>
#define int long long
using namespace std;

int InvMod1(int a,int put,int mod){
  int ans;

  ans=1;
  while(put>0){
    if(put%2==1){
      ans*=a;
      ans%=mod;
    }
    a*=a;
    a%=mod;
    put/=2;
  }

  return ans;
}

int FI(int n){
  int d,ans;

  d=2;
  ans=n;
  while(d*d<=n){
    if(n%d==0){
      while(n%d==0){
        n/=d;
      }
      ans=(ans/d)*(d-1);
    }
    d++;
  }
  if(n>1){
    ans=(ans/n)*(n-1);
  }

  return ans;
}

void CMMDC(int a,int b,int &x,int &y){
  if(b==0){
    x=1;
    y=0;
  }else{
    CMMDC(b,a%b,x,y);
    int aux;
    aux=x;
    x=y;
    y=aux-y*(a/b);
  }
}

int InvMod2(int a,int n){
  int x,y;

  x=y=0;
  CMMDC(a,n,x,y);

  if(x<0){
    x=n+x%n;
  }

  return x;
}

signed main(){
  int a,n;
  FILE *fin,*fout;
  fin=fopen("inversmodular.in","r");
  fout=fopen("inversmodular.out","w");
  fscanf(fin,"%lld%lld",&a,&n);

  //fprintf(fout,"%lld",InvMod1(a,FI(n)-1,n));
  fprintf(fout,"%lld",InvMod2(a,n));

  fclose(fin);
  fclose(fout);
  return 0;
}