#include <cstdio>
#include <cmath>
using namespace std;
int n;
int mypow(int a, int b){
  int ans = 1;
  for (; b; b >>= 1){
    if (b & 1)
      ans = (1LL * ans * a) % n;
    a = (1LL * a * a) % n;
  }
  return ans;
}
int main(){
  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);
  int a, div, lim, ans, i;
  scanf("%d%d", &a, &n);
  lim = sqrt(n);
  div = 1 + (n != 2);
  for (i = 2; i < lim; i ++)
    if (n % i == 0)
      div += 2;
  if (1LL * lim * lim == n)
    div ++;
  if (div == 2)
    ans = mypow(a, n - 2);
  else
    ans = mypow(a, div - 1);
  printf("%d\n", ans);
  return 0;
}