#include<fstream>
#include<math.h>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long int n,i,S,s,x;
int main()
{
    i=3;
    cin>>x>>n;
    S=n;
    while(n%2==0)
            n/=2;
    if(S!=n) S/=2;
    while(n>1)
    {
        s=0;
        if(n%i==0)
        {
        s=1;
        while(n%i==0)
            n/=i;
        }
        if(s==1) S=S/i*(i-1);
        i+=2;
        if(i*i>n) i=n;
    }
    cout<<pow(x,S-1);
    return 0;
}