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

int Inv1(int a,int b,int mod){
  int ans;

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

  return ans;
}

int Euler(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,m;
  FILE *fin,*fout;
  fin=fopen("inversmodular.in","r");
  fout=fopen("inversmodular.out","w");
  fscanf(fin,"%lld%lld",&a,&m);

  fprintf(fout,"%lld",Inv1(a,Euler(m)-1,m));

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