#include <fstream>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return gcd(b % a, a);
    }
}

int phi(int n) {
    int res = 1;
    for (int i = 2; i <= n; ++i) {
        if (gcd(i, n) == 1) {
            ++res;
        }
    }
    return res;
}

int main()
{
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");

    int a, n;
    cin >> a >> n;

    int64_t ans = 1;
    for (int i = 1; i <= phi(n) - 1; ++i) {
        ans *= a;
    }
    cout << ans % n;

    return 0;
}