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

int n;

int F(int q);
int Putere( int a, int b );
 
int main()
{
    int a;
    fin >> a >> n;
     
    fout << Putere(a, F(n)-1 )%n;
    //fout << ' ' << F(n);
     
    fin.close();
    fout.close();
     
    return 0;
}
 
int F( int q )
{
    int n1 = q;
    for( int i = 2; i*i <= q; ++i )
    {
         if( q % i == 0 )
             n1 = n1 / i * ( i - 1 );
              
         while( q % i == 0 )
                q /= i;      
    }
     
    if( q != 1 )
        n1 = n1 / q * ( q-1);
     
    return n1;
}
 
int Putere( int a, int b )
{
    if( b == 0 )
        return 1;
     
    if( b % 2 == 0 )
        return (long long) Putere( (a*a)%n, b/2 )%n;
    else
        return (long long) (a*Putere( (a*a)%n, b/2 ))%n;
}