#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int main()
{
    int N,A,f,i,r,n;
    long long p;
    fin>>A;
    fin>>N;
    n=N;
    f=0;
    p=1;
    i=2;
    f=N;
    while(i*i<=N)
    {
        if(N%i==0)
        {
            f=f/i*(i-1);
            while(N%i==0);
            {
                N=N/i;
            }
        }
        i++;
    }
    if(N!=1) f=f/N*(N-1);

    f=f-1;
    while(f!=0)
    {
        if(f%2!=0)
        {
            p=(p*A)%n;
        }
        A=(A*A)%n;
        f=f/2;
    }

    fout<<p;
    return 0;
}