#include <bits/stdc++.h>

using namespace std;

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

int phi(int x) {
    int answer = x;
    for ( int i = 2; i <= x / i; i++  )
      if ( x % i == 0 ) {
        answer -= answer / i;
        while ( x % i == 0 )
          x /= i;
        }
    if (x > 1)
      answer -= answer / x;
    return answer;
}

int llput(int a, int b, int mod) {
    int answer = 1;
    while (b != 0 ) {
      if (b & 1)
        answer = (long long)answer * a % mod;
      a = (long long)a * a % mod;
      b >>= 1;
    }
    return answer;
}

int main() {
    int a, b, mod;
    fin >> a >> mod;
    b = phi(mod) - 1;
    fout << llput(a, b, mod);
    return 0;
}