#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");

int n, mod;

int get_phi(int x) {
    int phi = x;

    if (x % 2 == 0) {
        while(x % 2 == 0) {
            x /= 2;
        }
        phi = phi / 2;
    }

    for (int d = 3; d * d <= x; d += 2) {
        if (x % d != 0) continue;

        while(x % d == 0) {
            x = x / d;
        }
        phi = phi / d * (d - 1);
    }

    if (x != 1) phi = phi / x * (x - 1);
    return phi;
}

int putere(int x, int p, int mod) {
    if (p == 0) return 1;

    int aux = putere(x, p / 2, mod);
    aux = (1LL * aux * aux) % mod;
    if (p % 2) return 1LL * x * aux % mod;
    return aux % mod;
}


int main() {
    f >> n >> mod;
    int phi = get_phi(mod);
    g << putere(n, phi - 1, mod) << '\n';
    return 0;
}