#include <cstdio>
#define LL long long
using namespace std;

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

int main() {
    int n, i, phi;
    LL a, inv;

    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%lld%d", &a, &n);
    phi = getphi(n)-1;
    inv = 1;
    for (i = 1; i <= phi; i <<= 1) {
        if (phi & i) inv = (inv * a) % n;
        a = (a * a) % n;
    }

    printf("%d", inv);

    return 0;
}