#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long a,n,f=1,i,d,x,v,p;
int main()
{
    fin>>a>>n;
    d=2;
    x=n;
    f=n;
    v=0;
    if(x%2==0)
    {
        f=f*(d-1)/d;

    while(x%2==0)
    {
        x/=2;
        v=1;
    }}
    for(i=3; i*i<=x && x>1; i++)
    {
        if(x%i==0)
        {
            f=f*(i-1)/i;
            while(x%i==0)
            {
                x/=i;
                v=1;
            }
        }
    }
    if(x>1)
        f=f*(x-1)/x;
    f--;
    p=1;
    while(f>0)
    {
        if(f%2==1)
        {
            f--;
            p=(p*a)%n;
        }

            a=(a*a)%n;
            f/=2;
        }

    fout<<p;
    return 0;
}