#include <iostream>
#include <fstream>

using namespace std;

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

int logpow (int a, int n) {
    int p = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            p *= a;
        }
        a *= a;
        n /= 2;
    }
    return p;
}

int phi (int n) {
    int p = 2, k, rez = 1;
    while (p * p <= n) {
        k = 0;
        while (n % p == 0) {
            n /= p;
            k ++;
        }
        if (k > 0) {
            rez *= logpow (p, k - 1) * (p - 1);
        }
        p ++;
    }
    if (n > 1) {
        rez *= (n - 1);
    }
    return rez;
}

int main() {
    int a, n;
    long long int rez;
    in >> a >> n;
    rez = logpow (a, phi (n) - 1) % n;
    out << rez;
    return 0;
}