#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <deque>

using namespace std;
const int inf = 3e4 + 5;
const int NMax = 1e3 + 5;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
using zint = int;

int A,N;

zint getPhi(zint);
zint pw(zint,zint);

int main() {
    in>>A>>N;
    zint phi = getPhi(N);
    out<<pw(A,phi-1)<<'\n';

    in.close();out.close();
    return 0;
}

zint getPhi(zint nr) {
    zint ans = nr;

    for (zint i=2;i*i <= nr;++i) {
        if (nr % i != 0) {
            continue;
        }

        while (nr % i == 0) {
            nr /= i;
        }

        ans = 1ll * ans * (i-1) / i;
    }
    if (nr != 1) {
        ans = 1ll * ans * (nr-1) / nr;
    }

    return ans;
}

zint pw(zint base,zint exp) {
    zint ans = 1;
    while (exp) {
        if (exp & 1) {
            ans = (1ll * ans * base) % N;
        }
        base = (1ll * base * base) % N;
        exp >>= 1;
    }

    return ans;
}