#include <fstream>
using namespace std;
ifstream f ( "inversmodular.in" );
ofstream g ( "inversmodular.out" );
#define ll long long
ll A, N;

ll EXP ( int  POWER )
{
    if ( POWER == 1 ) return A;

    return POWER % 2 ? ( A * ( EXP ( POWER / 2 ) * EXP ( POWER / 2 ) ) % N ) % N : ( EXP ( POWER / 2 ) * EXP ( POWER / 2 ) ) % N;
}
int phi ( int value )
{
    int i, result = value;

    for ( i = 2; i*i <= value; ++i ) if ( value % i == 0 )
        {
            for ( ; value % i == 0; value /= i );

            result = result - result / i;
        }

    if ( value != 1 )
        result = result - result / value;

    return result;
}
int main()
{
    f >> A >> N;
    g << EXP ( phi ( N ) - 1 ) << '\n';


    f.close();
    g.close();
    return 0;
}