#include <cstdio>
int A, N;
int totient(int N) {
 int result = N;
 for (int i = 2; i * i <= N; i++) {
  if (N % i == 0) {
   result = result / i * (i - 1);
   while (N % i == 0) {
    N /= i;
   }
  }
 }
 if (N != 1) {
  result = result / N * (N - 1);
 }
 return result;
}
int lgput(int base, int exponent, int MOD) {
 int result = 1, basePow2Value = base;
 for (int powIdx = 0; (1LL << powIdx) <= exponent; powIdx++) {
  if (exponent & (1 << powIdx)) {
   result = (1LL * result * basePow2Value) % MOD;
  }
  basePow2Value = (1LL * basePow2Value * basePow2Value) % MOD;
 }
 return result;
}
int main() {
 freopen("inversmodular.in", "r", stdin);
 freopen("inversmodular.out", "w", stdout);
 scanf("%d%d", &A, &N);
 printf("%d\n", lgput(A, totient(N) - 1, N));
 return 0;
}