#include <stdio.h>
#include <stdint.h>
#include <math.h>

void read_uint64_t(FILE *__restrict stream, uint64_t *__restrict nr) {
  uint8_t ch;
  *nr = 0;
  while ((ch = fgetc(stream)) && ('0' <= ch && ch <= '9')) {
    *nr *= 10;
    *nr += ch - '0';
  }
  if (ch == '\r') {
    fgetc(stream);
  }
}

uint64_t etot(uint64_t x) {
  uint64_t sqx = sqrt(x);
  uint64_t res = x;
  int32_t i;
  for(i = 2; i <= sqx; ++i) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
      }
      res -= res / i;
    }
  }
  if (x != 1) {
    res -= res / x;
  }
  return res;
}

uint64_t lpowm(uint64_t b, uint64_t exp, uint64_t mod) {
  uint64_t r = 1;
  b %= mod;
  if (exp == 0) {
    return r;
  }
  while (exp != 0) {
    if ((exp & 1) == 1) {
      r *= b;
      r %= mod;
    }
    exp >>= 1;
    b *= b;
    b %= mod;
  }
  if (r == 0) {
    return -1;
  }
  return r;
}

int main(void) {
  uint64_t a, n;
  {
    FILE *__restrict in = fopen("inversmodular.in", "r");
  
    read_uint64_t(in, &a);
    read_uint64_t(in, &n);
  
    fclose(in);
  }

  {
    FILE *__restrict out = fopen("inversmodular.out", "w");
  
    fprintf(out, "%lu\n", lpowm(a, etot(n) - 1, n));
  
    fclose(out);
  }

  return 0;
}