#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int phi(int n)
{
    int nr=n,i;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
    {
        while(n%i==0)
            n/=i;
        nr=nr/i*(i-1);
    }
    if(n!=1)
        nr=nr/n*(n-1);
    return nr;

}
int main()
{   int a,n,p,sol,i;
    f>>a>>n;
    p=phi(n)-1;
    if(p%2)
    {
        sol=a;
        for(i=1;i<=(p-1)/2;i++)
            sol*=(a*a)%n;
        g<<sol%n;
    }
    else
    {sol=1;
        for(i=1;i<=(p-1)/2;i++)
            sol*=(a*a)%n;
    g<<sol%n;
    }

    return 0;
}