#include <fstream>
using namespace std;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

int phi(int x){
  int euler=x,d=2;
  while(d*d<=x){
    if(x%d==0){
      euler=euler/d*(d-1);
      while(x%d==0){
        x/=d;
      }
    }
    d++;
  }

  if(x>1){
    euler=euler/x*(x-1);
  }
  return euler;
}

long long modPow(long long a,int exp,int mod){
  long long res=1;
  while(exp){
    if(exp&1){
      res=(res*a)%mod;
    }
    a=(a*a)%mod;
    exp/=2;
  }
  return res;
}

int main(){
  int a,n;

  cin>>a>>n;
  cout<<modPow(a,phi(n)-1,n);

  return 0;
}