#include <cstdio>

int n;

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

int powLog(int base, int exp) {
  int pow = 1;
  int nr = base;
  for (int i = 1; i <= exp; exp /= 2) {
    if (i & exp)
      pow = (1LL * pow * nr) % n;
    nr = (1LL * nr * nr) % n;
  }
  return pow;
}

int main() {
  freopen ("inversmodular.in", "r", stdin);
  freopen ("inversmodular.out", "w", stdout);

  int a;
  scanf("%d%d", &a, &n);
  printf("%d\n", powLog(a, phi(n)));
  return 0;
}