#include <bits/stdc++.h>
using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long N, A;

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

    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) {
                x /= i;
            }
        }
    }

    if (x != 1) {
        res = res / x * (x - 1);
    }
    return res;
}

long long lgPow(long long base, long long exp, long long mod) {
    long long res = 1;

    while (exp) {
        if (exp & 1) {
            res = (res * base) % mod;
        }

        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    f >> A >> N;
    g << lgPow(A, phi(N) - 1, N) << '\n';
    return 0;
}