#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long ridicare_log(int N,int P,int constanta)
{
    if(P==0) return 1;

    long long rez=ridicare_log(N,P/2,constanta);
    rez=(rez*rez)%constanta;

    if(P%2==1) rez=(rez*N)%constanta;

    return rez;

}
int phi(int N)
{
    int aux=N,sol=N, d=2;
    while(d*d<=aux)
    {
        if(aux%d==0)
        {
            aux=aux/d;
            aux=aux*(d-1);
            while(aux%d==0) aux=aux/d;
        }
        d++;
    }
    if(aux>1)
    {
        sol=sol/aux;
        sol=sol*(aux-1);
    }
    return sol;
}
int main()
{   
	int A,N;
	fin>>A>>N;

	fout<<ridicare_log(A,phi(N)-1,N);

    fin.close();
    fout.close();
	return 0;
}