#include <cstdio>
using namespace std;

typedef long long i64;

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

int main() {
    i64 n, i, a;

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

    scanf("%lld%lld", &a, &n);

    i64 phi = getphi(n)-1;
    i64 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;
}