#include <cstdio>
int a, n;

int phi(int n) {
  int res = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      res = res / i * (i - 1);
    }
  if (n != 1) {
    res = res / n * (n - 1);
  }
  
  return res;
}

int lgput(int base, int exp, int mod) {
  int res = 1;
  while (exp) {
    if (exp & 1) {
      res = (1LL * res * base) % mod;
    }
    base = (1LL * base * base) % mod;
    
    exp >>= 1;
  }
  
  return res;
}

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