#include<cstdio>
#include <vector>
#include <cstring>
/* #include "Euclid.cpp"
#include "EuclidExtended.cpp"
#include "LCS.cpp"
#include "RabinKarp.cpp"
#include "KMP.cpp"
#include "Arbint.cpp"
#include "Eratosthenes.cpp"
#include "Heap.cpp"
#include "Permutations.cpp"
 */
using namespace std;

#include <cstdio>
#include <cmath>

using namespace std;

class InvMod {
private:

    int A, N;
    long long p[25];

    int phi(int x) {
        int d = x - 1;
        for (int i = 2; i * i <= N; i++)
            if (x % i == 0)d -= 2;
        return d;
    }

    void lgpowx(int px) {
        long long q = log2(px);

        p[0] = A;
        for (int i = 1; i <= q; i++)
            p[i] = (p[i - 1] * p[i - 1]) % N;
    }

    int lgpow(int n, int px) {
        long long ans = 1;
        int k = 0;
        lgpowx(px);
        while (px) {
            if (px & 1)
                ans = ans * p[k] % N;
            ++k;
            px = px >> 1;
        }
        return ans;
    }


public:
    void invMod_main() {
        freopen("inversmodular.in", "r", stdin);
        freopen("inversmodular.out", "w", stdout);

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

        printf("%d", lgpow(A, phi(N) - 1));

    }


} invMod;

int main() {
    invMod.invMod_main();
    return 0;
}