#include <iostream>
#include <fstream>

using namespace std;
typedef long long ll;

int a,n,fi,na;
int pw(int nr,int exp){
  if(exp==1)return nr;
  else {
    ll aux;
    if(exp%2){
      aux=pw(nr,exp-1);
      aux=aux*(ll)nr;
      return aux%n;
    } else {
      aux=pw(nr,exp/2);
      aux=aux*aux;
      return aux%n;
    }
  }
}

int main()
{
    ifstream f ("inversmodular.in");
    ofstream g ("inversmodular.out");
    f>>a>>n;
    na=fi=n;
    for(int i=2;i*i<=na;i++)
      if(na%i==0){
        fi=(fi/i)*(i-1);
        while(na%i==0)na/=i;
      }
    if(na!=1)fi=(fi/na)*(na-1);
    g<<pw(a,fi-1);
    f.close ();
    g.close ();
    return 0;
}