#include <bits/stdc++.h>

using namespace std;

long long phi(int N) {
    long long result = N, it;

    for (it = 2; it * it <= N; ++it) {
        if (N % it == 0) {
            do N /= it; while (N % it == 0);
            result = (result / it) * (it - 1);
        }
    }

    if (N != 1) {
        result = result / N * (N - 1);
    }

    return result;
}

int main() {
    long long A, N, power, result = 1, bit;

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

    scanf("%lld%lld", &A, &N);

    power = phi(N) - 1;

    for (bit = 1; bit <= power; bit <<= 1) {
        if (power & bit) {
            result = (result * A) % N;
        }

        A = (A * A) % N;
    }

    printf("%lld", result);

    return 0;
}