#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

typedef long long int64;

inline int64 log_pow(int x, int p);
inline int mod(int64 x, int m);
inline int phi(int x);

int A, N;

int main() {
  fin >> A >> N;
  fout << log_pow(A, phi(N) - 1);
  return 0;
}

inline int64 log_pow(int x, int pow) {
  int64 result = 1;
  for (int64 p = 1, log2_p = x; p <= pow; p *= 2) {
    if (p & pow) {
      result = mod(result * log2_p, N);
    }
    log2_p = mod(log2_p * log2_p, N);
  }
  return result;
}

inline int phi(int x) {
  int result = 0;
  for (int d = 2; d * d <= x; ++d) {
    if (x % d == 0) {
      while (x % d == 0) x /= d;
      ++result;
    }
  }
  if (x) ++result;
  return x - result;
}

inline int mod(int64 x, int m) {
  if (x < m) return x;
  if (x < 2 * m) return x - m;
  return x % m;
}