#include <stdio.h>
#include <stdlib.h>

int cmmdc(int a, int b){
  int r;
  while(b!=0){
    r=a%b;
    a=b;
    b=r;
  }
  return a;
}

int ridicare(long long b, int p, long long n){
  long long rez=1;
  while(p>0){
    if(p%2==0){
      b=(b*b)%n;
      p/=2;
    }else{
      rez=(rez*b)%n;
      p--;
    }
  }
  return rez;
}

int main()
{
    FILE *fin, *fout;
    int n,k,e,i;
    fin=fopen("inversmodular.in","r");
    fout=fopen("inversmodular.out","w");
    fscanf(fin,"%d%d",&k,&n);
    /*
    e=0;
    for(i=1;i<n;i++){
      if(cmmdc(i,n)==1)
        e++;
    }
    */e=n-1;
    k=ridicare(k,e-1,n);
    k=(k-1)%n+1;
    fprintf(fout,"%d",k);
    fclose(fin);
    fclose(fout);
    return 0;
}