/**
  *  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 - 1;
  for(int i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      answer--;

      if(i * i != n) {
        answer--;
      }
    }
  }

  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;
}