#include<stdio.h>
#define ll long long
using namespace std;

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)%mod)*(putere(a, n/2, mod))%mod)%mod;
else return (((putere(a, n/2, mod)%mod)*(putere(a, n/2, mod))%mod)*(a%mod))%mod;
}

int main()
{freopen("inversmodular.in", "r", stdin);
freopen("inversmodular.out", "w", stdout);
scanf("%lld %lld", &a, &n);
	
printf("%lld\n", putere(a, phi(n)-1, n));
return 0;
}