# include <cstdio>

const char *FIN = "inversmodular.in", *FOU = "inversmodular.out";
typedef long long ll;

ll N, M;
ll phi (ll x) {
    ll sol = x;
    for (int i = 2; 1LL * i * i <= x; ++i)
        if (x % i == 0) {
            for (; x % i == 0; x /= i);
            sol /= i, sol *= i - 1;
        }
    if (x != 1) sol /= x, sol *= x - 1;
    return sol;
}

ll lgput (int N, int P, int MOD) {
    ll sol = 1;
    for (; P > 0; P >>= 1) {
        if (P & 1) sol *= N, sol %= MOD;
        N = (1LL * N * N) % MOD;
    }
    return sol;
}

int main (void) {
    fscanf (fopen (FIN, "r"), "%lld %lld", &N, &M);
    fprintf (fopen (FOU, "w"), "%lld", lgput (N, phi (M) - 1, M));
}