#include <iostream>
#include <fstream>

using namespace std;

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

int n, mod;

int get_phi(int x) {
    int rez = x;
    if (x % 2 == 0) {
        while (x % 2 == 0) x /= 2;
        rez = rez / 2;
    }
    for (int i = 3; i * i <= x; i += 2)
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            rez = rez / i * (i - 1);
        }
    if (x != 1) rez = rez / x * (x - 1);
    return rez;
}

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 == 1) aux = (1LL * aux * x) % mod;
    return aux;
}

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