#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);

int A, N;

int main() {
  fin >> A >> N;
  fout << log_pow(A, N - 2);
  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 mod(int64 x, int m) {
  if (x < m) return x;
  if (x < 2 * m) return x - m;
  return x % m;
}