#include <iostream>
#include<cstdio>
using namespace std;
long long a,n,e,i,m,x;
int main()
{
   freopen("inversmodular.in","r",stdin);
   freopen("inversmodular.out","w",stdout);
   cin>>a>>n;
   e=1;m=n;
   for(i=2;i*i<=n;i++)
   if(n%i==0)
   {
       while(n%i==0)
       {
           n/=i;
           e*=i;
       }
       e/=i;e*=i-1;
   }
   if(n>1) e*=n-1;
   e--;
   x=1;
   while(e)
   {
       if(e%2)
       x=(x*a)%m;
       a=(a*a)%m;
       e/=2;
   }
   cout<<x;
    return 0;
}