#include<fstream>
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int F(int n);
int Putere( int a, int b );

int main()
{
    int a, n;
    fin >> a >> n;
    
    fout << Putere(a, F(n)-1 )%n;
    //fout << ' ' << F(n);
    
    fin.close();
    fout.close();
    
    return 0;
}

int F( int n )
{ 
    int n1 = n;
    for( int i = 2; i*i <= n; ++i )
    {
         if( n % i == 0 )
             n1 = n1 / i * ( i - 1 );
             
         while( n % i == 0 )
                n /= i;       
    }
    
    if( n != 1 ) 
        n1 = n1 / n * ( n-1);
    
    return n1;
}

int Putere( int a, int b )
{
    if( b == 0 )
        return 1;
    
    if( b % 2 == 0 )
        return Putere( (a*a), b/2 );
    else
        return a*Putere( a*a, b/2 );
}