#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int a,n;
int Phi(int n)
{
    int r=n;
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            r-=r/i;
        }
    }
    if(n>1)
        r-=r/n;
    return r;
}
int putere(int a,int b)
{
    if(b==1)
        return a%n;
    int r=putere(a,b/2);
    if(b%2==1)
        return r*r%n*a%n;
    return r*r%n;
}
int main()
{
    in>>a>>n;
    int u=Phi(n);
    --u;
    out<<putere(a,u);
    return 0;
}