#include <fstream>

using namespace std;

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

int N;

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

long long powlog ( int b, long long p ) {
    long long nr = b;
    long long pow = 1;
    for ( long long i = 1 ; i <= p ; p /= 2 ) {
        if ( i & p )
            pow = ( pow * nr ) % N;
        nr = ( nr * nr ) % N;
    }
    return pow;
}

int main()
{
    int a;
    fin >> a >> N;
    fout << powlog ( a, phi ( N ) - 1 );
    return 0;
}