#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int n,p,aux;
int mod;

void euler(int v)
{
 int d=2;
 aux=v;

 while( d*d<=v )
 {
  if( v%d!=0 ) d++;
  else
  {
   aux/=d;
   aux*=(d-1);
   while( v%d==0 ) v/=d;
   d++;
  }
 }

 if( v!=1 ) aux/=v,aux*=(v-1);
}

int putere(int a,int b)
{

 int sol=1,put=a;

 while( b>0 )
 {
  if( b%2==1 ) sol= (1LL*sol*put)%mod;

  put=(1LL*put*put)%mod;
  b/=2;
 }

 return sol;
}

int main()
{
 f>>n>>p;
 mod=p;

 euler(p);

 g<<putere(n,aux-1);
}