#include<fstream>
#define ll long long
using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a, n;

ll phi(ll x)
{ll result=x;

for(ll i=2; i*i<=x; i++)
   if(!x%i)
     {while(!x%i) 
           x/=i;
      result=(result/i)*(i-1);;
     }

return (x>1) ? (result/x*(x-1)):(result);
}

ll putere(ll a, ll n, ll mod)
{if(n==1) 
   return a;

if(n%2==0)
  return (putere(a, n/2, mod)*putere(a, n/2, mod))%mod;
else return (putere(a, n-1, mod)*a)%mod;
}

int main()
{f>>a>>n;
g<<putere(a, phi(n)-1, n);
return 0;
}