#include<fstream>
using namespace std;

long long getphi(int nr)
{
    long long cur = nr;
    for( long long i = 2; i*i <= nr; i++ )
    {
        if( nr % i == 0 )
        {
            while( nr % i == 0 )
                nr /= i;
            cur = (cur/i)*(i-1);
        }
    }
    if( nr != 1 )
        cur = cur/nr*(nr-1);
    return cur;
}

int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");

    long long A, N;
    in >> A >> N;
    long long phi = getphi(N) - 1, p = A, nr = 1;

    for( long long i = 0; (1<<i) <= phi; i++ )
    {
        if( (phi & (1<<i)) )
            nr = (nr * p)%N;
        p = (p * p)%N;
    }
    out<<nr;
    return 0;
}