#include <iostream>
#include <fstream>
using namespace std;
int mod;
long long modulo(long long a,long long b){
   if(b==0){
    return 1;
   }
    long long x=modulo(a,b/2);
      x=x*x%mod;
      if(b%2==1){
        x=x*a%mod;
      }
   return x;
}
int main()
{
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    int a,b;
    cin>>a>>b;
    mod=b;
    double x=b;
    int p=2;
    while(b>1 && p*p<=x){
        if(b%p==0){
            double f=1.00*(p-1)/p;
            x=x*f;
            while(b%p==0){
                b/=p;
            }
        }
        p++;
    }
    if(b>1){
        double f=1.00*(b-1)/b;
        x=x*f;
    }
    cout<<modulo(a,x-1);
    return 0;
}