#include <fstream>

using namespace std;

typedef long long i64;

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

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

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

    i64 sol= 1;
    for ( --phi; phi>0; phi/= 2 ) {
        if ( phi%2==1 ) {
            sol= (sol*a)%n;
        }
        a= a*a%n;
    }
    fout<<sol<<"\n";

    return 0;
}