#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;
    int n2=n,x2=x;
    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;
    }
    for(i=2;i<=S-1;i++)
        x=(x*(x2%n2))%n2;
    cout<<x;
    return 0;
}