#include <fstream>

using namespace std;

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

typedef long long i64;

i64 a, n;

i64 lgput( i64 x, i64 y ) {
    i64 sol= 1;
    for ( ; y>0; y/= 2 ) {
        if ( y%2==1 ) {
            sol= (sol*x)%n;
        }

        x= (x*x)%n;
    }

    return sol;
}

int main(  ) {
    fin>>a>>n;

    i64 phi= n, j= n;
    for ( int i= 2; i*i<=n; ++i ) {
        if ( n%i==0 ) {
            for ( ; j%i==0; j/= i ) ;
            phi= phi/i*(i-1);
        }
    }

    if ( j>1 ) {
        phi= phi/j*(j-1);
    }

    fout<<lgput(a, phi-1)<<"\n";

    return 0;
}