#include <bits/stdc++.h>

using namespace std;

int phi(int x) {
    int ans = x;

    for (int i = 2; i * i <= x; ++i) {
        if (x % i)
            continue;

        ans = (1LL * ans * (i - 1)) / i;

        while (x % i == 0)x /= i;
    }

    if (x > 1)
        ans = (1LL * ans * (x - 1)) / x;

    return ans;
}

int put(int a, int b, int mod) {
    int ans = 1;

    for (; b; b >>= 1) {
        if (b & 1)
            ans = 1LL * ans * a % mod;

        a = 1LL * a * a % mod;
    }

    return ans;
}
int main() {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int n, a;
    scanf("%d%d", &a, &n);
    printf("%d\n", put(a, phi(n) - 1, n));
}