#include<fstream>
using namespace std;
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");

long long a,n,ro,rasp;

long long phi(long long n){
     long long i,sol=n;
     
     for(i=2;i<=n;i++)
       if(n%i==0){
                  while(n%i==0) n/=i;
                  sol=(sol/i)*(i-1);
                 }
     if(n>1) sol=(sol/n)*(n-1);
     
     return sol;
}

long long exponentiere(long long a,long long n){
     long long p=1;
     
     while(n){
              if(n%2) p=(p*a)%ro;
              a=(a*a)%ro;
              n/=2;
             }
     
     return p;
}

int main(){
    fi>>a>>n; ro=n;
    
    rasp=exponentiere(a,phi(n)-1);
    fo<<rasp;
    
    fi.close();
    fo.close();
    return 0;
}