#include<fstream>
using namespace std;

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

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

    long long A, N;
    in >> A >> N;
    long long phi = getphi(A, 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;
}