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

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

int n, mod;

static inline int putere(int a, int b) {
  int rez = 1;
  while(b) {
    if(b % 2 == 1)
      rez = (rez * a) % mod;
    a = (a * a) % mod;
    b /= 2;
  }
  return rez;
}

static inline int phi(int n) {
  int r = n, d = 2;
  while(n > 1) {
    int e = 0;
    while(n % d == 0) {
      n /= d;
      e++;
    }

    if(e)
      r = r / d * (d - 1);
    
    d++;
    if(d * d > n)
      d = n;
  }
  return r;
}

static inline int InvMod(int a, int b) {
  return putere(a, phi(b) - 1);
}

int main() {
  fin >> n >> mod;
  fout << InvMod(n, mod);

  return 0;
}