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

inl Power(inl a,inl b,inl m){
  inl r;
  r=1;
  while(b>0){
    if(b%2==1){
      r*=a;
      r%=m;
      b--;
    }
    a*=a;
    a%=m;
    b/=2;
  }
  return r;
}

inl FormulaFi(inl n){
  inl ans,i;

  ans=n;
  for(i=2;i*i<=n;i++){
    if(n%i==0){
      while(n%i==0){
        n/=i;
        ans=(ans/i)*(i-1);
      }
    }
  }
  if(n!=1){
    ans=(ans/n)*(n-1);
  }
  return ans;
}

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

  fprintf(fout,"%lld",Power(a,FormulaFi(n)-1,n));

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