/**
  *  Worg
  */
#include <cstdio>

FILE *fin = freopen("inversmodular.in", "r", stdin); FILE *fout = freopen("inversmodular.out", "w", stdout);

/*-------- Data --------*/
int a, n;
/*-------- --------*/

int ComputePhi() {
  int answer = n;
  int x = n;
  for(int i = 2; i * i <= x; i++) {
    if(x % i == 0) {
      while(x % i == 0) {
        x /= i;
      }

      answer = answer / i * (i - 1);
    }
  }

  if(x != 1) {
    answer = answer / x * (x - 1);
  }

  return answer;
}

int Power(int base, int exp, int mod) {
  int ans = 1, aux = base % mod;

  for(long long i = 1; i <= exp; i <<= 1) {
    if(i & exp) {
      ans = 1LL * ans * aux % mod;
    }
    aux = 1LL * aux * aux % mod;
  }

  return ans;
}

int main() {
  scanf("%d%d", &a, &n);

  int phi = ComputePhi();

  printf("%d\n", Power(a, phi - 1, n));

  return 0;
}