#include <algorithm>
#include <fstream>

using namespace std;

const char Input[] = "inversmodular.in";
const char Output[] = "inversmodular.out";

long long int A, N;

long long int Phi( long long int x ) {

    long long int i, aux0, aux1;

    aux0 = aux1 = N;
    for( i = 2; i * i <= N; ++i )
        if( aux1 % i == 0 ) {

            aux0 = aux0 / i * (i - 1);
            while( aux1 % i == 0 )
                aux1 /= i;
        }

    if( aux1 > 1 )
        aux0 = aux0 / N * (N - 1);

    return aux0;
}

long long int Pow( long long int x, long long int p ) {

    long long int i, aux, xxx;

    aux = x;
    xxx = 1;
    for( i = 0; (1LL << i) <= p; ++i ) {

        if( (1LL << i) & p )
            xxx = (xxx * aux) % N;
        aux = (aux * aux) % N;
    }

    return xxx;
}

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    fin >> A >> N;
    fout << Pow( A, Phi( N ) - 1 );

    fin.close();
    fout.close();

    return 0;
}