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

long long a,n,b,r,ind;

int main()
{
    int i,aux,p;
    in>>a>>n;
    a=a%n;
    ind=n;
    aux=n;
    if(aux%2==0)
    {
        ind=ind/2;
        while(aux%2==0)
            aux/=2;
    }
    for(i=3;i*i<=aux;i+=2)
    {
        p=0;
        while(aux%i==0)
        {
            p++;
            aux/=i;
        }
        if(p)
            ind=ind/i*(i-1);
    }
    if(aux>1)
        ind=ind/aux*(aux-1);
    r=1;
    b=ind-1;
    while(b)
    {
        if(b%2==1)
            r=(r*a)%n;
        a=(a*a)%n;
        b/=2;
    }
    out<<r;
    return 0;
}