#include <fstream>
using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int a,n;

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

int put(int a,int b)
{
    if (b==0)
        return 1;
    if (b==1)
        return a;
    if (b%2==0)
        return put((1LL * a * a)%n,b/2);
    return (1LL * put((1LL * a * a)%n,b/2) * a)%n;

}
int main()
{
    f>>a>>n;
    int exp = getphi(n);

    g<<put(a,exp-1);
    return 0;
}