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

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

long long n, mod;

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

static inline long long phi(long long n) {
  long long 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;
}

//daca modul este un numar prim atunci vom ridica pe a la puterea mod - 2 pentru ca mod are deja mod - 1 nr prime cu el;
static inline long long InvMod(long long a, long long b) {
  return putere(a, phi(b) - 1);
}

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

  return 0;
}