#include <iostream>
#define int long long
using namespace std;

int fpow(int n, int p, int mod) {
    if(p == 0)
        return 1;
    if(p % 2)
        return n * fpow(n, p - 1, mod) % mod;
    int pw = fpow(n, p / 2, mod);
    return pw * pw % mod;
}

int getphi(int n) {
    int d, phi = n;
    for(d = 2; d * d <= n; d ++) {
        if(n % d == 0) {
            while(n % d == 0) n /= d;
            phi = (phi / d) * (d - 1);
        }
    }
    if(n != 1) phi = phi / n * (n - 1);
    return phi;
}

signed main() {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int n, mod; cin >> n >> mod;
    int phi = getphi(mod) - 1;
    cout << fpow(n, phi, mod);
}