#include <iostream>
#include <fstream>

using namespace std;
uint64_t A, N;
uint64_t getphi(uint64_t n)
{
    uint64_t result = n;
    for(uint64_t i = 2; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            while(n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if(n > 1)
        result -= result/n;
    return result;
}

int main()
{
    ifstream in ("inversmodular.in");
    ofstream out ("inversmodular.out");
    in>>A>>N;
    uint64_t X;
    uint64_t unit = A;
    uint64_t pow = getphi(N) - 1;
    //cout<<pow<<"\n";
    X = 1;

    for(int i = 1; i <= pow; i = (i<<1))
    {
        if(i & pow)
            X = (X * A) % N;
        A = (A * A) % N;
    }
    cout<<X;
    out<<X;
}