#include <cstdio>

using namespace std;

FILE *f = fopen ( "inversmodular.in" , "r" ) , *g = fopen ( "inversmodular.out" , "w" );

long long A , N;

long long toPower ( long long x , long long exp )
{
    long long result = 1;
    while ( exp )
    {
        if ( exp % 2 == 1 )
        {
            exp --;
            result = ( result * x ) % N;
        }
        x = ( x * x ) % N;
        exp /= 2;
    }
    return result;
}

long long phi ( long long x )
{
    long long phin = x , i;
    for ( i = 2 ; i * i <= x ; i ++ )
    {
        if ( x % i == 0 )
        {
            while ( x % i == 0 )
                x /= i;
            phin = ( phin / i ) * ( i - 1 );
        }
    }
    if ( x != 1 )
        phin = ( phin / x ) * ( x - 1 );
    return phin;
}

int main()
{
    //read
    fscanf ( f , "%lld %lld" , &A , &N );

    //compute A ^ ( N - 2 )
    fprintf ( g , "%lld\n" , toPower ( A , phi( N ) - 1 ) );

    return 0;
}