#include <iostream>
#include <fstream>

using namespace std;

long phi(long x)
{
    long n=x;
    for(long i=2;i*i<=x;i++)
    {
        if(!(x%i))
        {
            while(!(x%i))
                x/=i;
            n=(n/i)*(i-1);
        }
    }
    if(x!=1)
        n=n/x*(x-1);
    return n;
}

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

    long A,N;

    f>>A>>N;
    long pwr=phi(N)-1;
    long ans=1;

    for(long i=1;i<=pwr;i++)
    {
        ans*= A;
    }

    o<<(ans%N);

    f.close();
    o.close();

    return 0;
}