#include <iostream>

using namespace std;

//ifstream cin("inversmodular.in");
//ofstream cout("inversmodular.out");

int MOD;

int logpow(int val, int exp) {
    int ans(1), aux(val);
    while (exp > 0) {
        if (exp&1) {
            ans = 1LL * ans * aux % MOD;
        }
        exp>>=1;
        aux = 1LL * aux * aux % MOD;
    }
    return ans;
}

int phi(int val) {
    int a(3), ans(val);
    if (!val&1) {
        ans /= 2;
        while (!val&1) {
            val>>=1;
        }
    }
    while (a * a < val && val > 1) {
        if (val % a == 0) {
            ans /= a;
            ans *= (a - 1);
            while (val % a == 0) {
                val /= a;
            }
        }
        a += 2;
    }
    if (val > 1) {
        ans /= val;
        ans *= (val - 1);
    }
    return ans;
}

int main()
{
    int a, b;
    cin >> a >> b;
    MOD = b;
    cout << logpow(a,phi(MOD) - 1);
    return 0;
}