#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n,exp;
unsigned long long rasp;
unsigned long long pow(int x,int y);
int euler(int nr);
int main()
{
    fin>>a>>n;
    exp=euler(n)-1;
    rasp=pow(a,exp);
    fout<<rasp%n<<'\n';
    return 0;
}
int euler(int nr)
{
    int p=n-1;
    for(int i=2;i*i<=nr;i++)
        if(!(nr%i))
        {
            p-=(p/i);
            while(!(nr%i))
                nr/=i;
        }
    return p;
}
unsigned long long pow(int x,int y)
{
    if(y==0)
        return 1;
    unsigned long long t=pow(x,y/2)%n;
    if(y%2==0)
        return (t*t)%n;
    else return (((t*t)%n)*x)%n;
}