#include <algorithm>
#include <fstream>

using namespace std;

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

int A, N;

int Phi( int x ) {

    bool ok;
    int i, aux;

    ok = false;
    aux = N;

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

            aux = aux / i * (i - 1);
            ok = true;
        }

    if( ok == false )
        aux = aux / N * (N - 1);

    return aux;
}

int Pow( int x, int p ) {

    int i, aux, xxx;

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

        if( (1 << i) & x )
            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;
}