#include <bitset>
#include <fstream>
#include <iostream>
#include <vector>

std::ifstream in("inversmodular.in");
std::ofstream out("inversmodular.out");

constexpr int nmax = 1000001;

std::bitset<nmax> ciur;
std::vector<int> prime;

void genciur() {
  ciur[1] = ciur[0] = true;
  for (int i = 4; i < nmax; i += 2)
    ciur[i] = true;
  for (int i = 3; i * i <= nmax; ++i)
    if (!ciur[i])
      for (int j = i * i; j <= nmax; j += 2 * i)
        ciur[j] = true;
  for (int i = 1; i <= nmax; ++i)
    if (!ciur[i])
      prime.emplace_back(i);
}

int phi(int n) {
  int d = 0, r = n;
  while (prime[d] * prime[d] <= n) {

    if (n % prime[d] == 0) {

      r -= r / prime[d];
      while (n % prime[d] == 0)
        n /= prime[d];
    }
    d++;
  }
  if (n > 1)
    r -= r / n;
  return r;
}

int pow(int a, int b, long long mod) {
  int r = 1;
  while (b) {
    if (b & 1)
      r = 1LL * (1LL * r * 1LL * a) % mod;
    a = 1LL * (1LL * a * 1LL * a) % mod;
    b /= 2;
  }
  return r;
}

int main() {
  prime.reserve(80000);
  genciur();

  int a;
  long long n;
  in >> a >> n;
  out << pow(a, phi(n) - 1, n);
  return 0;
}