#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;
}

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));

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