#include <fstream>

using namespace std ;

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

long long a , n , rasp , modulo ;

long long getphi ( long long nr ) //n*(1-1/p1)(1-1/p2)...(1-1/pn) = n*((p1-1)/p1)*((p2-1)/p2)*...((pn-1)/pn)
{
    long long cur = nr ;
    for ( long long i = 2 ; i * i <= nr ; ++i )
        if  ( nr % i == 0 )
            {
             while ( nr % i == 0 )
                nr /= i ;
             cur = ( cur / i ) * ( i - 1 );
            }
    if ( nr != 1 )
        cur = cur / nr * (nr - 1);
    return cur ;
}
long long ridica_la_putere ( long long a , long long n )
{
 if ( n == 0 )
    return 1 ;
 if ( n == 1 )
    return a ;
 if ( n % 2 == 1 )
    {
     long long tmp = a * ( ridica_la_putere ( a , n - 1 ) ) ;
     return tmp % modulo ;
    }
 else
    {
     long long tmp = ridica_la_putere ( a , n / 2 ) ;
     return ( tmp * tmp ) % modulo ;
    }
}

int main ()
{
 f >> a >> n ;
 modulo = n ;
 long long phi = getphi ( n ) ;
 rasp = ridica_la_putere ( a , phi - 1 ) ;
 g << rasp ;
}